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 ~

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

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.

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.

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.

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.

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.

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.

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.

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!