EGTB usage idea

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
MOBMAT
Posts: 110
Joined: Sat Feb 04, 2017 10:57 pm
Location: USA

EGTB usage idea

Post by MOBMAT » Sat Feb 01, 2020 1:36 am

I'm sure someone has already tried this, or has already implemented it, but I was wondering what the tactical improvement would be from the following scenario.

Design:
EGTBs that at the lowest level, only return WLD (or unknown to indicate in illegal position).
This would require a nibble per entry (win = 1, loss = 2, draw = 0, illegal = 3). we'll assume no need for an illegal check except for debugging)

After a EGTB probe, if the position is a draw, 0 is returned. If the result is a win or loss, one possible option is to return a big mate value, such as M500 or -M500, adjusted to the ply of the search. Instead, we can use the maximum mate value associated with the state of the position at the time it was probed. Example, we get to a KRK position and the lookup is a win for the side moving, instead of using M500 as a return value, M16 is used since that is the maximum moves needed to force mate. For KQK it is M10. KBBK is M33, etc. This information is available up to 7-man tables now.

The logic that probes the EGTB would need to know these values, but they could be stored easily in a small hash or lookup table.

The potential gain is that the search would favor the results with the smallest value, which would be either the EG type with the smallest mate value at the same depth, or smaller values found further up the tree.

It seems logical that using the maximum position state mate values would solve mates faster than just using a big mating score, but how much better is it?

Also, using only WLD EGTBs saves a lot of space.

Has anyone tried this idea?
Vince S
Author of MOBMAT

"Reductions, extensions, and pruning, oh my!"

User avatar
phhnguyen
Posts: 561
Joined: Wed Apr 21, 2010 2:58 am
Location: Australia
Full name: Nguyen Hong Pham
Contact:

Re: EGTB usage idea

Post by phhnguyen » Sat Feb 01, 2020 4:46 am

Did you study bitbase EGTB as well as Scorpio bitbase?

https://www.chessprogramming.org/Endgame_Bitbases
https://www.chessprogramming.org/Scorpio_Bitbases

The huge disadvantage of bitbases is sometimes you may hardly make progress on searching. I had had already a question/discuss about that problem:

http://www.talkchess.com/forum3/viewtopic.php?t=45009
https://banksiagui.com
A freeware chess GUI, based on opensource Banksia - the chess tournament manager

MOBMAT
Posts: 110
Joined: Sat Feb 04, 2017 10:57 pm
Location: USA

Re: EGTB usage idea

Post by MOBMAT » Sat Feb 01, 2020 5:51 am

That thread is great, thanks.
No, I hadn't seen that thread. Sometimes you don't always find what you are looking for because of incorrect search terms.
Harms' ideas are interesting and tells me I would be reinventing the wheel to proceed further.
which only proves my usual theory that if I can think of it, someone else has already done it!

Thanks for the quick reply.

V
Vince S
Author of MOBMAT

"Reductions, extensions, and pruning, oh my!"

bob
Posts: 20770
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: EGTB usage idea

Post by bob » Sat Feb 01, 2020 6:32 am

Couple of points. W/D/L tables, by themselves are problematic once you are actually into a (say) 5 piece ending, because they don't tell you the shortest path, they just choose a winning path. Which will start to fail as you approach the 3-fold repetition or 50 move draw rules. You might be lucky and not walk into a forced repetition or 50 move draw where you can't avoid it without playing a move not flagged as winning.

Most of us use both. W/D/L inside the search, but once we actually get into the specific endgame position, we drop into the DTC table bases which does take us on the shortest path to a conversion which is an approximation of the shortest path to win (close enough).

An alternative that would work most of the time would be to generate all ply one moves, then go through them and cull any move not flagged as WON in the W/D/L table base. Search only those, which will let you at least play a winning move, but giving your search a chance to guide you through the 50 move and repetition land mines most (but not all) of the time.

Using both seems to be the easiest solution. With SYZYGY the size of the 3-4-5 man tables (W/D/L + DTC) is 939mb according to the files I have. At the root, probe the DTC which gives you the shortest path to a conversion (removing a piece for example). While not completely optimal in terms of DTM, it works since a conversion resets the 50 move counter after a capture, promotion, etc.

There is already code in the syzygy library to do this for you. I use it in Crafty and it works flawlessly

Post Reply