Author |
Topic: Arimaa rating deflation (Read 30012 times) |
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender: 
Posts: 1413
|
 |
Re: Arimaa rating deflation
« Reply #15 on: Nov 29th, 2003, 8:01pm » |
 Quote  Modify
|
on Nov 29th, 2003, 7:29pm, MrBrain wrote:| The question is, how many "levels" of bots would be between random and shallowblue? I believe that at worst, there would be a bot that could beat random 99% of the time, while it could beat shallowblue 1% of the time. |
|
That's what I'm saying when I say that random would be approximately -2000... I think there are 4 levels between random and shallowblue where each can beat the ones below. Clauchau pointed out that there are actually an infinite number, but I'm talking about stochastic ones. But anyway, it's only a guess based on seeing how random played a couple of times.
examples of the levels in between them are:
0) Random
1) Random, no suicide (NS)
2) Random, NS, Rabbits Forward (RF)
3) Greedy Killer, Otherwise Random NS
4) Greedy Killer, RF, Otherwise Random NS
5) Shallowblue
|
|
 IP Logged |
|
|
|
MrBrain
Forum Guru
Arimaa player #344
Gender:
Posts: 148
|
|
Re: Arimaa rating deflation
« Reply #16 on: Nov 29th, 2003, 8:20pm » |
Quote Modify
|
"An infinite number" would indicate that we are saying that a bot will beat another bot just a simple majority of the time. But 51% victories does not a 400-point difference make. I think if you defined a "whole new level" to mean winning 99% of the time, then I don't believe there would be more than 2 levels between random and shallowblue.
By the way, I created a bot that is worse than random, "bot_brain". It plays by moving its elephant to the middle, and then in subsequent moves, moving its elephant one space clockwise, or if that's blocked, counterclockwise, and if that's blocked too, it resigns. Yet even though this bot should, according to what you're saying, be rated less than -2000, it beat bot_occam, because bot_occam lost on time (don't know why).
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimaa rating deflation
« Reply #17 on: Nov 30th, 2003, 5:35am » |
Quote Modify
|
Yes, it is possible to have a very large number of bots in between that beat all below them 100% of the time. I think Clauchau was thinking of deterministic bots, where it's either 100%, 50% or 0%.
|
|
IP Logged |
|
|
|
MrBrain
Forum Guru
Arimaa player #344
Gender:
Posts: 148
|
|
Re: Arimaa rating deflation
« Reply #18 on: Nov 30th, 2003, 8:18am » |
Quote Modify
|
I don't think there can be as many levels in arimaa as there are in go. Even with a random bot, there's a good chance that it will do something good (move a rabbit forward). In go, it seems that a random player would have almost no chance of doing anything constructive. And from looking at the levels you have there, it's not clear to me that 1 would always beat 0. It seems that sometimes, 0 would play as well as 1 just by luck (having a friendly piece next to a trap before it walks into one). Also, I believe that 3 would play better against 2 than it does against 1 since the rabbits moving forward would quickly be eaten. Also, it's not clear to me that 3 would be any worse than 4, and could actually be better.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimaa rating deflation
« Reply #19 on: Nov 30th, 2003, 10:09am » |
Quote Modify
|
on Nov 30th, 2003, 8:18am, MrBrain wrote:| And from looking at the levels you have there, it's not clear to me that 1 would always beat 0. It seems that sometimes, 0 would play as well as 1 just by luck (having a friendly piece next to a trap before it walks into one). Also, I believe that 3 would play better against 2 than it does against 1 since the rabbits moving forward would quickly be eaten. Also, it's not clear to me that 3 would be any worse than 4, and could actually be better. |
|
I'm convinced that 1 would beat 0 in 99% of cases. Games between these 2 would be quite long, and the occasional material advantage would grow and grow. Defending your own trap against suicide is not sufficient. To get to the other side you have to go past the opponent traps...
I agree with you that the results between 3 and 4 are not clear - it was hard to make up those examples, because I couldn't really visualise the game - however I do know that when Gnobot was a primitive 1-ply, it still easily lost to Shallowblue.
|
|
IP Logged |
|
|
|
MrBrain
Forum Guru
Arimaa player #344
Gender:
Posts: 148
|
|
Re: Arimaa rating deflation
« Reply #20 on: Nov 30th, 2003, 10:15am » |
Quote Modify
|
Yes, I think you have convinced me (although the examples you gave are not conclusive) that random would be significantly lower than 0 on the current scale.
On the other hand, 0 for completely random (meaning something different than what Omar suggested, i.e. random position selection as opposed to random move selection) is aesthetically very pleasing. So despite the fact that it would significantly impact the rating scale, I think it should be done at some point.
A couple of things to note, however. Sometimes bots lose on account of interface issues, on time, etc. This may account for some unexpected results. Also, it is also possible to have a "cycle" of bots (1 beats 2 a majority of the time, 2 beats 3, and 3 beats 1). Such "cycles" would have a tendency to keep the ratings closer together than with a "chain" of bots who always beat the bot next in line.
|
| « Last Edit: Nov 30th, 2003, 10:16am by MrBrain » |
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Arimaa rating deflation
« Reply #21 on: Nov 30th, 2003, 10:16pm » |
Quote Modify
|
By random I was thinking of generating all valid board positions and then selecting one at random. Mostly because this is the first step before applying an evaluation function to each of the positions to get a 1 ply bot.
Also for the random initial setup. I think it would be OK for bot_random to use a semi-random setup lik most of the good bots do. For example have it select one from a set of predefined intial positions or fix the postion of the rabbits to the back row and randomly place the stronger pieces. This is just so that the initial setup does not become a big negitive factor in it's performance.
Fixing the rating of bot_random bot to 0 I think makes the most sense.
The next step would be to make a 1 ply bot that has a pretty good evaluation function and see what percent of the games it wins.
I think the games between such bots should be played offline using a
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Arimaa rating deflation
« Reply #22 on: Dec 1st, 2003, 12:29am » |
Quote Modify
|
My keyboard at home stopped working. I rebooted the compter and it didn't help. Problem is Im in the middle of a game with bot_Bomb. So I rushed over to the office to use the computer here. Good thing I had a lot of reserve time left.
I think the games between such bots should be played offline using a referee script in between which passes the move from one bot to the other. This avoids problems with games being lost due to network or server problems. Also it is going to require a lot of games to get good statistical numbers.
For the bots in between 0 and 1 ply I think we should use the 1 ply bot and pass it some parameter that specifies what percent of the moves it should look 1 ply deep. I perfer this over methods that use different evaluation functions because it is not specific to Arimaa and could be used with other games as well.
How the bot decides at each move if it should look 1 or 0 ply could be done stocastically or deterministically. The bot could do this stocastically by randomly picking a number before each move and comparing it to the given percentage to decide if it should look 1 ply or 0 ply deep. One way of doing it deterministically is to keep a running total of the number of moves it looked 1 ply and the number of moves it looked 0 ply and chosing the next one to bring the ratio closer to the given percentage. Im a bit inclined to use the deterministic method.
Im guessing that a bot that looks at 1 ply on 10% of the moves would only be slightly stronger than the random bot. In a 40 move game it would have looked 1 ply only on about 4 moves. Then a 20%, 40% and 70% bot would gradually get us up to a full 1 ply bot. Then a similar set of bots could get us from 1 ply to 2 ply. So we would only need about 10 bots to get to 2 ply bots (which we know is a good match for beginners). But this number is just a guess.
Once we have established a rating for the 2 ply bot we could then adjust the ratings in the gameroom and also have a good estimate of what rating to bring in new players. For example if the 2 ply bots rating in the gameroom was 1400 but among the simple bots it has a rating of 2400, then we just add 1000 to all the ratings in the gameroom and bring in new players at around 2000.
I've been thinking about this for awhile, but just have not had the time to create such bots and run the games. Maybe if we all work together on this we can get it done. Any takers?
Omar
|
|
IP Logged |
|
|
|
fotland
Forum Guru
Arimaa player #211
Gender:
Posts: 216
|
|
Re: Arimaa rating deflation
« Reply #23 on: Dec 1st, 2003, 2:15am » |
Quote Modify
|
You can do this experiment with ariminator. In the startup dialog you can see a box labeled "chance of blunder". You can set the depth to 4 steps and the chance of blunder to 90%, and it will only consider 10% of the legal moves at the first step.
David
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimaa rating deflation
« Reply #24 on: Dec 1st, 2003, 4:27am » |
Quote Modify
|
This:
on Dec 1st, 2003, 2:15am, fotland wrote:it will only consider 10% of the legal moves at the first step.
|
|
is a bit different to this:
Quote:| a bot that looks at 1 ply on 10% of the moves |
|
Omar is talking about each time the bot steps up for its turn, it has a 10% chance of being a 1 ply bot, and a 90% chance of being a 0 ply bot.
|
| « Last Edit: Dec 1st, 2003, 10:13am by 99of9 » |
IP Logged |
|
|
|
MrBrain
Forum Guru
Arimaa player #344
Gender:
Posts: 148
|
|
Re: Arimaa rating deflation
« Reply #25 on: Dec 1st, 2003, 8:17am » |
Quote Modify
|
on Nov 30th, 2003, 10:16pm, omar wrote:| Also for the random initial setup. I think it would be OK for bot_random to use a semi-random setup lik most of the good bots do. For example have it select one from a set of predefined intial positions or fix the postion of the rabbits to the back row and randomly place the stronger pieces. This is just so that the initial setup does not become a big negitive factor in it's performance. |
|
No, I strongly disagree. If our standard is to be a truly random robot, then make it truly random. There should be no predetermined strategy considerations or intelligence in the play of this bot whatsoever, either during the game, or for initial setup.
If you like, you could make an intermediate bot, slightly stronger than the truly random bot, which plays random, but has predetermined initial setups. I think the difference in strength between these two bots would be negligible, however.
|
| « Last Edit: Dec 1st, 2003, 8:22am by MrBrain » |
IP Logged |
|
|
|
MrBrain
Forum Guru
Arimaa player #344
Gender:
Posts: 148
|
|
Re: Arimaa rating deflation
« Reply #26 on: Dec 1st, 2003, 8:20am » |
Quote Modify
|
on Nov 30th, 2003, 10:16pm, omar wrote:| By random I was thinking of generating all valid board positions and then selecting one at random. Mostly because this is the first step before applying an evaluation function to each of the positions to get a 1 ply bot. |
|
Yes, this is my method #2 which we all seem to agree on. However, great care must be taken when implementing this method so that the each unique position different than the current position is generated once and only once.
|
|
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: Arimaa rating deflation
« Reply #27 on: Dec 1st, 2003, 8:45am » |
Quote Modify
|
I'll contribute to the experiments.
Toby's, Omar's and David's ideas of partially random bots seem all interesting to me. Toby's is my favorite to explore Arimaa. I'll add essential variants that are as many improvements as human beginners are likely to go through:
- the Stepper thinks at the step level only. He randomly picks up a step among all the valid steps or all the valid steps that maximize his good feeling about his position, and he repeats this four times to achieve his move;
- while the Mover is aware of the whole set of positions she can reach with a valid move (Brian, most bots here already do that);
- the Infiltrator is happy with one rabbit going as far as possible, so she views the board as an integer from 1 to 8 - the row of her farthest rabbit;
- while the Flooder is happy with getting many rabbits as far as possible, so he views the board as some 8-uple of integers - how many rabbits he has got on the last row, how many on the row before, and so on;
- the Attacker focuses on the advantages of his position only and maximalises the resulting value, for example his rabbits' rows or his material. An Attacking Infiltrator might be called a Pro-Infiltrator. In general an Attacker tends to play short games;
- while the Defender strives to counter her opponent's advantages only and does not really tries get closer to win. A Defending Infiltrator might be called an Anti-Infiltrator. In general a Defender tends to play long games;
- and the Symmetrical is equally happy with maximazing her good feeling or minimizing her opponent's good feeling (take the difference "her value minus her opponent's value").
Unlike Omar, I'd rather call C++ playing functions in turn in the same program to share the data and not wave the whole board around between every move. That should be fast. Thousands of games would be as easy to collect as drinking a cup of tea meanwhile.
|
| « Last Edit: Dec 7th, 2003, 5:52am by clauchau » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimaa rating deflation
« Reply #28 on: Dec 1st, 2003, 10:28am » |
Quote Modify
|
on Dec 1st, 2003, 12:29am, omar wrote:
For the bots in between 0 and 1 ply I think we should use the 1 ply bot and pass it some parameter that specifies what percent of the moves it should look 1 ply deep. I perfer this over methods that use different evaluation functions because it is not specific to Arimaa and could be used with other games as well.
|
|
No matter what, it's not comparable with other games, because of the specific evaluation function you implement in your 1 ply eval. If that is a good one, then your 100% 1 ply bot will be good, if that is a bad one, then your 100% 1 ply bot will be bad.
I admit that what you are suggesting is aesthetically nice, but I don't think comparison between games will be that easy.
Instead I would go for Eval functions which are as simple and easily described as possible, so that there are as few arbitrary parameters as possible. (eg the concept of "no suicide" needs no parameters, the concept of "greedy for material" doesn't have many parameters).
Perhaps just go with Omar's approach using a purely materialistic evaluator (with win conditions also in eval)? At sufficient depth (approx 50% 2 ply) this would eventually surpass shallowblue. But don't expect to be able to compare these intermediate bots with their equivalents in other games. Maybe it's still fair to ask how far above random are humans though.
|
|
IP Logged |
|
|
|
MrBrain
Forum Guru
Arimaa player #344
Gender:
Posts: 148
|
|
Re: Arimaa rating deflation
« Reply #29 on: Dec 1st, 2003, 1:21pm » |
Quote Modify
|
How about using the inherent scoring function in the game itself? This takes into account material and rabbit position. The score of a function could be s1-s2 where s1 is the score of our position and s2 is the score of the opponent's position. (This approach is simply utilizing something that's in the rules of the game already. There is no abitrary decision that has to be made about any kind of evaluation function.)
Now as far as the bots between 0 and 1 ply go, 0 ply is equivalent to choosing one position randomly out of all positions, evaluating, and then choosing the best one. Since there's only one position that we've chosen, the best one is obviously that one no matter what the evaluation function says about it.
Now, a significantly stronger bot would be one that chooses just 2 positions randomly. This bot would already have the ability to avoid suicides somewhat, and to advance rabbits. It's unlikely that of two random positions, that the one with the higher score is one where a suicide occurred, or one in which an opponent's rabbit would be pulled further towards the goal. (Omar, I noticed that your sample code did a lot more suicides and "helping" of opponent's rabbits than would be expected from the description (choosing 10 positions and evaluating to find the best one). My guess is that some sign was switched somewhere in the code or something of that nature.)
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print