Author |
Topic: Fundamentally Identical Board Positions (Read 1421 times) |
|
Kushiel
Forum Full Member
Arimaa player #9913
Gender: 
Posts: 16
|
 |
Fundamentally Identical Board Positions
« on: Sep 29th, 2014, 3:25pm » |
 Quote  Modify
|
Quick Note: I think the word I'm looking for is isomorphism, but even the wikipedia page confused me so I figured I was better off not using the word.
In arimaa, if both players are missing camels, you could replace any elephants on the board with camels, and it would have no impact on the game.
If gold has no cats or dogs remaining, and silver has only 1 cat remaining, you could replace silver's cat with a dog without affecting the game at all.
Zobrist hashes are used to prevent your bot from wasting time re-evaluating the same positions. I'm wondering if modifying the way we generate zobrist hashes to prevent wasting time re-evaluating fundamentally identical positions would save more time (because less re-evaluation) or waste more time (because more complicated hashing).
I'm guessing that the slowdown in hashing that my naive approach will cause will far outweigh the benefit of the reduced re-evaluation, but my intuition could be wrong.
I was wondering if anyone else had thought about this before and/or tried to implement it. Especially if someone has any neat tricks (bitboard magic still confuses me) for generating identical hashes for fundamentally identical boards, I'd love to hear it.
|
|
 IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: Fundamentally Identical Board Positions
« Reply #1 on: Sep 29th, 2014, 6:45pm » |
Quote Modify
|
That's a neat idea, and probably is an effective way to compress things like N-piece tablebases. I wouldn't be surprised if jdb's tablebases exploit this fact.
But there's a pretty big problem with this for general search, which is that given the search depths reachable by bots, the proportion of equivalent positions with nominally different material in the same search tree will be about zero for almost every typical game position. Search trees usually only go 2-4 moves deep in current bots, and the proportion of sequences only 2-4 moves long that lead into an alternate-material transposition will obviously be very tiny.
It's the same thing as in Chess, where if there are no castling and enpassant rights, two mirror-symmetric positions are equivalent. But you don't bother making your zobrist hash understand this. Except for the very end of the game with almost no pieces on the board, in the typical position, what sane sequences of play could possibly ever result in the board reaching two different mirrored states?
|
|
IP Logged |
|
|
|
Kushiel
Forum Full Member
Arimaa player #9913
Gender:
Posts: 16
|
|
Re: Fundamentally Identical Board Positions
« Reply #2 on: Sep 29th, 2014, 9:28pm » |
Quote Modify
|
I think I figured out a way to make any impact it has on the time wasted during searches negligible.
After every capture (very rare): check to see if any pieces remain which are the same strength as the captured piece. If none remain, downgrade every stronger piece by 1 rank.
For example, silver dog gets captured. I check and see that no gold or silver dogs remain in the game, so I downgrade all horses to dogs, then all camels to horses, then all elephants to camels. I then continue searching and/or playing the game.
You keep track of any substitutions you've made seperately so you can make the game controller happy by trying to move your camel from f7 rather than asking to move a horse from f7, but you only have to convert horse to camel once when telling the controller your bestmove, and camel to horse once when it passes you a makemove.
Then, in your internal representation, no fundamentally identical positions will ever occur that aren't actually identical.
This has benefits not only for zobrist hashing (which would likely be minimal), but also for any heuristics which factor in material strength. If silver evaluates 2 boards A and B and finds:
A: Better positionally, 1 cat remaining, no opponents cats or dogs
B: Slightly worse Positionally, 1 dog remaining, no opponents cats or dogs
Depending on how you weight cats/dogs, you might choose position B because it's "stronger in material" when in reality it has the exact same material strength as A.
If your internal representation always downgrades stronger pieces when intermediate tiers cease to exist, then in your internal representation, silver will have 1 cat in each position (and all horses will be dogs, all camels horses, all elephants camels).
The piece downgrade on capture method will help your bot view fundamentally equivalent material (and positions) as equivalent wherever you try to compare 2 boards.
|
|
IP Logged |
|
|
|
Kushiel
Forum Full Member
Arimaa player #9913
Gender:
Posts: 16
|
|
Re: Fundamentally Identical Board Positions
« Reply #3 on: Sep 30th, 2014, 6:41am » |
Quote Modify
|
Extending the previous idea (downgrading stronger pieces once no pieces exist which are immediately below them in strength), you could also flip the board if the gold elephant ever crosses the midline, ensuring that right to left symmetry never causes your bot to view 2 fundamentally identical positions as different.
I'll have to think more about that one though, because you need to know and care about repeating the same position too many times in Arimaa. It's not a problem if you only modify the board after a capture, since at that point you can never repeat any previously hit position anyways. It is a problem if you're flipping it horizontally when gold's elephant moves though.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print