Author |
Topic: Arimaa scoring function discussion (Read 5147 times) |
|
omar
Forum Guru
Arimaa player #2
Gender: 
Posts: 1003
|
 |
Arimaa scoring function discussion
« on: Aug 14th, 2004, 6:03pm » |
 Quote  Modify
|
The Arimaa match rules define a scoring function that
is used to decide the outcome of a game should a game
not finish naturally within the time allotted for the game.
http://arimaa.com/arimaa/learn/matchRules.html
In a different post 99of9 commented:
The gripe: the arimaa scoring function is terrible!! I think it WAY overvalues advanced rabbits. Have a look at the game bot_firsttry played against bot_Gnobot2004CC. That game was decided by score after 8 hours (fair enough!), but the wrong bot was given the game as far as I'm concerned. Firsttry had only lost one dog. Gnobby on the other hand had only 4 pieces left... elephant, camel and 2 advanced rabbits.
http://arimaa.com/arimaa/gameroom/replayFlash.cgi?gid=6990&s=b
Ok sure, we could all program our bots to push the opposing rabbits back when we get to 7 hours and 50 minutes... but that would just be silly, and counter to the idea of developing great game playing ai. Instead I think you should change the scoring function (a lot). I understand that it's good to incentivise pushing rabbits forward, because it gets the game going... but I think this amount is excessive, and I don't think any of the current bots are deliberately trying to play silly stalemate arimaa.
If that result had happened in the bot championships I would be pretty annoyed! (no matter which bots it was that were playing) What do other people think?
To which Haxe replied:
Omar has once made the very good suggestion to simply give the win to the player with the most time left instead of evaluating to position. As he pointed out, this will not only be more fair than an arbitrary evaluation, but will probably also influence the behaviour of the players so that games are less likely to be ended by time at all.
I think this would be really great. Please give it a second thought, and, if applicable, introduce this new rule as soon as possible, before people get used to the scoring thing.
I still like the idea of the player with the most amount
of time left winning.
Advantages:
1. No need for a scoring function.
2. Preasures the players to finish the game naturally.
3. Independent of the game.
Disadvantages:
1. A player that is clearly winning can still lose.
What do others think.
Omar
|
|
 IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Arimaa scoring function discussion
