Jump to content

  • Log In with Google      Sign In   
  • Create Account


Hashing connect -4 board (for Transposition table)..need some help :)


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
80 replies to this topic

#1 patishi   Members   -  Reputation: 212

Like
0Likes
Like

Posted 25 June 2013 - 08:54 PM

Hi all.  I am sorry for the post flood i am doing here lately smile.png      today's topic:  Transposition table for my connect 4 game.  
I am programming in java and when looking for a scheme to hash a board (array of 42 ints: 1 for white, 2 for black and 0 for empty) i first tried

to put it in a long number..  but java won't let me to have a long number with 42 digits (even the LONG type).    It says that it is: out of range (??)  

sooo.. I am now doing it another way:  i am "casting"  this 42 int array into a string instead of a number,  that means everytime i want to hash a board,  i pass through all the array indexes  and if the current index in the array is 1 , i concatenate "1" to the string...and so on until i finish.  
In the end i get something like this:  "12200011"...  etc'.      and after i done with this operation ,i take this string and using the java Hash()  function, i am giving it a hash number.       this hash number is the key code for the board in my TT.    
what do you think about this scheme?    I read about zobrist keys but i just couldn't understand how exactly i should parse a board of 42 ints (1,2 or 0)  into a number of 42 digits / charachters / bits...  whatever.      
I wish i could just do   12200001 etc',  than it would be simple and unique, but i cant  

I know that working with strings like i do takes a lot of time,  and i am also not sure if the hahing is good / unique.     I will be very very glad if any of you can help me thourgh it (cause i am a total noob smile.png  )     and guide me on what is the best way to hash a board position.   

Thanks in advance!   


Edited by patishi, 25 June 2013 - 09:17 PM.


Sponsor:

#2 AfroFire   Members   -  Reputation: 392

Like
1Likes
Like

Posted 25 June 2013 - 09:53 PM

"java won't let me to have a long number with 42 digits (even the LONG type).  "

 

A long is at most 8 bytes -- that's 64 bits. That means you can have 64 zeros or ones. However, you've stated that you need 0, 1 and 2. So we need a base 3 system. The problem with this is you'd need to take up 2 bits a piece to store 0, 1, or 2. So now you can only cram, at most, 32 bits in to a long type. The long just doesn't have enough memory to store the entire board.

 

There are many different solutions: For example: you could use a multidimensional array to simply store bytes. byte[][] ?

 

If you want a rather 'tricksy' solution, you could do what I once did in school:

Create a table that holds Player 1's pieces (0 = no piece, and 1 is a piece), and create another table for Player 2's pieces (0 = no piece, and 1 is a piece). Since we're now back to using base 2 system, we can hold all of player 1's pieces in a long, and all of player 2's pieces in a long.

 

THEN if we want to see if we have a valid move, we can go ahead and make the move on the respective player's long and simply do a logical AND compare - if you have two values overlapping the logical AND will return true (at which point, you need to undo the move so that the board is in a valid state).

 

If you just want to see where the next available space is on a board, then you will logically OR/XOR the two values and anywhere there is a zero is an empty space. I'll leave the finer shifting details to you (or if you make an effort I can lend a hand).

 

If you want to see if a player has won after their move, if you are feeling super duper excited, you could probably create a dictionary of winning states for the board and logically AND your board against these states (you could systematically remove boards that are definitely not going to happen in a game as well, so that as the game goes on, the number of boards checked for victory goes down).

 

As I said, there are lots of ways to do what you're asking - this is another one :D

 

Additionally, if you are not too comfortable with performing bitwise operations -- look in to Java's BitSet.


AfroFire | Brin"The only thing that interferes with my learning is my education."-Albert Einstein

#3 patishi   Members   -  Reputation: 212

Like
0Likes
Like

Posted 25 June 2013 - 10:17 PM

thanks you for the answer, and although the bits operation stuff is a bit vague to me right now, i am trying to unserstand the first part of your solution.    

So basically i need to do two bytes arrays (or one two dimentional) in length of 42 (for all the board squares)  and each one of them will represent the pieces of one of the two players.(0 for no piece and 1 for a piece)

