Author |
Topic: Checking for repeated positions (Read 6047 times) |
|
leon_messerschmidt
Forum Senior Member
Arimaa player #6344
Gender: 
Posts: 26
|
 |
Checking for repeated positions
« on: Jul 5th, 2014, 10:12pm » |
 Quote  Modify
|
Up until now I simply ignored the rule for repeating positions. However, in the last two games that my bot played (gameid 307055 and 307051) it made illegal moves and lost a game that wasn't necessarily over yet 
So my question is what is the best way to deal with repeat positions?
I could check and move generation time but that would involve hundreds of millions of additional board comparisons.
Or I could do some jiggery pokery in my transposition table but my gut feel tells me it is a hack which could cause me some pain later on.
The best option seems to check the position for repetition after search/evaluation. But what do I replace it with? Keep track of the second best?
These are just from the top of my head. Anyone want to share some insight?
|
|
 IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: Checking for repeated positions
« Reply #1 on: Jul 6th, 2014, 4:08am » |
Quote Modify
|
I have a hashset which contains all board positions that has occured. And in the search, just before calling the evaluation function, I check if the position is a repetition, if it is, I don't evaluate that position, or make its eval -infinity.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Checking for repeated positions
« Reply #2 on: Jul 6th, 2014, 4:25am » |
Quote Modify
|
First of all - in an arimaa bot, you never want to compare positions, at least not in the performance-critical parts. Always compare the zobrist hash of the position.
As JimmSlimm said, you need to keep the history of all positions (or their hashes) that have occurred in the game, and how many times they occurred. An efficient data structure for searching (like a hash table) is best.
I want to add two things though:
1- This is not only about evaluation, you should check that the moves are legal before recursing on your search as well. What's the point of continuing a search branch where an illegal (repeating) move occured? You probably already have a check for illegal moves in your search (like moves that don't change the board). In that same place in the code you can add the repetition check.
2- It can also be good (if less important) to consider the positions in the search branch so far. For this purpose you shouldn't need any fancy data structure, as the searches are not very deep in Arimaa. A simple array of the hash for each position after a player's move in the current branch should work.
|
| « Last Edit: Jul 6th, 2014, 5:04am by rbarreira » |
IP Logged |
|
|
|
leon_messerschmidt
Forum Senior Member
Arimaa player #6344
Gender:
Posts: 26
|
|
Re: Checking for repeated positions
« Reply #3 on: Jul 6th, 2014, 6:32am » |
Quote Modify
|
Thank you for the replies. It helps a lot.
Aren't there enough hash collisions that I have to do a full comparison when the hashes are equal? Perhaps my hash implementation isn't great but I almost always see a handful of collisions.
I already remove illegal and duplicate moves from my search. But only for the current tree and not previous moves.
It would be easy enough to add a additional hash table that cover previous moves. The only reason I'm resisting it is the additional hash calculations and comparisons, which would run an awful lot.
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: Checking for repeated positions
« Reply #4 on: Jul 6th, 2014, 6:48am » |
Quote Modify
|
As rbarrieira mentioned, check out "zobrist" hashing if you haven't already done so.
Collisions are practically almost non-existant, it's extremely fast to calculate the hash if you do it inside step generation, and it's just a 64bit integer, so the comparisons are kept to a minimum.
Here's a good link that describes this:
https://chessprogramming.wikispaces.com/Zobrist+Hashing
|
|
IP Logged |
|
|
|
leon_messerschmidt
Forum Senior Member
Arimaa player #6344
Gender:
Posts: 26
|
|
Re: Checking for repeated positions
« Reply #5 on: Jul 6th, 2014, 5:40pm » |
Quote Modify
|
I get the feeling I'm missing something really fundamental.
From the chessprogramming site ( https://chessprogramming.wikispaces.com/Zobrist+Hashing#Collisions ) it seems as if there is a collision expected for roughly every 2^32 (roughly 4 billion) entries.
Back of envelope calculation says that at an average branching factor of 15,000 I'd see ~800 collisions for a 12 step deep search. Did I get that right?
Are you saying that you either don't see any collisions or that they're close enough to be treated as the same position?
Edit: at the moment I do seem some collisions in my hash function and I resolve them with a full comparison.
|
| « Last Edit: Jul 6th, 2014, 5:41pm by leon_messerschmidt » |
IP Logged |
|
|
|
dree12
Forum Senior Member
Arimaa player #4082
Gender:
Posts: 27
|
|
Re: Checking for repeated positions
« Reply #6 on: Jul 6th, 2014, 8:40pm » |
Quote Modify
|
on Jul 6th, 2014, 5:40pm, leon_messerschmidt wrote:I get the feeling I'm missing something really fundamental.
From the chessprogramming site ( https://chessprogramming.wikispaces.com/Zobrist+Hashing#Collisions ) it seems as if there is a collision expected for roughly every 2^32 (roughly 4 billion) entries.
Back of envelope calculation says that at an average branching factor of 15,000 I'd see ~800 collisions for a 12 step deep search. Did I get that right?
Are you saying that you either don't see any collisions or that they're close enough to be treated as the same position?
Edit: at the moment I do seem some collisions in my hash function and I resolve them with a full comparison. |
|
With 64-bit keys, a collision in general between any two positions will result every roughly 4 billion positions searched. (This is the birthday problem.) This is the probability of a collision between any two positions, not the probability of a collision with a specific position, which is much smaller.
Because the number of positions that have occurred so far this game is small, the chance of collision with any of those is very small. The 0.0000001% chance of incorrectly rejecting a position, which is very likely to be inconsequential anyways, is not a concern worth sacrificing performance for.
In addition, no modern computer will search 4 billion positions rapidly, unless the evaluation function is a lot faster than it should be  . Even a 3-ply deep search must be heavily pruned.
|
| « Last Edit: Jul 6th, 2014, 8:42pm by dree12 » |
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: Checking for repeated positions
« Reply #7 on: Jul 7th, 2014, 2:49am » |
Quote Modify
|
Quote:| Back of envelope calculation says that at an average branching factor of 15,000 I'd see ~800 collisions for a 12 step deep search. Did I get that right? |
|
I don't know how to calculate it, but looks like you are mistaking single steps for a full move here(That branching factor looks more likely to be for 4 steps, not 1)
|
|
IP Logged |
|
|
|
leon_messerschmidt
Forum Senior Member
Arimaa player #6344
Gender:
Posts: 26
|
|
Re: Checking for repeated positions
« Reply #8 on: Jul 7th, 2014, 3:40am » |
Quote Modify
|
on Jul 7th, 2014, 2:49am, JimmSlimm wrote:
I don't know how to calculate it, but looks like you are mistaking single steps for a full move here(That branching factor looks more likely to be for 4 steps, not 1) |
|
Each move (4 steps) has a branching factor of roughly 15,000. So for 3 moves or 12 steps deep I did 15,000x15,000x15,000
|
|
IP Logged |
|
|
|
JimmSlimm
Forum Guru
Arimaa player #6348
Gender:
Posts: 86
|
|
Re: Checking for repeated positions
« Reply #9 on: Jul 7th, 2014, 4:52am » |
Quote Modify
|
oh d**n
you might be right. I underestimated how much 15'000 ^ 3 really is. Most of those states are not usually really considered though in alpha beta.
So, I think the more realistic number in a normal game of arimaa, for a bot, of "false collisions" is less than 1 on average. It shouldn't be hard to actually measure the number of comparisons made with some counter and calculate the true chance of collision.
double a = 1.0 / (2^32); //chance of collision in single comparison
double b = 1.0 - a; //chance of non collision
double c = b^X; //chance of no collisions in X comparisons
From those numbers and windows calc.exe, I get ~79% chance of there being no collisions after comparing 1billion boards.
I just get the feeling that it really doesn't matter enough to store the actual, full bitboards in addition to the zobrist hash keys
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Checking for repeated positions
« Reply #10 on: Jul 7th, 2014, 12:37pm » |
Quote Modify
|
You're better off worrying about a coconut falling on your head while programming than 64-bit hash collisions, provided your zobrist numbers are pretty random. Especially when it comes to the subject being discussed here - the number of positions in the game history is quite small.
|
|
IP Logged |
|
|
|
clyring
Forum Guru
Arimaa player #6218
Gender: 
Posts: 359
|
|
Re: Checking for repeated positions
« Reply #11 on: Jul 7th, 2014, 2:03pm » |
Quote Modify
|
Even when considering type-1 errors in the entire transposition table (much bigger than the set of positions since the last capture and therefore much more likely to yield an error), this problem is still too small to care about when using a 64-bit hash.
--derivation follows--
There are three numbers to take into account here. Two have already been mentioned: The number of nodes searched (n) and the size of the hash-space. (H) However, we must also consider the number of entries in the transposition table. (T)
First let us consider the number of vacant entries (V) in the transposition table after n nodes have been searched. With each new node searched, the probability that the number of vacant entries will go down is V/T. Assuming both n and T are large enough for the continuum approximation to be reasonable, I take this as a differential equation dV/dn=-V/t, with the initial value V(0)=T. Solving this gives us V(n)=Te^(-n/T).
The probability that adding another node will cause a type-1 error is equal to the number of occupied entries in the transposition table divided by H, or (T-V)/H=[T-Te^(-n/T)]/H. We can again use the continuum approximation to estimate the number of type-1 errors with an integral. Doing so yields the number of errors E={Tn+T²[e^(-n/T)-1]}/H.
--end derivation--
The longest game in this year's CC lasted 15 116 seconds. Assuming all of that time was spent searching or pondering at 10Mnps, we have a reasonable upper bound on n. Plugging H=2^64 and T=2^32 into the formula, we get as our average number of type-1 errors for the whole game...
34. You can decide for yourself whether or not that is enough to warrant concern. 
EDIT: Using the same idea with repetition checking, the hashes that can cause a false match are only as many as the number of plies since the last capture out of all 2^64. Realistically, this number will hardly ever be more than 100 and the probability of a false positive on any given node is less than one in 10^17. There might be occasional, very rare issues with hash comparison in the TT but it should essentially never happen with hash comparison for the purposes of repetition checking.
|
| « Last Edit: Jul 7th, 2014, 2:22pm by clyring » |
IP Logged |
I administer the Endless Endgame Event (EEE). Players welcome!
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: Checking for repeated positions
« Reply #12 on: Jul 7th, 2014, 10:14pm » |
Quote Modify
|
Computing 15000^3 is seriously misleading - almost all of those nodes will never even be visited by an alpha-beta search. What's really relevant is your hashtable size and the speed of your search in nodes per second.
A simple heuristic not requiring you to solve any equations is that you need on the order of 2^n pairwise comparisons to find collisions with a good n-bit hash. So if as in the birthday paradox you have 2^32 hashes with each one compared against each other one, than that's about 2^64 pairwise comparisons - so 2^32 is where you start getting significant probability to find at least one collision against a 64 bit hash. Zobrist hashing isn't perfect, but it's quite good and in practice sees to come close to the bound that a true "random" hash would give. So...
For repetition checking, you aren't comparing each position against 2^32 others. You're comparing each position against a few hundred others - less than 2^10, so you need close to 2^54 nodes searched to worry about collisions. Not going to happen.
For transposition tables, you're comparing each position against N others where N is the size of your table. Probably N is close to but not quite as large as 2^32 unless you have a lot of RAM. If N is, say, 2^27 ~= 128 million, then you expect a collision once you start getting close to 2^37 ~= 128 billion nodes searched. Based on how fast your own search is, you can determine how long that would take and how much you care.
Also consider this study. It turns out that a chess search can actually tolerate surprisingly high error rates. The probability that any single random error actually affects the root node is small. Similar should be true for Arimaa.
https://www.cis.uab.edu/hyatt/collisions.html
So use zobrist hashing with 64 bits and don't worry about it, unless you're really paranoid, in which case 96 bits should be plenty.
|
| « Last Edit: Jul 7th, 2014, 10:18pm by lightvector » |
IP Logged |
|
|
|
leon_messerschmidt
Forum Senior Member
Arimaa player #6344
Gender:
Posts: 26
|
|
Re: Checking for repeated positions
« Reply #13 on: Jul 8th, 2014, 3:30am » |
Quote Modify
|
Thanks lightvector that is a really good article. Form the article:
Quote:
The numbers are surprising, but they clearly show that errors do not influence the search nearly as much as has always been suspected. Even with programs searching at one million nodes per second and beyond, the errors do not wreck the search and cause substantial problems. For example, in the tactical positions, there are just a few key positions that influence the final result. In a tree search space of 120 million nodes, a signature collision on one of such a small set of critical nodes is very unlikely. One point this certainly underlines is that past claims that programs search a large number of useless chess positions is clearly right on target. One can almost change scores at will and still have little adverse effect on the quality of the moves produced. |
|
I will probably stop worrying about collisions altogether. The probability of a 64bit collision is outlandishly small. And even then the effect on the quality of play is minimal.
|
|
IP Logged |
|
|
|
rbarreira
Forum Guru
Arimaa player #1621
Gender:
Posts: 605
|
|
Re: Checking for repeated positions
« Reply #14 on: Jul 8th, 2014, 5:02am » |
Quote Modify
|
on Jul 7th, 2014, 10:14pm, lightvector wrote:
So use zobrist hashing with 64 bits and don't worry about it, unless you're really paranoid, in which case 96 bits should be plenty. |
|
And then you'd probably be hurting yourself with the paranoia, given the extra overhead of maintaining and comparing 96 bit hashes, and the lost RAM/cache space from storing bigger hashes in the TT (both of which will have an easily measurable impact on your bot, unlike the impact of the collisions).
|
| « Last Edit: Jul 8th, 2014, 5:19am by rbarreira » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print