Author |
Topic: Board Representation (Read 7867 times) |
|
lightvector
Forum Guru
Arimaa player #2543
Gender: 
Posts: 197
|
 |
Re: Board Representation
« Reply #45 on: Feb 4th, 2008, 8:47am » |
 Quote  Modify
|
I suspect that something in the above calculations is wrong. It should not be possible to get to 122 bits simply by piece combinations.
Take the subcase where there are 32 pieces on the board. Then, the number of unique positions is given by:
64!/32!/8!/8!/2!/2!/2!/2!/2!/2! = 4.63 * 10^42 = 2^141.7
Any lossless encoding, regardless of how well it compresses, must distinguish each of these positions, and therefore must use at least 141.7 bits on average. And this doesn't even account for the cases where there are 31, 30, 29, etc. pieces. Taking into account things like traps, it could be possible to reduce it a bit, but the true optimal value should be close to 140 bits, if not slightly greater.
Edit: This was addressed just prior to my post.
|
| « Last Edit: Feb 4th, 2008, 8:49am by lightvector » |
 IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: Board Representation
« Reply #46 on: Feb 4th, 2008, 10:36am » |
Quote Modify
|
Well spotted, lightvector.
So I'll use 20 bytes = 160 bits to store each position that has already occured during the game.
Now I realize I can use fewer bits when comparing a move with the other moves already generated for a given position, since most of the board is the same within the distance of a move (1 to 4 steps by the same player). Ideally I would like to compare the steps themselves modulo permutations and equivalent paths, but it seems a bit complicated to me for the moment.
I have a simple solution with 58 bits, i.e. 58 bits are enough to code every unique positions 1 move away from a known given position, whatever that fixed position is. Any astute improvement?
|
| « Last Edit: Feb 4th, 2008, 10:38am by clauchau » |
IP Logged |
|
|
|
leo
Forum Guru
Gender:
Posts: 278
|
|
Re: Board Representation
« Reply #47 on: Feb 4th, 2008, 3:06pm » |
Quote Modify
|
on Feb 4th, 2008, 10:36am, clauchau wrote:| I have a simple solution with 58 bits, i.e. 58 bits are enough to code every unique positions 1 move away from a known given position, whatever that fixed position is. Any astute improvement? |
|
I probably miss your point, but moves can be stored in 36 bits:
For each step:
- 6 bits for the index of the origin square
- 2 bits for the direction
- 1 bit telling whether the nearest trap was activated
(6+2+1)*4 = 9*4 = 36
But you are probably looking for a more convenient way to compute board state difference? Please tell us more!
EDIT: One can even use piece index on 5 bits instead of square index, since we start from an already analysed position. Which reduces the data to 32 bits. But I keep feeling that this is not what you're after. Do you search a system that allows generating the resulting full state of the board by a simple operation out of the previous state and the difference?
|
| « Last Edit: Feb 5th, 2008, 1:56am by leo » |
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: Board Representation
« Reply #48 on: Feb 5th, 2008, 6:40am » |
Quote Modify
|
Leo, it's a good idea but I am not looking after a fast and compact way to code moves so that it's simple and fast to compose a board state with the code to get a new board state. For now listing steps is good enough for me for that purpose.
I need a fast equivalence test for comparing the million moves I generate for the same position : If I show you two moves with different steps, can you tell me if they result in getting the same position? If they do, they are equivalent and I ignore one of them.
So I would like a way to recode moves that would yield the same code if the moves are equivalent. Then I would only have to check equality of a few bytes. That's what hash/zobrist codes do on board states, except I also want to be sure the codes are different when the moves are not equivalent.
Your code is a good start, but it doesn't say how to give the same code to equivalent moves with different steps.
One solution is to compare the state boards. We could use the schemes we have designed here to deal with only 160 bits or so.
With the help of lightvector's combinatorial wizardry and your reduction from 6 to 5 bits, I now claim there is a scheme that only need 31 bits. Something at the complication level of 99of9's and lightvector's ideas, but reasonable enough, especially because it's now only 31 bits.
(By the way, the best solution would be to radically avoid any comparison by generating only one move for each set of equivalent moves. The move that represents his equivalence set could be minimal with respect to something. Every time I generate a move, I would only check whether it is minimal among all valid permutations of its steps and other null-effect changes on its paths. Anyway, it's a bit complicated to design right now.)
|
|
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: Board Representation
« Reply #49 on: Feb 5th, 2008, 7:52am » |
Quote Modify
|
on Feb 2nd, 2008, 6:39pm, jdb wrote:| If 64 bit zobrist hashing is used, there is a better chance of being killed by a falling coconut while playing arimaa, than having an incorrect hash collision. |
|
I realize you are right. I calculated that during a million games between a random mover and a piece-count-optimizing mover (57 turns on average and 14600 unique best moves on average for each turn), there is a risk of 1 over 3000 to have a collision if 64 bits are used.
I have been using 32 bit zobrist hashing, that's where I was wrong.
Anyway, I think I'll now use an exact 31-bit coding scheme for the move generator. I'm crazy about being as tight and exact as possible.
|
| « Last Edit: Feb 5th, 2008, 8:41am by clauchau » |
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print