Author |
Topic: Handling repetition (Read 1324 times) |
|
leo
Forum Guru
Gender: 
Posts: 278
|
 |
Handling repetition
« on: Apr 26th, 2006, 12:53pm » |
 Quote  Modify
|
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?
|
|
 IP Logged |
|
|
|
ddyer
Forum Guru
Gender:
Posts: 66
|
|
Re: Handling repetition
« Reply #1 on: Jan 18th, 2007, 9:17pm » |
Quote Modify
|
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.
|
|
IP Logged |
visit my game site: http://www.boardspace.net/
free online abstract strategy games
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Handling repetition
« Reply #2 on: Jan 18th, 2007, 11:57pm » |
Quote Modify
|
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).
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Handling repetition
« Reply #3 on: Jan 19th, 2007, 12:25am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Handling repetition
« Reply #4 on: Jan 19th, 2007, 1:47am » |
Quote Modify
|
on Jan 19th, 2007, 12:25am, 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?
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Handling repetition
« Reply #5 on: Jan 19th, 2007, 8:59am » |
Quote Modify
|
on Jan 19th, 2007, 1:47am, 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.
|
|
IP Logged |
|
|
|
ddyer
Forum Guru
Gender:
Posts: 66
|
|
Re: Handling repetition
« Reply #7 on: Jan 19th, 2007, 11:32am » |
Quote Modify
|
on Jan 19th, 2007, 12:25am, 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.
|
|
IP Logged |
visit my game site: http://www.boardspace.net/
free online abstract strategy games
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Handling repetition
« Reply #8 on: Jan 19th, 2007, 1:23pm » |
Quote Modify
|
ddyer -- you're new here (by your userid anyhow), but you seem extremely knowledgeable. Care to share a bit about your background?
|
|
IP Logged |
|
|
|
IdahoEv
Forum Guru
Arimaa player #1753
Gender:
Posts: 405
|
|
Re: Handling repetition
« Reply #9 on: Jan 19th, 2007, 2:02pm » |
Quote Modify
|
on Jan 19th, 2007, 11:32am, ddyer wrote: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. |
|
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.
|
|
IP Logged |
|
|
|
ddyer
Forum Guru
Gender:
Posts: 66
|
|
Re: Handling repetition
« Reply #10 on: Jan 19th, 2007, 4:02pm » |
Quote Modify
|
on Jan 19th, 2007, 1:23pm, 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.
|
|
IP Logged |
visit my game site: http://www.boardspace.net/
free online abstract strategy games
|
|
|
ddyer
Forum Guru
Gender:
Posts: 66
|
|
Re: Handling repetition
« Reply #11 on: Jan 19th, 2007, 4:15pm » |
Quote Modify
|
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.
|
|
IP Logged |
visit my game site: http://www.boardspace.net/
free online abstract strategy games
|
|
|
leo
Forum Guru
Gender:
Posts: 278
|
|
Re: Handling repetition
« Reply #12 on: Dec 7th, 2007, 12:00am » |
Quote Modify
|
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...
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print