Sign in to follow this  
patishi

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

Recommended Posts

alvaro    21246
That code is very very slow. Make hashValue a part of the board representation and whenever you place a disk or remove a disk, ^= it with the appropriate entry from the table.

Share this post


Link to post
Share on other sites
patishi    212

sorry,but i am a slow thinker smile.png  when exactly should i ^= ?  when i make an actual move or when i make a move inside the alpha beta function?  and how (technically) this can be done??  after i make a move i get a totally new position..how (without hashin it) can i tell what to xor it with?        and what did you mean by making the hashvalue a part of the board representation?   

Edited by patishi

Share this post


Link to post
Share on other sites
alvaro    21246

The way I structure my code, there is a class Board that looks something like this:

struct Board {
  u64 bitboard[2];
  int height[7];
  u64 hash_key;
 
  void make_move(int square, int side) {
    bitboard[side] ^= u64(1) << square;
    height[square/7]++;
    hash_key ^= zobrist_table[square][side];
  }
 
  void undo_move(int square, int side) {
    bitboard[side] ^= u64(1) << square;
    height[square/7]--;
    hash_key ^= zobrist_table[square][side];
  }
};

 

I don't create new positions in the search tree, but modify the existing one by calling make_move and undo_move. Does that make more sense?

Share this post


Link to post
Share on other sites
patishi    212

ok.. first of all thx for the code,it is very helpful.   and yes,ofcourse i am also doing make and unmake move (not creating new board arrays or something like this) i am working on a single board in my program.    I see that you XOR that hash_key class member..but what are you doing with it?  aren't you saving it in the hash table or something?  

in my program i have a special class for all the transposition table functions.  you can also find there the zobrist making and the insert and find method.   In the alpha beta function,after i finish calculating a move, or when i get an early cut off i normally store the current board position in the hash table.  and in the start of the function i search for a similar position to see if it is in the table (and for that i need to hash it again!).      but you know that stuff already smile.png   I just don't get how your hash_key relates to the transposition table    

Edited by patishi

Share this post


Link to post
Share on other sites
patishi    212

Ok thanks,you are right.  i will try to figure it on my own for a while.  i am sure that in some way or the other it will work,even if the implementation won't be the best.

Share this post


Link to post
Share on other sites
patishi    212

EDIT: I rewrote this post, i've  managed to work it!  now i have a zobrist hashing and the speed gain is very nice.    thanks a lot Alvaro for the help smile.png

      But i have a another question related to the transposition table management.  would you recommend using some sort of replacement scheme for same positions with different depth?   say if the new position has a larger depth than the saved one than i should replace it  with the new one.        casue right now i am not doing any replacement,i am just inserting the positions blindly to the table.     

I am handling collisions by using a LinkedList in every table index,so if two board positions fall at the same index, i just add them to the list.   

And what size of Transposition table do you recommend using?  right now i have table at size 500009 .  but when i measure the amount of insertions to the table,I get more than 3 million ! (depth 15)

Edited by patishi

Share this post


Link to post
Share on other sites
alvaro    21246
If your search is fast at all, you won't be able to keep all the results in memory. The way a transposition table typically works, it has a fixed size and at some point you'll have to overwrite entries and forget things. There are several replacement schemes you can use to decide what to throw out. I have always had good results with size-4 buckets. See this page for more info.

The size of the transposition table should be determined by the available RAM in your computer. Make them as big as you can without forcing the OS to swap memory pages. If you have 4 GB of memory, you should be able to use 2GB for the transposition table without any trouble. Edited by Álvaro

Share this post


Link to post
Share on other sites
patishi    212

thx, this is exactly what i needed!     But how can i know when is the best time to start replacing entries from the table?    regardless of the replacement scheme i use, how should i technically remove old entries from the table?   should i iterate over the whole array and start deleting items?   

EDIT:  I was getting out of memory errors!  so now  my implementation includes one array in size 500009, each index contains a LinkedList (for chaining when collision occurs) 

 so right now when a linked list has over 2 items in it i just clear them from the list.   but i don't know if my approach is good or not.   

 

Edited by patishi

Share this post


