• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
patishi

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

82 posts in this topic

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
0

Share this post


Link to post
Share on other sites

"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.

1

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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)

1

Share this post


Link to post
Share on other sites

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
2

Share this post


Link to post
Share on other sites

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.    

0

Share this post


Link to post
Share on other sites

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?

*/

1

Share this post


Link to post
Share on other sites


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.

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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'.

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

 

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...

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

 

 

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.

0

Share this post


Link to post
Share on other sites

 

 

 

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.

0

Share this post


Link to post
Share on other sites

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
1

Share this post


Link to post
Share on other sites

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
1

Share this post


Link to post
Share on other sites

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. 

0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

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
0

Share this post


Link to post
Share on other sites

Here's the code again:

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

 

Hopefully it is clear what `occupied' means. `occupied << 1' means the set of squares that are above an occupied square. I compute the union of that and the bottom row (which is a constant) and now I have the set of all the squares occupied or on top of an occupied one. XORing that with the set of black pieces sets the places with black pieces to 0, leaving the unique number that I described early in this thread.

 

Is that clear now?

 

Remember to do something about what I mentioned at the end of post #17.

0

Share this post


Link to post
Share on other sites

ok,thx.  yeah,i chose a prime number for the table (do you think that 500009 is enough?) and for the bit mixing part, the function you posted already does that i suppose(?).  

By the way, i do keep the lowest free square of each column in an array called height[] (size 7) but i am only using the exact 42 bits for the board,unlike john tromp's 49 bits representation.    when i make a move and updating ( height[n]++ ), when i reach the column topMost square , the height[n] becomes equal to the next column lowest bottom square.  (this is how i also check for if a certain column is full or not).      e.g i don't have extra 7 dummy bits.    

so i guess the method you showed above still works in my case..?

Edited by patishi
0

Share this post


Link to post
Share on other sites

ok,thx.  yeah,i chose a prime number for the table (do you think that 500009 is enough?) and for the bit mixing part, the function you posted already does that i suppose(?).


No, it does not. But you might not need it because you are using a non-power-of-2 table size.

By the way, i do keep the lowest free square of each column in an array called height[] (size 7) but i am only using the exact 42 bits for the board,unlike john tromp's 49 bits representation.    when i make a move and updating ( height[n]++ ), when i reach the column topMost square , the height[n] becomes equal to the next column lowest bottom square.  (this is how i also check for if a certain column is full or not).      e.g i don't have extra 7 dummy bits.    

so i guess the method you showed above still works in my case..?


No, in that case the code I posted is useless to you. The whole point of the 49-bit representation is to allow that trick.

Alternatively, you can still use a traditional Zobrist key, which would work just fine. Simply generate a table `long zobrist_table[42][2]', initialize it with random 64-bit numbers and XOR together the numbers corresponding to the pieces present on the board. The resulting quantity can be updated incrementally when a disk is place or removed, and it's quite cheap.
0

Share this post


Link to post
Share on other sites

ok thanks!  sorry for the confusion..I should have known that me not using the 49 bits method will not work in this case.  so i think i will go for the zobrist solution,seems simple enough.                  Although i can't help thinking that if a combination of 2 bitboards (white and black both)  is unique for each position (e.g there can't be a situation with the same white bitboard and the same black bitboard together) , there is a straight forward way to produce some kind of key  (something like addition of the two bitboards together + another something smile.png  )      but i afraid that if i will go for something of my own i will get identical keys / codes for different positions.     so  i will go for the safe and popular method of zobrist.      

Edited by patishi
0

Share this post


Link to post
Share on other sites

And another quick question if i may, i know that after making a move (an actual one) i should empty the table and start fresh (please correct me if i am wrong) .

But what about if there is no depth limit..e.g if i am doing a complete tree search. Do i still need to reinitialize the table after each move?

EDIT: while the random numbers part is rather easy for me to understand.   from what i understood, one of the advantages of zobrist is that instead of hashing the entire board every time, one can update it's hash value by means of using XOR.   but i can't figure out how exactly should i do it in connect 4.  I would like to get some example if possible. 
Or maybe this is not relevant in connect 4 since unlike chess,  the pieces are not moving on the board,just being added to it..??

 

 

EDIT2:  what do you say about those two functions.  one is initializing the table with random numbers and the other produce the hash code.  I need some review here
             zobrist is a long [42] [2] array defined in the begining of this class

 

private void initZobrist(){
       Random r = new Random();
     
       for(int i = 0; i<42; i++){
           for(int j = 0; j<2; j++){
                zobrist[i][j] = r.nextLong();
          }
      }
 }
 
 
public long hash(long[]board){
      long hashValue = 0;
      long y1 = board[0];  //white's bitBoard
      long y2 = board[1];  //black's bitBoard
 
      for(int i = 0; i<42; i++){
            if((y1 & (1L<<i)) !=0){
                  hashValue ^= zobrist[i][0];
            }
 
            else if((y2 & (1L<<i)) !=0){
                  hashValue ^= zobrist[i][1];
           }
     }
     return hashValue;
}
Edited by patishi
0

Share this post


Link to post
Share on other sites
Guest
This topic is now closed to further replies.
Sign in to follow this  
Followers 0