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

Started by
81 comments, last by Tom Sloper 8 years, 3 months ago

good news, i have been able to improve my code a little, and the engine's thinking time is less than before. but one thing i think that's holding me back is my Transposition table operation. right now whenever i want to insert an entry to the table i create an Entry object with all the neccesary variables inside. but creating a java object takes time (and also memory,but i don't think that's an issue in my case) . is there another way of doing this? If i understood correctly from looking at john tromp's code, he is not using a standart Entry object, but using a Long instead..? but how can i save all this data into a Long type? only the hashTable key is a 64 but long itself...
any ideas on how i can improve this area?

Advertisement

As I explained elsewhere, you should avoid dynamic memory allocation in this type of performance-bound program. The transposition table should be that, a table, with a fixed size that is allocated once at the beginning of the program and then just written to or read from.

A hash key only needs 49 bits in connect 4, as was discussed earlier in this thread. Also, where you are in the table gives you partial information as to what the hash key is, so you can afford to store fewer bits to avoid collisions. [EDIT: I think you need 27 bits.]

I am using the zobrist hashing at the moment, which gives me a 64 bit hash keys.. (or am i mistaken?). and besides that, whithout using an Entry object which holds all the TT Entry info (score,key,valueType etc.) than how can i store all that in a single array index? should i bunch it all into the bits of a 64 bit Long variable? I really don't know how to do it.

You can pack several fields in a single integer, by deciding that bits 0-2 will encode the score, 3-4 the bound type, 5-63 the higher bits of the Zobrist key (for instance). The bit manipulations are pretty straight forward.


long encode_TT_entry(int score, long key, int valueType) {
  return score + (valueType<<3) + (key & 0xffffffffffffffe0L);
}
 
int get_score_from_TT(long TT_value) {
  return TT_value & 7;
}
 
int get_valueType_from_TT(long TT_value) {
  return (TT_value>>3) & 3;
}
 
long get_key_from_TT(long TT_value) {
  return TT_value & 0xffffffffffffffe0L;
}

John Tromp seems to use small positive integers as scores, perhaps so he can do this type of thing easily. Handling signed numbers can also be done, but it's trickier.

[EDIT: 42 bits should be enough to distinguish all 64-bit patterns, if you have 8306069 separate locations in the TT.]

thank you very much for the code, i will investigate it

And another small thing before i get on with the code, when i am doing key%tableSize to get the entry index, should i do it with the complete 64 bit hash key and only after that (when creating the entry integer) cut it down to 58 bits? Or should i do the mod operation already with the shorter key..

EDIT: by the way, how do you store -1 in the 3 right most bits? i know that java only supports sign numbers, so the left most bit of a number is a "sign" bit. (that means that -1 needs to look something like this: 10000001 if this is a Byte type) so how can i put a "-1" in the entry pattern and than add some other information? I can always store a -1 as a 3 (11 in binary) and just manually translate it into -1 smile.png

This is my New Transposition Table code (in my own simple way smile.png ) please give me corrections

private final int N = 8306069;
private long[] table;
public NewTT(){
table = new long[N];
}
public void initTable(){
for(int i = 0; i<table.length; i++){
table = 0L;
}
}
private int compress(long key){
return (int)(key % N);
}
public void insert(long key,int value,int valueType){
int index = compress(key);
long entry = 0;
if(value == -1){
entry = 3 + (valueType << 2) + (key & 9223372036854775792L); // if the value is -1 i translate it to 3 ( 11 in binary )
}
else{
entry = value + (valueType << 2) + (key & 9223372036854775792L);
}
table[index] = entry;
}
public long find(long key){
int index = compress(key);
if((key & 9223372036854775792L) == (table[index] & 9223372036854775792L)){
return table[index];
}
else{
return 0;
}
}
public int getValue(long entry){
if((entry & 3) == 3){ // here i again translate the 3 back to -1
return -1;
}
else{
return (int)(entry & 3);
}
}
public int getValueType(long entry){ // 1 = EXACT_VALUE, 2 = LOWERBOUND, 3 = UPPERBOUND
return (int)((entry >> 2) & 3);
}
EDIT: OH MAN!! what a major improvement in speed! still not like john tromp engine, but much much better than what i had before smile.png
Alvaro, now only 3 seconds with the position you showed above!! OH man i am so happy

Update: I improved my engine's speed incredibely! the trick was actually to change the static move ordering (combined with killer moves ofcourse). now my default columns order is {1,5,4,3,2,0,6} starting at the root node and changing dynamically with the help of killer moves. I will try to improve the move ordering by maybe trying (again) to use the hash move. No matter what variant of the history heuristic i tried to use, the killer moves gives me greatest boost in speed.

Now my engine analyses the most complex position i encountered so far (took 2-3 minutes in the beginning), now only in 16-17 seconds! which is exactly the same time as john tromp engine take to solve the exact position. smile.png

Another question i have is: is it ok if i use only 47 bits in my TT entry for the hash key? (the most left ones). is it enough in order to be unique?

I just want to mention that when i am saving to the table, i am using the full hash key (zobrist) for the compression process (key % Size of Table) to find the index in the table,and only when actually saving iam cutting it to 53 bits only (cause i also store the depth,score,valueType...)


Another question i have is: is it ok if i use only 47 bits in my TT entry for the hash key? (the most left ones). is it enough in order to be unique?

I just want to mention that when i am saving to the table, i am using the full hash key (zobrist) for the compression process (key % Size of Table) to find the index in the table,and only when actually saving iam cutting it to 53 bits only (cause i also store the depth,score,valueType...)

Yes, that's enough. You can probably prove it formally using the Chinese remainder theorem.

How many positions per second does your program examine?

can you advice me how can i measure the nodes per second rate? i assume that i need to put some sort of a counter somwhere in the alpha beta, but can't figure out where exactly? (maybe inside the for loop where i go through each possible move? ) right now i am just measuring the start and end time of the calculation so i have the total seconds. if i have the total number of nodes i can just divide it by the seconds

The two popular options for counting nodes are:

(1) Count calls to the alpha-beta function

(2) Count calls to make_move

I use (1), and so does Fhourstones, so that's the number I am more interested in.

This topic is closed to new replies.

Advertisement