Link to post
Share on other sites
alvaro    21246
Each index should contain an entry and nothing else. You need to decide what locations an entry might be stored in (I use buckets of 4 locations) and then, when you want to store some information, you might find that all those locations are occupied by other stuff: That's when you overwrite something with the new entry.

Share this post


Link to post
Share on other sites
patishi    212

thanks for your patience Alvaro...very much appreciated!     but i don't understand.  what do you mean by 4 locations?  (by "location" you mean an index in the array? should i store the same entry in 4 different indexes?)  if i have an array ,that each index of the array (this is what you mean by bucket?)  contains only single  Entry object (Entry object contains all the details like zobrist key,depth,score  etc..).   the index which the Entry is stored in get's picked by the compression function (zobrist key % size of array).        my logic tells me,that i can store only one Entry object per index (instead of a list of a few Entries)

and when a collision occurs, i can decide whether to keep the already saved entry or to overwrite it for the sake of the new entry  (  the new entry might be the same position, or a different one that only fell in the same index by the compression function).      

Am i totally in the wrong direction here??       

 

EDIT:  Right now i am experimenting with an array of size 1000003, and everytime a position collide to a certain index which already have a position in it,i simply replace no matter what is stored.    i will try to improve it,with a replacement by depth.      but is it at least acceptable?

 

Edited by patishi

Share this post


Link to post
Share on other sites
alvaro    21246
Naming convention:
* Entry: A structure containing hash key, depth, score, bound type, best move, age...
* Bucket: A group of a few consecutive entries (say, 4).

There are many possible replacement schemes (I gave you a link earlier to a chessprogrammingwiki page about it). The one I use consists of computing n=(hash_key%table_size)&~3, and storing the entry in the "weakest" of entries n, n+1, n+2 and n+3. By "weakest" I mean:
(1) If the hash_key of the stored entry matches the hash_key of what we are storing, that is the weakest entry.
(2) Empty entries are weakest.
(3) Entries with a value of age that is not the current age (meaning they are from a previous search) are weaker than entries from the current search.
(4) For entries that are not distinguished by the previous criteria, lower depth is weaker.

When you want to retrieve data from the transpositions table, you need to search in four locations before giving up. If you align things correctly, all four entries might fit in a cache line, which means you get the extra memory accesses essentially for free.

If I were using this scheme, I would pick a table size that is a multiple of 4, of course.

Share this post


Link to post
Share on other sites
patishi    212

Hi.  I just wanted to say that so far i have implemented the Transposition table with zobrist keys and also a killer moves heuristic mechanism. all that combined with bit board logic and my program runs super fast.  only 2-3 ( maybe 4 at the first move only) seconds in depth 15!   when comparing the time this calculation takes without the use of TT and killer moves,  the difference is HUGE (it takes forever).  so thank you all and especially Alvaro for all the help in all subjects, thanks to you i have learned a lot and have a nice working engine  :)  

Share this post


Link to post
Share on other sites
patishi    212

just one final question related to this subject,  i am applying the transposition table and killer moves only in the "inner" negamax function, not int the "root" negamax where i go through the root moves (the "root" negamax calls the negamax on every root move and the negamax calls itself recursively).  should i implement the TT and killer moves operations in the root negamax also?       
And i also clear the hashTable and killer moves table after every move, is this neccesary?  my TT  replacement scheme is "always replace" at the moment, not by depth...so maybe clearing the hash table every move is not neccesary. 

Edited by patishi

Share this post


Link to post
Share on other sites
alvaro    21246
Clearing the TT makes your program forget a lot of what it found in previous searches, some of which is still useful. So one should generally not do it.

The main reason to clear the TT is that it is much easier to debug problems if they can be reproduced, and clearing the TT and other data structures (e.g. killer moves, history heuristic) makes your searches reproducible.

Share this post


Link to post
Share on other sites
patishi    212

thank you , i wll try it without the clearing process.  actually in the 4 first moves i use an evaluation function and after that i am brut forcing to the end of the game tree,so i hope that this is still ok (to retain the positions searched in the "evaluation" part of the program).   