so for example, the byte array for the first player can look like this?   000000000000000000000000000000000000001000      here the first player just played his first move in the middle square at the buttom of the board.     so now every board representation ,instead of  one array of 42 int's (0,1 or 2) will be those two Bytes arrays?    

and sorry for my ignorance,  but even if i have those two bytes array for the players' pieces,  how can i transpose each one of them to a Long type number?     
and after i do that,  how should i hash those two long numbers into one hash initeger so i can store in my TT?     by the way,thanks for the java's Bitset tip, i think i will be using that :)



 


Edited by patishi, 25 June 2013 - 11:00 PM.


#4 hovermonkey   Members   -  Reputation: 129

Like
1Likes
Like

Posted 26 June 2013 - 07:04 AM

Actually you can hash a 7x6 Connect-4 board fairly simply in 63 bits, since you know that the empty holes must always appear above the pieces:

7*6 = 42 bits for the piece colours (0 = white or empty, 1 = black)

7*3 = 21 bits for the height of the columns (a three bit number containing a height of 0-6, 7 is invalid)



#5 Álvaro   Crossbones+   -  Reputation: 12807

Like
2Likes
Like

Posted 26 June 2013 - 07:14 AM

John Tromp taught me of a slight variation of what hovermonkey suggests: Reserve an extra bit per column and encode a position by marking the first empty spot in each column and each white disk. That will give you a 49-bit unique encoding of the position.

 

EDIT: Here's what the code would look like (in C++, because I don't know Java):

/*
Square numbering:
 
 6  13  20  27  34  41  48  <-- extra row to mark the first empty spot, even when the column is full
 5  12  19  26  33  40  47
 4  11  18  25  32  39  46
 3  10  17  24  31  38  45
 2   9  16  23  30  37  44
 1   8  15  22  29  36  43
 0   7  14  21  28  35  42
*/
 
typedef unsigned long long u64;

u64 const BOTTOM_ROW = (1ull<<0) | (1ull<<7) | (1ull<<14) | (1ull<<21) | (1ull<<28) | (1ull<<35) | (1ull<<42);

struct Position {
  u64 white;
  u64 black;
  int move_number;
};

u64 encode(Position const &p) {
  u64 occupied = p.white | p.black;
  return ((occupied << 1) | BOTTOM_ROW) ^ p.black;
}

FURTHER EDIT: Sorry I had to fix my sloppy code.


Edited by Álvaro, 26 June 2013 - 09:52 AM.


#6 patishi   Members   -  Reputation: 212

Like
0Likes
Like

Posted 26 June 2013 - 09:39 AM

thanks for the great advices. I also read the john tromp's code but except for the first couple of lines i couldn't understand exactly what's going on.     
let's say i want to implement what hovermonkey suggest..  how do i do that?    what do you mean by 0 = white or empty?   how can i tell the difference than?  
and when you say 3 bit number containing a height, how does it look like?   

again,I am very sorry for my ignorance but i am rather new java programmer and programmed only in OOP fashion up until now,  i have no idea about bits and bits manipulation so i am getting a hard time understand this stuff.       but i (kinda)  got the basic idea , it's mostly the technical part that holds me back.    



#7 AfroFire   Members   -  Reputation: 392

Like
1Likes
Like

Posted 26 June 2013 - 11:37 AM

I think hovermonkey and alvaro are suggesting the same solution.

 

First: recognize that one byte is 8 bits. Each bit is a switch that is either on or off.