« Reply #1 on: Aug 15th, 2004, 4:56pm » |
Quote Modify
|
I'm not averse to that idea - I think it is better than the current scoring function!
One problem I forsee is both players ending with full time in reserve - who wins?
Many bots ensure they use just less than the total time per move. If both bots were doing this they would end with the situation above.
To fix this, and augment your method I suggest this:
Just stop incrementing the time once the game gets to 8 hours (or 7.5). Then if the bots have been judicious with their use of time they will have 15 min on the clock, and the game will definitely end within 30 min.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Arimaa scoring function discussion
« Reply #2 on: Aug 16th, 2004, 10:14pm » |
Quote Modify
|
Actually I was not even thinking about the reserve time.
What I ment to say was the player that has used
the least amount of total time for making all their moves
should win when the game time runs out.
Omar
|
|
IP Logged |
|
|
|
MrBrain
Forum Guru
Arimaa player #344
Gender:
Posts: 148
|
|
Re: Arimaa scoring function discussion
« Reply #3 on: Sep 10th, 2004, 2:04pm » |
Quote Modify
|
That seems good. Make sure the total amount of time used for each player is shown though. Otherwise, you might have to guess to figure out who's winning the time game.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Arimaa scoring function discussion
« Reply #4 on: Sep 15th, 2004, 8:17pm » |
Quote Modify
|
I have a general prejudice against games being decided on time. I avoid sudden-death time controls, because I feel that they make time just as important as (if not more important than) the position on the board. The clock is a necessary evil to prevent delays, true, but there is no reason to exaggerate its significance.
In a game of Arimaa which has gone the allotted total time without a victor, I'm opposed to deciding a victor by some positional score formula or time formula. I say that if you can't play the game out to its finish on the board, then you have to call it a draw. Any other solution rewards something other than good play.
The one thing this formula will do is encourage more aggressive play by the side in the lead as the cutoff time is approaching. This has advantages and disadvantages, but at least good play is still necessary to win, as opposed to merely fast play, or pushing rabbits crazily.
I frankly expect that if time-cutoff games are declared draws, then very, very few human vs. human games will be drawn because of it. It will be mostly if not entirely the bots who are affected, and if they're too dumb to win with a big advantage on the board, they deserve to only get the draw.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimaa scoring function discussion
« Reply #5 on: Sep 16th, 2004, 8:21am » |
Quote Modify
|
on Sep 15th, 2004, 8:17pm, Fritzlein wrote:
In a game of Arimaa which has gone the allotted total time without a victor, I'm opposed to deciding a victor by some positional score formula or time formula. I say that if you can't play the game out to its finish on the board, then you have to call it a draw. Any other solution rewards something other than good play. |
|
I'm a little bit swayed by this argument. But the thing is, that often it takes quite a while to finish someone off in arimaa. This means that often when a game ends because the allotted time has gone, it's just that the one who was clearly ahead had not quite finished finishing his/her/its opponent off.
I would be perfectly happy with a scoring function based on material that said something like "if neither player is ahead by more than a horse, then it's a draw".
But on the other hand, Omar's method is very definitive... and neat...
on Sep 15th, 2004, 8:17pm, Fritzlein wrote:
The one thing this formula will do is encourage more aggressive play by the side in the lead as the cutoff time is approaching. This has advantages and disadvantages, but at least good play is still necessary to win, as opposed to merely fast play, or pushing rabbits crazily. |
|
It also encourages stalling play by the side that is behind. Imagine, you're a few moves from victory, and your opponent decides it would be a good idea to use the whole 3min and the 15min he/she/it has in reserve! At least Omar's method would prevent this AS WELL AS encouraging more aggressive play by the side who is ahead.
on Sep 15th, 2004, 8:17pm, Fritzlein wrote:
I frankly expect that if time-cutoff games are declared draws, then very, very few human vs. human games will be drawn because of it. |
|
No, this comment is too hasty. Obviously it depends on what the time cutoff is! But I presume you were talking about something in the 8 hour region that we have for most tournaments? Remember that they use 3 minute time controls, which means 10 moves per side per hour. This gives a total of only about 80 moves if both players are playing as carefully as possible (as would be usual in a good tournament). I am very confident that an arimaa game can go for more than 80 moves with both players trying their very best to win. Of course for this to happen both players must be reasonably good, and reasonably defensive players. But it could definitely happen. I can see myself being involved in such a game. By move 80 I would usually expect to see one side with an advantage, but they may not yet have fully converted it into a win. Note that most recent wins over speedy have been been around 60 moves... and speedy is not *that* good  . You yourself played a 115 move game to beat speedy, I presume that was not because you were "too dumb to win".
on Sep 15th, 2004, 8:17pm, Fritzlein wrote:
It will be mostly if not entirely the bots who are affected, and if they're too dumb to win with a big advantage on the board, they deserve to only get the draw. |
|
That's all very well for the dumb "all defensive" bots. But my impression is that as humans improve at arimaa, the length of their best games is getting longer. I believe this will be true for bots also (presuming you are matching top bots with other top bots).
I remember some of my games against Belbo and Naveed where the first tangible lead that either player got was when a single rabbit got dragged forward a single step... on move 25!!!!!!
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimaa scoring function discussion
« Reply #6 on: Sep 16th, 2004, 8:26am » |
Quote Modify
|
Oh, and plus... one of the greatest things about arimaa is that the game hardly ever results in a draw. I think it's a fantastic example of a game which is poised on an unstable equilibrium at the start, and it becomes more and more unstable as the number of pieces is reduced.
Which reminds me... I think Naveed threw away a game against speedy in the last few moves, a game which could have been the greatest arimaa draw I've ever seen.
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Arimaa scoring function discussion
« Reply #7 on: Sep 16th, 2004, 11:11am » |
Quote Modify
|
Ideally one would allow all games to be played out to victory over the board, since draws are extremely rare. A peek at the newly available game database shows that in 7957 games, one was drawn and one decided on score. Still, if you must cap the total time allowed for a game, whatever method you use to determine a victor should (IMHO) deviate as little as possible from favoring whoever we think would win if the game were to continue.
Omar's proposal to award the game to whoever used less total time does not encourage aggressive play by whoever is ahead on the board. It encourages defensive play by whoever has used less total time, even if that player is ahead on the board. If I have used less time than you, I can cool my heels, play defensively, and try to win "on time" when the total time for the game is used up. Admittedly, the player who is behind on total time used might be encouraged to play aggressively, but if that player isn't ahead on the board, they would be better off playing defensively and as fast as possible so as to try to get ahead on total time used and win at the cutoff. I can imagine a strange sort of time scramble where neither player is trying to win on the board any more, but both are trying to be the one to use less total time, so in 8 hours each player makes 400 moves without making progress.
If you must cut off a game at 8 hours (and I think it is reasonable to do so) then three minutes per move is too much. Two minutes per move allows at least 120 moves in the game, and even two and a half minutes per move allows 96 moves. It may be a bit on the short side to allow only 80 moves to convert a win, but I'd be fairly comfortable with allowing only 100.
Yes, my 115 move win against speedy illustrated quite a bit of dumbness on my part. I made many waiting moves while I was trying to think of a plan and/or wait for a mistake from speedy. With a slower time control I would have converted in fewer moves even without the pressure of a move cutoff.
I am glad that draws aren't really an issue at present, but I am curious to see whether they will be to a greater extent in the future. Quite possibly a rising level of play will make it more likely for a game to stay balanced for longer at the beginning. On the other hand, it is also possible that a rising level of play will allow quicker conversion of won positions.
It is in the nature of Arimaa that an advantage snowballs, and I believe that the better the players are, the more inevitable this is. In fact, a good human player will not let an opponent slowly and surely accumulate an advantage, but will "mix it up" in hopes of reversing the tide, which will further tend to shorter games.
You correctly point out a disadvantage of calling games draws if no one has won by time cutoff, namely that a player may choose a strategy designed to hang on only for a certain number of moves, even if that strategy will certainly lose in the long run. If this happens a significant fraction of the time with, say, a 100-move cutoff, then I'd go back to a materialistic score formula rather than total time usage.
Here's my first pass at a new scoring function: Line up all the remaining pieces for both sides. If the strongest piece on each side is the same piece, remove both. Otherwise remove the strongest piece from the player who has it and from the other player remove their strongest and weakest piece. Repeat. Whoever runs out of pieces first loses. (exception - a player with no rabbits who would win under this formula only draws instead)
This doesn't reward rabbit advancement, but I don't mind, because advanced rabbits can be a disadvantage as much as an advantage. I'd rely on material advantage instead.
Just some thoughts.
Peace,
-Karl
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Arimaa scoring function discussion
« Reply #8 on: Sep 19th, 2004, 5:36am » |
Quote Modify
|
on Sep 10th, 2004, 2:04pm, MrBrain wrote:| That seems good. Make sure the total amount of time used for each player is shown though. Otherwise, you might have to guess to figure out who's winning the time game. |
|
Yes definitely. In place of showing the scores for each player the total time that each player has used would be shown.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Arimaa scoring function discussion
« Reply #9 on: Sep 20th, 2004, 12:35pm » |
Quote Modify
|
on Sep 16th, 2004, 11:11am, Fritzlein wrote:| A peek at the newly available game database shows that in 7957 games, one was drawn and one decided on score. |
|
And if I remember right, the draw was a deliberate one against an easy bot.
Quote:| Still, if you must cap the total time allowed for a game, whatever method you use to determine a victor should (IMHO) deviate as little as possible from favoring whoever we think would win if the game were to continue. |
|
Or you find a method which works to ensure the game will finish faster, which effectively prevents itself from ever being used. This is the type of method that Omar has proposed. Another method in this category is "upon timeout, both players lose"... surely no one with a chance of winning would ever stall under that method!
Quote:| I can imagine a strange sort of time scramble where neither player is trying to win on the board any more, but both are trying to be the one to use less total time, so in 8 hours each player makes 400 moves without making progress. |
|
This would never happen for the entire 8 hours. If you play at a scramble, I will beat you using my full 3 minutes per move.
In fact we already have plenty of examples of how it would go on a shorter timescale. Arimaa already permits fixed time games ("game in 30 minutes"). I have had quite a few of these extremely short ones with other human players. Because the overall time was so short, the pace was brisk, but there was never a scramble until players had well under 10 minutes left on their clock. To scramble earlier was to leave yourself open to blunders.
What happened during the srambles was not quite as you describe either. These games had all reached endgame by the time time was running out (of course an 8 hour game would be even closer to endgame I would expect). The most effective form of scrambling turns out not to be just to make a singular step and send that as your whole move. Although that is very quick, it does not put any pressure on your opponent. Playing 4 steps is still worthwhile, and the more goal threats you can put on him, the more likely he is to either blunder, or have to spend time on his reply. Basically it turns out to be reasonable blitz-arimaa ... and the leader generally wins (although in those short games about 1/4 of the games do go to timeout).
Quote:| If you must cut off a game at 8 hours (and I think it is reasonable to do so) then three minutes per move is too much. Two minutes per move allows at least 120 moves in the game, and even two and a half minutes per move allows 96 moves. |
|
What do others think about this, especially given that arimaa games *are* getting longer in terms of number of moves (as discussed in another thread)? I also think that 2 minutes might be better - but then again, everyone knows I'm not a thinker.
Quote:| I am glad that draws aren't really an issue at present, but I am curious to see whether they will be to a greater extent in the future. Quite possibly a rising level of play will make it more likely for a game to stay balanced for longer at the beginning. |
|
I predict we will see a high-level draw within the next year. However, I don't think the number of draws will ever exceed 1% of all arimaa games.
The prevalence of draws will also depend on which strategy eventually predominates. Specifically, is it better to drag opponent's rabbits, or try to drag opponent's big pieces? As far as I can see, both have their advantages and disadvantages, and no one strategy has become universal. If the answer is that dragging rabbits is better - then there might be many more arimaa draws.
Quote:| It is in the nature of Arimaa that an advantage snowballs, and I believe that the better the players are, the more inevitable this is. In fact, a good human player will not let an opponent slowly and surely accumulate an advantage, but will "mix it up" in hopes of reversing the tide, which will further tend to shorter games. |
|
Why are arimaa games getting longer then? (I agree with your comment, but it turns out the snowball is not so inevitable until the advantage is big. If camels are still on the table, anything could happen - so people tend not to mix it up until the camels have done their duty - even if they are losing.)
Quote:| Here's my first pass at a new scoring function: Line up all the remaining pieces for both sides. If the strongest piece on each side is the same piece, remove both. Otherwise remove the strongest piece from the player who has it and from the other player remove their strongest and weakest piece. Repeat. Whoever runs out of pieces first loses. (exception - a player with no rabbits who would win under this formula only draws instead) |
|
I quite like this. It's elegant and is approximately correct for arimaa. I'd definitely favour it to the current scoring function.
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Arimaa scoring function discussion
« Reply #10 on: Sep 21st, 2004, 1:45pm » |
Quote Modify
|
I would definitely perfer to have as many games as possible follow a natural ending and avoid having to be determined by score or some other method. Having an unlimited game time would be the best way to go. However due to practical considerations limiting the length of the game either by time or number of moves is required in some situations; especially for tournaments where a schedual needs to be maintained.
In situations where a game limit is requited, It may be a good idea to require that the game limit be chosen so that the game can reach at least 80 moves before the game limit is reached. One can always reduce the time per move and reserve time to comply with this even if the overall game time cannot be increased.
I would not want to have games that reach the limit be considered a draw. Doing so would allow a loop hole to the otherwise 'no mutual draw' match rule. Both players may stall just to let the game limit run out and have it be a draw. The reason why I don't want any possibility of a mutual draw is because I like to think of Arimaa as a sport rather than just a game. In sporting events the comfort and convienence of the players is always sacraficed for the enjoyment of the spectators. I don't mind having natural draws because they are so rare. Witnessing a natural draw would itself be a spectacular thing. So the method we chose should try to reduce the possibility of draws. I would rather error and give the win to the wrong player than allow the possibility of a draw by score.
An advantage of using the total time used by a player for computing the score is that it leaves very little margin for a draw.
But the one thing I don't like about using time is that it leaves a possibility for a player that has a clear material disadvantage, but a significantly higher score (because they made fast moves) a chance to win the game. I think we know for sure now that in Arimaa a significant material advantage can (provided the player still has at least one rabbit) be converted to a win. So I am inclined to perfer a scoring function based on material advantage in cases where the difference in material is significant. However, below some threshold of material advantage I would still perfer using a score based on time.
So maybe the new scoring function could be:
Score = K * sign(C)
where C is the number of rabbits remaining and K is the point value as defined on the match rules page of the pieces remaining after applying Karl's (Fritzlein) piece cancelation method.
http://arimaa.com/arimaa/learn/matchRules.html
If the absolute value of the difference in the players score is more than 6 then these scores are used. Otherwise the players scores are just:
Score = T - U
Where U is the total number of seconds used by the player for all the moves thus far (including current) and T is the total number of seconds allotted for the game; if the game limit was specified as the maximum number of turns than T = 2*(M*G+R) where M, R and G are as specified in the time control section of the match rules page (but in units of seconds).
|
|
IP Logged |
|
|
|
maker
Forum Full Member
bot_tod's maker
Gender:
Posts: 21
|
|
Re: Arimaa scoring function discussion
« Reply #11 on: Sep 23rd, 2004, 11:16pm » |
Quote Modify
|
Omar,
I love the idea of having both a material portion and a time portion of the scoring function for draws, but why don't we combine the two so that a large advantage of material(say a horse advantage, or two of any other noble piece) and a smaller use of time is the maximum value. The minimum would then be large use of time and large loss of material.
HOWEVER, the biggest advantage to scaling the time to fit such a function would be that time and material gains would be considered together, allowing a small loss of material and a minimum use of time to be considered a win, or a slightly larger use of time will a gain of material, depending on the magnitude of each difference.
For example, we could use something like the following:
for players x and y,
(m(x) - m(y)) + k(t(x) - t(y)) = score of player x
(m(y) - m(x)) + k(t(y) - t(x)) = score of player y
where m(player) = material value of player's pieces
and t(player) = used time value for player
and k = some arbitrary constant, decided upon by experience and, perhaps, a general consensus of the experienced players over a certain level of establishment. Just a thought.
maker
|
|
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Arimaa scoring function discussion
« Reply #12 on: Sep 24th, 2004, 3:16pm » |
Quote Modify
|
Upon furher consideration, I don't like any of the proposals so far, including my own two (i.e. imposing a draw and scoring by piece cancellation). Every metric to determine a winner when a time cutoff is reached runs into the same problem: it gives someone an incentive to play unnaturally on the board.
Example: The metric is the current score function. I can't get a rabbit to goal before cutoff (or I would do that) so I wait for the perfect time to suicidally advance rabbits and push my score up temporarily, i.e. not leave time for them to be captured.
Example: The metric is least total time used, and I have used less total time. As the cutoff approaches, I will be more concerned to stay ahead on time than to improve my position on the board.
Example: The metric is piece cancellation, and I am ahead by one rabbit. As the cutoff approaches, I will be eager to stall, avoid exchanges, avoid a fight, etc.
Unfortunately, the only solution proposed so far which avoids a cutoff is sudden-death time controls, which I also don't like. Therefore, I have a new favorite proposal for encouraging the game to be decided naturally on the board: accelerating time controls.
In practice a time cutoff doesn't seem to be an issue unless the time for each move is relatively large, for example allowing only 80 total moves. But in games with a large amount of time per move, there is room to speed up the game without imposing a cutoff.
For example, say you want the game to end in 8 hours for sure. Then clock the game at two minutes per move for the first 60 moves, one minute per move for the next 60 moves, thirty seconds per move for the next 60 moves, etc. In theory this could create the kind of time scramble I don't like, but in practice it won't. If I have an overwhelming position, and I just need more moves to finish it off, then thirty seconds per move will be adequate. And if the game has gone 120 moves without someone attaining an overwhelming advantage, then something very unusual has happened.
Incidentally, this idea also in keeping with Arimaa as a spectator sport. If the game is dragging on, it is probably because one side or the other has dug in their heels and decided to lose slowly-but-surely rather than to come out swinging. In that case speeding up the moves may keep the spectators from getting bored with the slow rate of change on the board.
Just some thoughts...
|
|
IP Logged |
|
|
|
omar
Forum Guru
Arimaa player #2
Gender:
Posts: 1003
|
|
Re: Arimaa scoring function discussion
« Reply #13 on: Sep 26th, 2004, 12:05am » |
Quote Modify
|
I really like this proposal. In fact chess also uses accelerating time controls.
I think it would be virtually impossible for a game to not end naturally after 180 moves especailly when moves were being made at the rate of 30 seconds per move for the last 60 moves.
I suppose we could specify it as a set of time controls. For example:
2/2/100/2/60t | 1/1/100/1/60t | 30s/30s/100/1/60t
would mean 2 minutes per move for the first 60 moves, 1 minute per move for the next 60 and 30 seconds per move for the last 60.
But before going with this I want to see how the 'total time used' method (just by itself) works in practice. I think in practice the two players will maintain fairly equal 'total time used' and I think it will work a lot like an acelerating time control system. But lets try it out for a while and see. I will change the Arimaa flash client in the near future so we can experiment with this.
|
|
IP Logged |
|
|
|
MrBrain
Forum Guru
Arimaa player #344
Gender:
Posts: 148
|
|
Re: Arimaa scoring function discussion
« Reply #14 on: Dec 23rd, 2004, 3:41pm » |
Quote Modify
|
Yes, Omar's suggestion of the player who used the least time winning should be implemented. Eliminate the score, and replace with "Total Time Used". I recommend this be done as soon as possible.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print