and one more thing please..  i am trying to understand what exactly is a "hash move"..  i know that when i am storing a position in my TT i should also store the best move (or something like that...).   but when should i use it?    at the beggining of alpha beta, when i am probing the table for a position, if the position is found in the table i just returning the score, or updating alpha/beta accordingly..  so when i get the change to use the hash move??     can you please advice on that?   

I tries reading stuff on the net, but no one actually gets to the technical part

Edited by patishi

Share this post


Link to post
Share on other sites
alvaro    21246

You get to use the hash move whenever you find the position in the TT but you can't use the information there to just return a score. What you do with it is try it first, of course.

Share this post


Link to post
Share on other sites
patishi    212

ok,  so every situation where i don't return the score (nor exact, and not alpha>= beta after updating them).    and i guess that the hash move can be not only when i get a cut-off but also after a complete branch search (?)     thx again for all the answers, i will conclude this topic in that final question  .(.unless someone else will want to post something ofcourse)

Edited by patishi

Share this post


Link to post
Share on other sites
alvaro    21246


and i guess that the hash move can be not only when i get a cut-off but also after a complete branch search (?)

 

I always store a move, but I think there are people that only do it if the move caused a beta cutoff. This is the kind of thing that you should determine by testing.

Share this post


Link to post
Share on other sites
patishi    212

Do you do TT and killermoves (etc) operations in the root alpha beta functions also?   right now i am just iterating through all the root moves without any further operations, all of the TT and killer moves operations are happening inside my recursive alpha beta functions (not for theroot moves),  but i would like to try and get an early cut off in the root moves as well.    right now my root moves order is static  (starting from the middle column and going to the side columns)   
 

Edited by patishi

Share this post


Link to post
Share on other sites
alvaro    21246

The order at the root is very easy to do well if you use iterative deepening: Whenever a move is determined to be the best so far, move it to the top of the list.

 

If you are going to always search to the end of the game, you should probably start with the hash move if there is one.  Then sort the other moves using history heuristic (John Tromp swears his particular flavor of history heuristic made his program dramatically faster).

Share this post


Link to post
Share on other sites
patishi    212

yes,right now i am starting with the hash move and than trying my two killers..after that i just continue to go through the rest of the columns list that wasn't played.  
I also got some very good improvements with the killer moves (and the TT ofcourse).  but like i said,i am not doing nothing at the root negamax and i think that this is the main reason that the search is not optimal.            I am not using iterative deepening yet,but i will investigate about it.         thx!

Edited by patishi

Share this post


Link to post
Share on other sites
patishi    212

Just another question, i can't stop thinking that i am doing something wrong.   so i need to check some things:
 

A.  whenever the alpha beta function returns a score (beta cut off or not), i am saving the current position in the Hash table with the evaluation and the current move that  was tried.     this is the so called "hash move" that i will use later in case this position ever occur again.    but I read somewhere (a chess blog) that i don't always have a best move to store...that is a little confusing, because i DO  always have a best move!     the move under investigation will be the best move!   so i don't get it...what am i missing here?

 

 

B.  the times when i store a position in the TT after a beta cut off, the hash move that i store is the same as the killer move for that same depth (if i understood correctly,a killer move is a move that caused a beta cut off).  so many times i have both hash move and a killer move that are actually the same(!).   is this normal?     i always try the hash move first, and after that i check if the killer is the same move,and if it is ,i don't play it and just move on to the next.    so many times, i don't  benefit at all from using the hash move cause i have the killer moves anyway.         up until now i haven't noticed a significant improvement from using the hash move sad.png      that got me thinking that maybe i am doing something wrong 

Edited by patishi

Share this post


Link to post
Share on other sites
alvaro    21246

A. Most chess programs use a so-called "null move" heuristic which can result in finishing a search without a move. This doesn't apply to connect 4 (it only works for games where Zugzwang is the exception).

 

B. Nothing wrong with what you describe. Most of what you read is geared towards minimax searches that don't get to the end of the game, where a lot of things are quite different. It is not surprising that heuristics that work well in a typical searcher don't work well in a program that does exhaustive search to the end of the tree. Even between programs of the same type, most heuristics don't work for everybody because they interact with other decisions made when building the program.

Share this post


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