/*
Each COLUMN is a BYTE (8 bits). The last/first (you decide) 3 bits tell you where the empty spot is (this is the parenthesis number). Since you have 3 bits, you can count from 0-7. You need 0-4 to mark where the empty spot is in the rows below. Then you can use whatever information is left to tell you what colored piece is left in the last row (once you've filled up rows 0-4).
 
c5: (0)  (0)  (0)  (0)  (0)  (0)  (0)  <-- extra row to mark the first empty spot. 
c4:  0    0    0    0    0    0    0
c3:  0    0    0    0    0    0    0
c2:  0    0    0    0    0    0    0
c1:  0    0    0    0    0    0    0
c0:  0    0    0    0    0    0    0

Zero can be white or nothing because of the number in the top. If you KNOW where the last available spot is, then you know that any zeros below that point are white pieces and you know that anything above that is empty. 

For example, imagine this board state:

c5: (3)  (4)  (2)  (0)  (0)  (0)  (0)  <-- extra row to mark the first empty spot. 
c4:  0    0    0    0    0    0    0
c3:  0    0    0    0    0    0    0
c2:  1    0    0    0    0    0    0
c1:  1    0    1    0    0    0    0
c0:  0    0    1    0    0    0    0

This is a win for the white player - Can you see why? Look at the 2nd column (the one with (4) at the top.) The 4 tells us that the free spot on this column is at c4, which means c0-c3 are all white pieces since in this case 0 is white. 1 is black.

Is this clear?

*/


AfroFire | Brin"The only thing that interferes with my learning is my education."-Albert Einstein

#8 Álvaro   Crossbones+   -  Reputation: 12807

Like
0Likes
Like

Posted 26 June 2013 - 11:56 AM


I think hovermonkey and alvaro are suggesting the same solution.

 

hovermonkey's suggestion uses 63 bits, while mine uses 49 bits only, so they can't possible be the same.

 

