15 replies to this topic

[cryo75]

I'm adding TT to my negascout function and I'm using zobrist keys. I have a question with regard to storing the score in the table. When storing the best move as well, is this always the best move that is updated in the root function?

[Álvaro]

No. The best move stored in the transposition table is the move that happened to be best the last time we search the node. The point is that if we ever visit this node again, even if we cannot skip the search with the information stored in the TT (because we are now searching at higher depth or because the bound stored wasn't good enough), we can still try that move first. This is particularly important when the move caused a beta cut-off. Chances are pretty good that the same move will also cause a beta cut-off at higher depth and save us a ton of time.

[cryo75]

When there's a beta cut-off I save the entry as follows:

setTT(key, depth, a, TTEntry.BOUND_UPPER, moves.get(i));

 

Before I exit the function returning 'a', I save the entry as follows:

setTT(key, depth, a, TTEntry.BOUND_LOWER, null);

 

But shouldn't I store an actual move instead of null?

 

When I attempt to find a  move at the beginning of the function, I do the following:

 

        if (depth == maxDepth)
        {
        	val = board.getScore();
        	setTT(key, depth, val, TTEntry.BOUND_EXACT, null);
        	
        	return val;
        }

Also, should the TT applied to the recursive function or also to the root?

[Álvaro]

I think you have the bounds wrong. When you have a buta cut-off you want to store it as a lower bound. When you exit the function returning alpha, you have either an upper bound (if alpha was never improved) or an exact score (if alpha was improved).

http://web.archive.org/web/20080315233307/http://www.seanet.com/~brucemo/topics/hashing.htm

The transposition table is for the recursive function only (and perhaps for quiescence search, if your program has it). I don't see any point in doing anything with the transposition table at the root.

[cryo75]

Ooopss I swapped them. I still don#t have quiescence search but I'm planning to add one soon... right after iterative deepening!!

[Álvaro]

Ooopss I swapped them. I still don#t have quiescence search but I'm planning to add one soon... right after iterative deepening!!

If you are programming chess, I would implement quiescence search immediately. The results of the search are almost meaningless without it.

[cryo75]

No I'm working on the nine men morris game for now. I will use quiescence search to return just the moves that will form mills. I think that would be similar to to capture moves in chess.

 

Also, how can I test transposition tables to check that the code I added with regards to TT works fine?

[Álvaro]

No I'm working on the nine men morris game for now. I will use quiescence search to return just the moves that will form mills. I think that would be similar to to capture moves in chess.

Oh, in that case it might help, but I don't think it will be as critical as in chess.

Also, how can I test transposition tables to check that the code I added with regards to TT works fine?

That's a very tricky thing to test. I would implement iterative deepening right away. You should then observe the behavior where after searching up to depth D, repeating the search gets you to depth D almost instantly. If that doesn't happen, you are probably doing something wrong.

You should pick a few positions and measure the number of nodes and the time it takes for the search to reach a particular depth. Although the speed in nodes per second will probably go down after implementing the transposition table, the time to reach a depth should go down.

Finally, you should play a match between your program with and without transposition tables. How many games to play is a tricky question, but I wouldn't do less than a thousand. They can be quite fast (for chess I use about 0.2 seconds per move). The important thing here is accumulating statistics. I would also observe the two programs playing at slower pace (say 10 seconds per move), so you can see what they are doing and notice if there's something broken.

I do what I described in the previous paragraph for almost every change to my program. If you don't do something like that, I don't think you can make meaningful progress.

Edited by Álvaro, 18 March 2013 - 03:11 PM.

[cryo75]

Thanks for the tips. I will definitely do like that. I already thought that I'd need to add iterative deepening to test transposition tables better. That will be my next task!!

[Druzil]

Also, how can I test transposition tables to check that the code I added with regards to TT works fine?

 

One thing I've done is to perform each search with TT on and TT off and then check that the same result is being returned.  The TT shouldn't affect the result (only in extremely rare instances) compared to a normal search - it should only affect the speed.

[Álvaro]

Also, how can I test transposition tables to check that the code I added with regards to TT works fine?

 
One thing I've done is to perform each search with TT on and TT off and then check that the same result is being returned.  The TT shouldn't affect the result (only in extremely rare instances) compared to a normal search - it should only affect the speed.

Unfortunately the result is affected much more often than "in extremely rare instances". Search instability is a well-known phenomenon in alpha-beta search, and transposition tables are responsible for quite a bit of it. In chess this is particularly easy to trigger in situations where draw by repetition or the 50-move rule are involved.

http://chessprogramming.wikispaces.com/Search+Instability

Edited by Álvaro, 18 March 2013 - 04:24 PM.

[Druzil]

It appears that most of these are caused by interactions with other search enhancements.  Surely for the purpose of proving that an implementation is correct, you would disable these enhancements initially?

[Álvaro]

A lot of it also has to do with graph-history interaction. It is possible that nine men morris doesn't have any such issues, and perhaps then this isn't much of an issue.

What happens when a position is repeated in nine men morris? Is the game a draw? If that's the case, there is the potential for trouble already.

[cryo75]

When adding quiescence search with TT, should the code be similar to this when depth == maxdepth??

 

        if (depth == maxDepth)
        {
        	val = quiesce(board, alpha, beta);
        	setTT(key, depth, val, TTEntry.BOUND_EXACT, null);
        	
        	return val;
        }

 

Is it also necessary to save the move struct in the TT? Can it be used for something??

[Álvaro]

I would store the position in the transposition table inside `quiesce'. Storing the move can be useful, because later on you are likely to visit this position again at a higher depth, and the move that turned out to be best in quiescence search is a reasonable candidate to try first.

Disclaimer: I have never obtained an improvement in my programs by using transposition tables in the quiescence search, so I don't use it.

[cryo75]

Well then I will not need quiescence search with TT