Arimaa Forum - Print Page


    
      
        Arimaa Forum
        (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
      

        Arimaa >> Bot Development >> Handling repetition
        
(Message started by: leo on Apr 26^th, 2006, 12:53pm)

Title: Handling repetition
Post by leo on Apr 26^th, 2006, 12:53pm

As I go on trying to code my goal-oriented bot, I'm bugged wondering how I'll handle repetition. The internal validity checker sure detects repetition, but how will I make the bot "understand" it so it behaves sensibly. It's simply not enough to have it find that some moves are illegal although they follow the basic rules. That's something for a global cognitive module, but it strongly bumps against all other modules. Not revealing your secrets, did you come up with original solutions or do you just prune the repeating branches without further consideration?

Title: Re: Handling repetition
Post by ddyer on Jan 18^th, 2007, 9:17pm

Don't make the repetition move illegal, allow it and score it as a loss (or as a draw, whatever is appropriate). Your lookahead will do the right thing, provided you are careful to recognise that it is also a "game over" condition and don't search deeper.

Title: Re: Handling repetition
Post by IdahoEv on Jan 18^th, 2007, 11:57pm

This is a question close to my heart, since Zombie just lost a championship game because of repetition. I agree with ddyer; evaluate a repetitive move the same way you would any other loss.

However, this begs another question that's been bugging me: how to detect third-time repetition? In the standard bot methodology, your bot (a getMove program) is invoked anew for each move. No state is persisted from previous moves unless you explicitly write a file. You get the gamestate, but that contains only a list of moves ... not a list of board states that could be consumed.

Options I see ... all of which should work but none of which are as easy as I'd like them to be:

1) At the beginning of the turn computation, take the move list provided by the gamestate and recreate all the board states that have existed. Store the hash of each one along with the number of times it has previously existed. Your evaluator then compares the hash of the current board with that hashmap, and if the state it is considering has occurred twice already, score that as a loss.

2) Maintain a file log containing a hash map similar to the above, with the game id# as part of the filename so your next invocation can open the appropriate log. Write to it once at the beginning of your run (to add the state your opponent just created) and again at the end of your run (to add the state you've just created with your chosen move).

Title: Re: Handling repetition
Post by jdb on Jan 19^th, 2007, 12:25am

Clueless uses option one. It is only necessary to check for repetition on the first move of the search. Deeper in the search, the repetitions are not important. This takes negligible time.

Title: Re: Handling repetition
Post by 99of9 on Jan 19^th, 2007, 1:47am

on 01/19/07 at 00:25:52, jdb wrote:

Deeper in the search, the repetitions are not important.

They would be important for your endgame test problems. Do you handle repetition correctly for them?

Title: Re: Handling repetition
Post by jdb on Jan 19^th, 2007, 8:59am

on 01/19/07 at 01:47:25, 99of9 wrote:

They would be important for your endgame test problems. Do you handle repetition correctly for them?

You are right, they are important for the endgame test problems, since we are trying to find the "perfect" line of play. In this case the search checks for repetition losses at every node of the search.

Title: Re: Handling repetition
Post by ddyer on Jan 19^th, 2007, 11:14am

detect repetition by calculating a zobrist hash for
each position. It's very cheap and easy. The
same technique is also handy for transposition
tables in search.
http://weblogs.asp.net/justin_rogers/archive/2004/04/06/108601.aspx

Title: Re: Handling repetition
Post by ddyer on Jan 19^th, 2007, 11:32am

on 01/19/07 at 00:25:52, jdb wrote:

Clueless uses option one. It is only necessary to check for repetition on the first move of the search. Deeper in the search, the repetitions are not important. This takes negligible time.

This line of thinking is Ok if you're just trying to keep
your play legal, but ANYTHING you ignore at lower levels
of a search will eventually cause you grief. For example,
if you ignore repetition, a deep branch might look very
favorable, and so be chosen over an almost-equally
favorable branch that does not include repetition.

Title: Re: Handling repetition
Post by IdahoEv on Jan 19^th, 2007, 1:23pm

ddyer -- you're new here (by your userid anyhow), but you seem extremely knowledgeable. Care to share a bit about your background?

Title: Re: Handling repetition
Post by IdahoEv on Jan 19^th, 2007, 2:02pm

on 01/19/07 at 11:32:58, ddyer wrote:

This would be pretty easy to implement, anyhow, by simply pre-evaluating all positions that have been repeated twice already as losses and pre-loading those into your transposition table before you begin the search. Then they will be detected as losses at any level regardless.

I see a couple of problems, though:
1) This won't catch positions that have been repeated zero or one times at the beginning of a search but then appear more than once in a particular branch, causing them to be losses when they appear the second or third time, but not the first. The only solution I can see to this problem is that the "position" would need to include not just the board state but also the number of times it has repeated, historically. This would then dramatically reduce the effectiveness of the transposition table and amplify the number of different states to be stored. (since detecting repeated states and evaluating them the same is kind of the point of the table...) Maybe you could construct a hash that would return the same value for the 1st and 2nd repeat of a position but not the third?

2) AFAIK all known bots evaluate every step rather than every turn, and repeated states do not cause a loss if they occur mid-turn. This means we have to add another flag to the position being evaluated and hashed: whether or not it is a mid- or end-turn state.

Title: Re: Handling repetition
Post by ddyer on Jan 19^th, 2007, 4:02pm

on 01/19/07 at 13:23:55, IdahoEv wrote:

ddyer -- you're new here (by your userid anyhow), but you seem extremely knowledgeable. Care to share a bit about your background?

I've been writing game programs for more than 30 years, including a long spell when I worked on Go. Lately I've been writing games and AIs for them which can be experienced at Boardspace.net. My interest is not really in making the best possible game playing programs, but in making AIs that are good enough to get real players hooked into the games.

Title: Re: Handling repetition
Post by ddyer on Jan 19^th, 2007, 4:15pm

Worring about preloading your transposition table
in the most effecient way is a waste of effort and
introduces unnecessary complexity. The number
of fully evaluated positions you could have saved
from previous searches is trivial compared to the
number of nodes about to be searched.

Title: Re: Handling repetition
Post by leo on Dec 7^th, 2007, 12:00am

Thanks everybody for your answers. At the time you wrote them I was off bot development and missed them.

Making repetition a lost rather than an illegal move is indeed better, but it unfortunately doesn't help a learning bot understand why it is so.

Repetition, like board setup and advanced strategy, is at a superior level of abstraction. Humans can even use repetition purposefully in order to hinder their opponent's future move, which is high-flight planning and tricky to implement in a bot (although classical bots can take advantage of it in a haphazard way).

For an AI to watch and use repetition "consciously", it needs a specialized module, something like a metagame brain. Fascinating...