TT in endgame

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

TT in endgame

Postby BitSet » 09 Jan 2011, 14:09

Hi,
Looks like transposition table causes serious problem in edgame (at least in my case). Recently my engine has seven pawns advantage over TSCP and the game ended up in a draw because of threefold repetition. I used to check if the best successor from TT will cause draw by repetition in current situation but that's not the case. Because of the fact that in endgame TT successor is often returned at root node and no further analysis is performed, my engine doesn't spot that returned move will alow opponent reply that will actually cause draw by threefold repetition. So I decided not to use TT when game state that will be looked up has already occured in the game or current variation (I've noticed that if state that has already occured in the game is looked up in TT it is common that game ends up in a draw). I don't know if it's good solution. Maybe You have some experience in using TT in the endgame.
BitSet
 
Posts: 23
Joined: 27 Feb 2010, 16:25

Re: TT in endgame

Postby H.G.Muller » 09 Jan 2011, 17:29

TT are most useful in the end-game, and I think you will cripple your engine by not using it there. Perhaps better would be to suppress TT cutoffs in the first 3 or 4 ply, so that you are sure the repetition-detection code will be executed there. Then you will never stumbleinto a repetition blindly.
User avatar
H.G.Muller
 
Posts: 3170
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: TT in endgame

Postby BitSet » 09 Jan 2011, 23:26

Seems to be good idea but I'm not sure if it really is for engine which usually searches to the deph between 7 and 12.
BitSet
 
Posts: 23
Joined: 27 Feb 2010, 16:25

Re: TT in endgame

Postby H.G.Muller » 10 Jan 2011, 09:15

Why not? Even at 7 ply less than 1% of your tree nodes has d<4.
User avatar
H.G.Muller
 
Posts: 3170
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: TT in endgame

Postby BitSet » 10 Jan 2011, 19:05

That's right and the conclusion is if TT cutoff occurs close to the root node then benefits are greater because more nodes are skipped.

I allow TT query only if game state didn't actually occured (or may have occured - current variation) in the game. But with Your idea it can be improved to allow lookup also when distance between current node and root node is greater than 3 plies.
BitSet
 
Posts: 23
Joined: 27 Feb 2010, 16:25

Re: TT in endgame

Postby H.G.Muller » 10 Jan 2011, 19:40

BitSet wrote:That's right and the conclusion is if TT cutoff occurs close to the root node then benefits are greater because more nodes are skipped.


That is not true at all. If an entry at ply level 2 would have gotten a hit for a remaining depth (= draft) of 5, it means that the daughter nodes (with draft 4) of the 5-ply search that created that entry are probably also still in the table, as are the grand-daughter nodes of draft 3. So if you ignore the hits at level 2 and 3, you will get all the hits at level3. Effectively you would only be doing a 2-ply search from level 2 with hash-cut leaf nodes at ply=4, so taking the d=5 hit will hardly have saved you any time at all.
User avatar
H.G.Muller
 
Posts: 3170
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: TT in endgame

Postby crystalclear » 18 Dec 2011, 21:03

I am looking for a thread to resurrect discussion about transposition tables.

I have just found this one and the problem described reminds me of something I discovered recently called Graph History Interaction :-
http://webdocs.cs.ualberta.ca/~mmueller/ps/aaai-ghi.pdf

The article I thought was of the most interest was this one, as it appeardd to describe a way to code elegantly and effectively around the problem.
http://wiki.cs.pdx.edu/wurzburg2009/nfp ... ll-ghi.pdf

But I am wondering if I can pick people's brains a little on the general subject of transposition tables, and I'll put that in a separate posting.
crystalclear
 
Posts: 91
Joined: 22 Sep 2011, 14:19


Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 3 guests

cron