What I suggested (again, John Tromp's idea, not mine) uses n_rows+1 bits per column. In each column the highest-set bit tells you how many pieces are in that column. The lower bits indicate whether those spaces are occupied by a white (1) or black (0) piece.

 

In hovermonkey's idea, the number of pieces in a column is encoded by a 3-bit number.



#9 patishi   Members   -  Reputation: 212

Like
0Likes
Like

Posted 26 June 2013 - 01:13 PM

thanks for the further explanations, i think i am starting to get it, but i will read it a couple more times before i'll start to write some code.  
and one more thing,  let's say i am working with bit board and i want to hash a board position,  so now instead of hashing it,  the key will be the bitboard ,right?


Edited by patishi, 26 June 2013 - 01:16 PM.


#10 Álvaro   Crossbones+   -  Reputation: 12807

Like
0Likes
Like

Posted 26 June 2013 - 02:38 PM

thanks for the further explanations, i think i am starting to get it, but i will read it a couple more times before i'll start to write some code.  
and one more thing,  let's say i am working with bit board and i want to hash a board position,  so now instead of hashing it,  the key will be the bitboard ,right?

No, the bitboard-based representation most likely will consist of two bitboards, one per player, as I showed in the piece of code above (I would probably use an array of 2 bitboards instead of calling them `white' and `black'). The function to hash it could then be the one I posted called `encode'.



#11 patishi   Members   -  Reputation: 212

Like
0Likes
Like

Posted 26 June 2013 - 04:49 PM

Alvaro,thank you for the code example.   i see you put the white and black bitboards in a structure (class) named Position.    so far so good, but can you kindly further explain to me what every line actually does on the encode()  function?    

I think maybe i will use java's BitSet class  for each bitboard (white and black).    The BitSet class has some nice functions that let you treat the bitset as some sort of array..
i can set a  bit in a certain index just like i would in a normal array and such..         but, is it a good practice to put zero's and 1's in the bitset (array-Like ) for the making and unmaking moves??   

for example,  when white makes a move on a certain square,  now i need to replace the 0 in his bitboard to 1 (in that certain bitboard index).     how do you do that in a normal fashion way?   (without using special BitSet classes).     or more clearely,  how do you manipulate the bits on the bitboard?   

 

From the john tromp's page i can see that he is initializing  the board array (holding the two bitboards,W&B, as Long primitives) with 0 for each one.    that i understand because at the starting position no one has played yet,  but after white makes a move,  do i need to replace that 0 Long with another long which corresponds to a bit parttern that looks like the current state of the board?    how can i know what number i need to represent the board  at any given position?  

 

 

EDIT:  by the way, i read some more info on bits and bits manipulation and i am starting to understand the four basic bitwise operations: or,and,xor, and ~


Edited by patishi, 26 June 2013 - 06:16 PM.


#12 AfroFire   Members   -  Reputation: 392

Like
0Likes
Like

Posted 26 June 2013 - 06:20 PM

 

thanks for the further explanations, i think i am starting to get it, but i will read it a couple more times before i'll start to write some code.  
and one more thing,  let's say i am working with bit board and i want to hash a board position,  so now instead of hashing it,  the key will be the bitboard ,right?

No, the bitboard-based representation most likely will consist of two bitboards, one per player, as I showed in the piece of code above (I would probably use an array of 2 bitboards instead of calling them `white' and `black'). The function to hash it could then be the one I posted called `encode'.

 

Meeehhhh

 

They're approximately the same. He just uses up an extra top row.

 

Additionally, you're saying

"In each column the highest-set bit tells you how many pieces are in that column" -- one bit can only tell you a maximum of 0-1. You need the highest 3 bits to keep track of the next empty space. I don't think 49 is enough bits. 56 sounds right though. Unless I am missing something...


AfroFire | Brin"The only thing that interferes with my learning is my education."-Albert Einstein

#13 patishi   Members   -  Reputation: 212

Like
0Likes
Like

Posted 26 June 2013 - 07:26 PM

well, for start i think that i will be using two full 64 bit Longs ( e.g bitboards),one for the white player and one for black (so i will have an extra 22 bits per board,so what)    i will store them

both in an array of size 2.  something like    static long[] board = new long[2];           I read some more about bit manipulation and started to get the trick of bit masking for checking states and such ,combined with the & (AND) operator.       but right now i am still facing the problem of how should i make and unmake moves on the bitboards (how do i set a certain bit to be 1 or 0 )??     can you please advice me to the right direction of doing this?


EDIT:  ok i think i am starting to get it (so excited! )   by investigating the john tromp bitBoard code a little further, i see that he is doing a xor on the certain bitboard he likes to place a piece (e.g a bit of 1) with the number 1L <<  the index he save in the height[] array...  now i understand the purpose of tracking the first empty square in each column.  it is for the <<  operation.        

he also keep track of the plies played,  and checking if the current ply is even or odd so he knows whether its white's  turn of black's.      


Edited by patishi, 26 June 2013 - 08:21 PM.


#14 Álvaro   Crossbones+   -  Reputation: 12807

Like
0Likes
Like

Posted 26 June 2013 - 09:24 PM

 

 

thanks for the further explanations, i think i am starting to get it, but i will read it a couple more times before i'll start to write some code.  
and one more thing,  let's say i am working with bit board and i want to hash a board position,  so now instead of hashing it,  the key will be the bitboard ,right?

No, the bitboard-based representation most likely will consist of two bitboards, one per player, as I showed in the piece of code above (I would probably use an array of 2 bitboards instead of calling them `white' and `black'). The function to hash it could then be the one I posted called `encode'.

 

Meeehhhh

 

They're approximately the same. He just uses up an extra top row.

 

Additionally, you're saying

"In each column the highest-set bit tells you how many pieces are in that column" -- one bit can only tell you a maximum of 0-1. You need the highest 3 bits to keep track of the next empty space. I don't think 49 is enough bits. 56 sounds right though. Unless I am missing something...

 

 

I don't think you understood what I was saying. "The highest-set bit" means "which bit is the highest one that is set". That is not a single bit of information. 49 bits works just fine. You shouldn't take anyone as an authority on anything, but I have done this type of thing before and I know what I am talking about, so your prior should be that I am probably correct and you need to think about it a little bit more.



#15 AfroFire   Members   -  Reputation: 392

Like
0Likes
Like

Posted 27 June 2013 - 12:18 AM

 

 

 

thanks for the further explanations, i think i am starting to get it, but i will read it a couple more times before i'll start to write some code.  
and one more thing,  let's say i am working with bit board and i want to hash a board position,  so now instead of hashing it,  the key will be the bitboard ,right?

No, the bitboard-based representation most likely will consist of two bitboards, one per player, as I showed in the piece of code above (I would probably use an array of 2 bitboards instead of calling them `white' and `black'). The function to hash it could then be the one I posted called `encode'.

 

Meeehhhh

 

They're approximately the same. He just uses up an extra top row.

 

Additionally, you're saying

"In each column the highest-set bit tells you how many pieces are in that column" -- one bit can only tell you a maximum of 0-1. You need the highest 3 bits to keep track of the next empty space. I don't think 49 is enough bits. 56 sounds right though. Unless I am missing something...

 

 

I don't think you understood what I was saying. "The highest-set bit" means "which bit is the highest one that is set". That is not a single bit of information. 49 bits works just fine. You shouldn't take anyone as an authority on anything, but I have done this type of thing before and I know what I am talking about, so your prior should be that I am probably correct and you need to think about it a little bit more.

 

Your advice is confusing. I shouldn't call anyone an authority but I should implicitly trust you based on the fact that I don't even know you?

 

Anyways, this is a place where we should be trying to clarify. I am still not understanding your approach. If we marked the highest bit with a single 1, we couldn't differentiate between each player. If you're feeling threatened/impatient perhaps you could just link to the original implementation? I tried googling around for it, briefly, but couldn't find it.


AfroFire | Brin"The only thing that interferes with my learning is my education."-Albert Einstein

#16 Paradigm Shifter   Crossbones+   -  Reputation: 5248

Like
1Likes
Like

Posted 27 June 2013 - 04:10 AM

The highest bit set in a particular column does not represent a piece. There will always be at least 1 bit set in each column, and the set bits beneath that dummy bit are the pieces of a particular colour. Bits not set beneath the highest set bit represent pieces of the other colour. You need an extra row to have room for the dummy bit.

 

EDIT:

Empty board

1111111

After first move, middle column (player who goes first represented by a 1)

0001000
1111111

Next player plays on top of that

0001000
0000000
1111111

If they had played to the right instead of on top, the board would be

0001100
1111011

etc.

Edited by Paradigm Shifter, 27 June 2013 - 04:20 AM.

"Most people think, great God will come from the sky, take away everything, and make everybody feel high" - Bob Marley

#17 Álvaro   Crossbones+   -  Reputation: 12807

Like
1Likes
Like

Posted 27 June 2013 - 07:17 AM


Your advice is confusing. I shouldn't call anyone an authority but I should implicitly trust you based on the fact that I don't even know you?

 

No, you shouldn't trust me. You should only believe what I say because it's convincing. But I have a decent track record of getting things right. The reputation score in these forums is an imperfect indication of that. For people that have been around here long enough, they probably [hopefully] have had good experiences with my suggestions before. It's rather annoying that you would claim it can't be done with 49 bits when I think I just explained how it's done.

 

But let's get back to the technical details, which is what really matters.

 

 


Anyways, this is a place where we should be trying to clarify. I am still not understanding your approach. If we marked the highest bit with a single 1, we couldn't differentiate between each player. If you're feeling threatened/impatient perhaps you could just link to the original implementation? I tried googling around for it, briefly, but couldn't find it.

 

Perhaps Paradigm Shifter's explanation is clear to you. Just in case, I'll try to explain it in a different way.

 

Take a connect-4 position on a 7x6 board, with white and black pieces. Extend the board to be a 7x7 board by adding an extra row at the top. Now drop a blue piece on top of each column as a marker of how filled the column is. I claim that the set of squares occupied by either a white or a blue piece completely describes the position.

 

If you are given the set of squares described above, you can deduce that a square was occupied by a piece originally if and only if it is below some square in the set. If one of those squares is in the set itself, it must have contained a white piece; otherwise, it must have contained a black piece.

 

I should mention that one should be careful when using this value to compute indices into a hash table. If the hash table has a size that is a power of 2, only the low bits of the key will be used to determine where in the table to store the position. With this particular hash, the content of the leftmost columns completely determines the low bits, so there would be tons of collisions and the performance of the hash table would suffer. There are a couple of ways to solve this problem:

  1. Use a table whose size is not a power of 2. Some people like to use a prime number for this, although what really matters is that you pick a number N such that all the powers of 2 are different modulo N. For instance, Mersenne primes are bad choices.
  2. Do some bit-mixing on the key, like adding some constant, multiplying by some odd constant and flipping the top and bottom 32 bits. Notice that all those operations are invertible, so the key is still unique.

I recommend going with 2.


Edited by Álvaro, 27 June 2013 - 07:18 AM.


#18 AfroFire   Members   -  Reputation: 392

Like
0Likes
Like

Posted 27 June 2013 - 08:04 PM

I get it!

 

Thank you for your efforts Paradigm Shifter!

 

Time for me to whip my e-penis out:

Alvaro, my own history on Gamedev extends back to 2000/2001, and it is because of this site that more than a decade later I have two degrees (physics and computer science) and work at a company that EVERYONE knows about. Even your grandmother. You do not know who I am, or who I work with. Your solutions may be correct, but the attitude that you deliver them with is off-putting. I'm probably coming at you a little hard, but it is only because this sense of friction I've always felt when getting 'help' from the so-called 'experts' of GameDev. They're what make this site, and also what ruin it. Anyways, being an expert in this field now means that it is my responsibility to "stand up" to others when they are not making sense, and to make certain that clarity is achieved. 

 

Finally, "You should only believe what I say because it's convincing." -- Which is what I am trying to do. I did NOT find it convincing.

 

"But I have a decent track record of getting things right." - I don't even know who you are. Why would I know that you have a history of getting it right? You're just a name in an HTML table to me.

 

"The reputation score in these forums is an imperfect indication of that." -- It's a horrible way to reason that your idea makes sense. At the risk of sounding tautological : The idea makes sense when feel I can implement it. Your reputation is irrelevant. 

 

"For people that have been around here long enough, they probably [hopefully] have had good experiences with my suggestions before" -- Again: Irrelevant to my understanding.

 

" It's rather annoying that you would claim it can't be done with 49 bits when I think I just explained how it's done." --. I never claimed that it "can't be done", I said "I don't think 49 is enough bits. 56 sounds right though. Unless I am missing something..." which is a lot less than a 'claim' that "This can't quite possibly be done with 49 bits, you faker!"

 

 

Please don't vilify me for simply challenging your claims explicitly - just try to make them clearer. If you're as awesome as you think you are, then helping me understand shouldn't take much effort. 


AfroFire | Brin"The only thing that interferes with my learning is my education."-Albert Einstein

#19 patishi   Members   -  Reputation: 212

Like
0Likes
Like

Posted 27 June 2013 - 08:23 PM

Meanwhile... i have written some code for my bitboard logic.   and although i found a rather ineffiecient way of checking for four in a row combinations (i was getting a hard time understand john tromp's own code for that)  , I am satisfied with my solution so far.       
but now i am facing the problem of checking for 1,2 and 3 in a row combinations (for the eval' function).   this was so easy working with arrays, cause i had all the possible winningLines saved in arrays of size 4 (all 69 of them)  and than all i had to do is passing through each one of them and count the number of pieces i have for each player on that same line.   

But how should i do it when working with a pattern of bits?  i can't just "walk"  through it and count the bits one by one.  ofcourse i need this to be as fast and effiecient as possible so i will enjoy the benefit of working with bitboards.      any suggestions?

 

 

 

EDIT:  the only way i can think of is to save (again)  all the winning lines in arrays like before, but this time just check each bit in a certain index to see if it is 1 or 0 by using the AND (&) operation on that bitboard with another bitboard with 1L<< - the certain index i want to check..   and than count them up.           


Edited by patishi, 27 June 2013 - 08:47 PM.


#20 patishi   Members   -  Reputation: 212

Like
0Likes
Like

Posted 01 July 2013 - 04:45 PM

The BitBoard code i wrote so far is working "bug-free",  after some experiments and optimizations.   so first of all thank you all for the great help and tips (also john tromp for his bitBoard logic code).    but i am still stick with the board hashing issue (which is the main reason i thought of moving to bitBoards to begin with..).   

Do you guys think i need zorbist hashing for this?   I didn't toally get how it works ,but from reading a little bit about it, it seems to much for connect 4.  maybe i can use a much more simple board encoding scheme.       can you please show me a way to take two bitBoards (white's and black's)  and hash them into one unique 64 bit long? 

I didn't get the Alvaro's example above..i would like for a brief explanation of how it works if possible.  thx!


Edited by patishi, 01 July 2013 - 04:46 PM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS