Author |
Topic: Board Representation (Read 7863 times) |
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender: 
Posts: 145
|
 |
Re: Board Representation
« Reply #30 on: Feb 2nd, 2008, 9:58am » |
 Quote  Modify
|
I'm going to store and compare lossless representations of positions instead of colliding hash values, so that
1) checking for games lost by repetition is not done wrong, and
2) I'm sure that the simple bots I have playing over a million games don't ever overlook moves by wrongly believing they've already been evaluated.
How few bits as possible would you need to code every possible Arimaa position (without needing too much time to code it)? I've a simple solution that goes down to using 153 bits (or 154 if I also need the active side).
|
|
 IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Board Representation
« Reply #31 on: Feb 2nd, 2008, 6:31pm » |
Quote Modify
|
OK, you got me thinking about it for a few minutes, and I couldn't beat your answer. I did a Huffman Code on the pieces, listed in order of the squares. Bit one is empty/occupied. Bit two is Silver/Gold. Bit 3 is rabbit/piece. Bit 4 is minor/major piece. Etc. The full code is
0 empty
100 silver rabbit
10100 silver cat
10101 silver dog
10110 silver horse
101110 silver camel
101111 silver elephant
110 gold rabbit
11100 gold cat
11101 gold dog
11110 gold horse
111110 gold camel
111111 gold elephant
My description length when all pieces are on the board is 32*1 + 16*3 + 12*5 + 4*6 = 164 bits, plus one for side to move. Of course it is shorter after captures, but it's eleven bits longer than yours worst case. 
Now you explain your 153-bit solution. It had better be more complicated than mine! 
|
|
IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Board Representation
« Reply #32 on: Feb 2nd, 2008, 6:39pm » |
Quote Modify
|
on Feb 2nd, 2008, 9:58am, clauchau wrote:I'm going to store and compare lossless representations of positions instead of colliding hash values, so that
1) checking for games lost by repetition is not done wrong, and
2) I'm sure that the simple bots I have playing over a million games don't ever overlook moves by wrongly believing they've already been evaluated.
How few bits as possible would you need to code every possible Arimaa position (without needing too much time to code it)? I've a simple solution that goes down to using 153 bits (or 154 if I also need the active side). |
|
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.
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: Board Representation
« Reply #33 on: Feb 3rd, 2008, 10:34am » |
Quote Modify
|
I don't know whether this is considered easy to code, but I have a practical way to achieve 146 bits (147 with side to move, 149 if you want to specify 1-4 steps as well).
First, compute a unique index for each possible combination of squares occupied on the board. There are 64C32 + 64C31 + ... +64C0 possible combinations for occupancy (ignoring traps, etc).
Adding all this up and taking the log base 2, we find we can store this index in 64 bits.
To represent what pieces are on the board, we can write a string such as RcEreMrrRrHDrDRC, specifying sequentially the pieces that are in each subsequent occupied position. Each string will be exactly 32 characters long, and will contain exactly 8 r's, 8 R's, 2 c's, 2 C's, and so on. If there are fewer than 32 occupied positions on the board, then we simply fill in the rest of the string past that point however we wish (this is wasteful, so there is still room to shave off a few more bits without resorting to Arimaa-specific properties like traps or the fact that there can never be more than 4 rabbits that have reached the goal line). We then compute a unique index for each possible 32 character string. The total number of possibilities is 32!/8!/8!/2!/2!/2!/2!/2!/2!, and taking the log base 2, we find we can store this index in 82 bits. This gives a grand total of 146 bits.
I hope I didn't get anything wrong above.
I will post how to calculate the indices shortly. It's not actually that bad.
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: Board Representation
« Reply #34 on: Feb 3rd, 2008, 11:14am » |
Quote Modify
|
How do we compute the required indices? Here is one way (there may be better ways). This requires 64 bit unsigned integer math.
To compute the index for occupied board positions, first count how many there are. We have a list matching number of positions to the desired combination.
32 Positions: 64C32
31 Positions: 64C31
30 Positions: 64C30
...
To get an index, we sum all the values of the previous, then add the specific index for the combination we want. For example there are 30 occupied positions, then we want the case 64C30. So our index is 64C32 + 64C31 + (the unique index for combinations of 30 elements from 64).
--------
To find the index for combinations of C squares from N, we number the board squares 0-N. Then we consider the smallest square chosen, x. Removing that square, we recursively have a choice of C-1 squares out of the remaining N-x-1 subsequent squares.
Again, to get an index in the case we want, we sum all the values of the previous, then recursively add the unique index for the combination we want. Say in our example x = 3, C=30, N = 64. Then, our list of the possible cases looks like:
x = 0: 63C29
x = 1: 62C29
x = 2: 61C29
x = 3: 60C29
...
and our index is 63C29+62C29+61C29 +(the unique index for a choice 29 squares from 60).
Recursively proceed until we have gone through each occupied square (recursively reaching a case of the form xC0). This gives us our final unique index.
-------
If we want to go from the index back to the position, we simply following the same procedure, but make the choice at each step that would give us the index we want. For example, in the initial counting of board squares, if our index X is such that 64C32+64C31...+64C10 <= X < 64C32+64C31...+64C10+64C9, then we know that there are 9 squares occupied, and to find out which squares, we continue into the case 64C9.
All of this can be made relatively fast by precomputing all the required values xCy up to 64C32 and storing them in an array.
Calculating the index for the piece string can be done very similarly (but will require up to 82 bit math).
Somewhat complicated, and probably a pain to code, but definitely feasible. Of course, the extra effort required to implement something like this is probably not worth the tiny reduction in size, but it is certainly fun to see how it can be done.
My explanation is probably overly confusing, but I hope it is good enough.
|
| « Last Edit: Feb 3rd, 2008, 11:24am by lightvector » |
IP Logged |
|
|
|
Janzert
Forum Guru
Arimaa player #247
Gender:
Posts: 1016
|
|
Re: Board Representation
« Reply #35 on: Feb 3rd, 2008, 11:50am » |
Quote Modify
|
Just a note since it was mentioned storing how many steps are left. If you have a mid-move position then you also need to know the type of the last piece to move and the square it moved from. Otherwise you can't correctly deal with pushes and pulls.
Janzert
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Board Representation
« Reply #36 on: Feb 3rd, 2008, 5:51pm » |
Quote Modify
|
I can get 160 bits quite easily (for the board configuration, not the move status).
Lightvector, you've given us a good bound to shoot for! Your first 64 bits are overly complex though... you can fully indicate occupancy by storing a 64 bit checkerboard with 1 for occupied and 0 for unoccupied, just as Fritz suggested for his first bit. No need to calculate anything.
|
| « Last Edit: Feb 3rd, 2008, 5:52pm by 99of9 » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Board Representation
« Reply #37 on: Feb 3rd, 2008, 8:02pm » |
Quote Modify
|
Using a slightly complex, but human-decodeable scheme, I can get 156. I'll also be fascinated to see the 153!
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: Board Representation
« Reply #38 on: Feb 3rd, 2008, 11:33pm » |
Quote Modify
|
on Feb 3rd, 2008, 11:50am, Janzert wrote:Just a note since it was mentioned storing how many steps are left. If you have a mid-move position then you also need to know the type of the last piece to move and the square it moved from. Otherwise you can't correctly deal with pushes and pulls.
Janzert |
|
It might depend on your search algorithm though. In my bot, I generate and search pushpulls first as 2-step moves, and never end in an intermediate position. But yes, if you have to store that info, it will increase the size.
on Feb 3rd, 2008, 5:51pm, 99of9 wrote:I can get 160 bits quite easily (for the board configuration, not the move status).
Lightvector, you've given us a good bound to shoot for! Your first 64 bits are overly complex though... you can fully indicate occupancy by storing a 64 bit checkerboard with 1 for occupied and 0 for unoccupied, just as Fritz suggested for his first bit. No need to calculate anything. |
|
Haha! I suppose I should have check for easier ways first. =).
|
|
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: Board Representation
« Reply #39 on: Feb 4th, 2008, 6:19am » |
Quote Modify
|
Lightvector, I'm delighted to see your optimal solution for the piece string. Fascinating.
Poor me, I miscalculated my solution (while trying to sleep and the next day making my groceries  ). I need 155 bits indeed, not 153. Forgive me. Here is what I had in mind.
The idea is to start with the 164-bits solution and simply drop 9 redundant bits!
For each board square, one bit tells whether it is empty or occupied => 64 bits.
For each occupied square except the possible 32nd one, one bit tells whether it is occupied by Gold or by Silver => 31 bits. If there are 32 occupied squares, it means 16 are by Gold and 16 are by Silver, so you always know the 32nd color is the one missing from the 31 first squares.
For each square occupied by Gold except the possible 16th one, one bit tells whether it is by rabbit or not => 15 bits. If there are 16 squares occupied by Gold, it means 8 are by rabbits and 8 are by non-rabbits, so you always know about the 16th according to how many rabbits are already counted for in the 15 first squares occupied by Gold.
For each square occupied by a non-rabbit Gold piece except the possible 8th, two bits tell whether it is 00 = by a cat, 01 = by a dog, 10 = by a horse, or 11 = by a camel or an elephant, not distinguishing camels from elephants => 14 bits. Same reasoning as above in case there are 8 non-rabbit Gold pieces - there should be two 00, two 01, two 10 and two 11, so the 8th one is the one missing.
For the first square occupied by a Gold camel or elephant, one bit tells whether it is a camel or an elephant => 1 bit. If there are two such squares, the 2nd is always of the other species.
Do the same for Silver, and you need 64+31+(15+14+1)x2 = 155 bits.
99of9, what's your own solution to get to 160?
|
| « Last Edit: Feb 4th, 2008, 6:25am by clauchau » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Board Representation
« Reply #40 on: Feb 4th, 2008, 6:41am » |
Quote Modify
|
Here is my 160 bit solution:
64 occupied/not
32 gold/not (as clauchau correctly notes, I should only use 31)
For each colour, we now have up to 16 squares. A location amongst 16 squares can be denoted with 4 bits. So listing the locations for all of the 8 majour pieces takes 8*4 bits. Times 2 for the two colours = 64.
The rest of the occupied squares (of known colour) must be rabbits.
64+32+64 = 160 (or 159 if you use clauchau's trick)
|
|
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Board Representation
« Reply #41 on: Feb 4th, 2008, 6:43am » |
Quote Modify
|
Using clauchau's trick, my complicated method comes down to 153!
64 occupied / not
31 gold / not
From now on everything must be doubled for both colours:
15 rabbit / not
Now we have 8 squares on which our majour pieces must be placed. An address amongst 8 requires 3 bits. Specify the addresses of the elephants and camels: 3 bits * 2 pieces = 6.
Now we have 6 squares to place 2C 2D and 2H. Divide these 6 into two sets of 3.
Are both cats in the same set of 3? 1 bit.
Are both dogs in the same set of 3? 1 bit.
a) If both answers were YES:
Are cats both in first set? 1 bit. The answer to this question tells us whether we have {c,c,h}{d,d,h} or {d,d,h}{c,c,h}. Either way, we just need to find the horse in each set of 3.
A location amongst 3 spots requires 2 bits. Do this for both sets of 3. 4 bits.
(total required under option a is 5 bits)
b) If both answers were NO:
Now we know we have {c,d,h} in both sets, which we have to sort out. Do the following for each set:
Specify the location of the cat. 2 bits.
Now, out of the D/H, is the D first? 1 bit.
(total required under option b is 6 bits)
c) If one answer was YES, and the other NO (wlog cats were the YES):
We have a similar situation to answer (a) except dogs have been switched for horses. We know we either have:
{c,c,d}{h,h,d} or {h,h,d}{c,c,d}
(figuring this out requires 5 bits, similar to answer (a)).
So, at worst, we use:
64 + 31 + (15 + 6 + 2 + 6) * 2 = 153
|
| « Last Edit: Feb 4th, 2008, 7:04am by 99of9 » |
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: Board Representation
« Reply #42 on: Feb 4th, 2008, 7:13am » |
Quote Modify
|
Edit : Ouch, I used ruby to compute it, and forgot ^ is xor, not exponentiation, which is **. So what I describe below doesn't miraculously use only 122 bits but 149 
Ah yes, poor poor me, I had really managed 153 bits. Instead of 14 bits for distinguishing Gold cats from dogs from horses from camel-elephant, first use 7 to distinguish cats-dogs from horses-camel-elephant (the possible 8th is the missing one), then 3 to distinguish cats from dogs (the possible 4th is the missing one) and 3 to distinguish horses from camel-elephant.
Combining lightvector arithmetics of combinations with this removal of 11 bits, and packing it all together we can get down to 149 bits :
There are A = 64C32 + 64C31 + ... + 64C0 = 10139684107326071075 ways to choose 0 to 32 occupied squares among 64.
There are B = 31C16 + 31C15 + ... + 31C0 = 1374282019 ways to choose 0 to 16 Gold pieces among 31.
There are C = 15C8 + 15C7 + ... + 15C0 = 22816 ways to choose 0 to 8 rabbits among 15 Gold pieces.
There are D = 7C4 + 7C3 + ... + 7C0 = 99 ways to choose 0 to 4 cats-dogs among 7 non-rabbit Gold pieces.
There are E = 3C2 + 3C1 + 3C0 = 7 ways to choose 0 to 2 cats among 3 Gold cats or dogs and 0 to 2 horses among 3 Gold horses or elephant or camel.
There are F = 2 ways to choose 0 to 1 camel among 1 Gold camel or elephant.
So we only need G = A*B*(C*D*E*E*F)^2 = 682813102718264674657879442836350524710195200 ~ 2^148.94 ~ 10^44.83
The drawback is you need arithmetics on 149-bits integers though.
|
| « Last Edit: Feb 4th, 2008, 8:21am by clauchau » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
Gender:
Posts: 1413
|
|
Re: Board Representation
« Reply #43 on: Feb 4th, 2008, 7:35am » |
Quote Modify
|
Nice! When computers go to 128 bits, someone might start trying this...
|
|
IP Logged |
|
|
|
clauchau
Forum Guru
bot Quantum Leapfrog's father
Gender:
Posts: 145
|
|
Re: Board Representation
« Reply #44 on: Feb 4th, 2008, 8:26am » |
Quote Modify
|
Sorry 99of9, I was highly dreaming for a while there, it seems there really are more than 2^128 different positions !
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print