Hi all. I am sorry for the post flood i am doing here lately 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 ) and guide me on what is the best way to hash a board position.

Thanks in advance!

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 :)

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)

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.

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.

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.

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?

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