Search with bitbase

[phhnguyen]

I am still working on my search function for bitbases but facing a big problem of heavy explosion.

At this moment, my search function is closed to a normal alpha-beta search (it uses hashtable, null move, pv, but there are not qs nor evaluation functions). All necessary endgames (bitbases for 5 men, full DTM for 4 men) are loaded into memory so they can be probed in high frequency. The search function is mainly used for 5 men only and it stops searching immediately at any branch down to 4 men due to full DTM 4 men.

I have tried few things such as probing at leaves only or 2/3 depths, and/or sorting move order by few ways such as hash move - captures - rest; hash move - winnings (based on probes) - draws - losings... but problem is still remaining. For example, for KRNKB, the search can reach easily depths 10-12 in reasonable time, but then too slow to go deeper and I don't think it can reach to depth 50 which needed for that endgame even in hours.

Still working but would like to know if anyone has experiences or any trick, technique?

Thanks for any help.

[kbhearn]

To reach depth 50 with alpha beta you're going to need massive amounts of pruning, an amount that's probably not attainable with just a WDL table for a generally won endgame. Perhaps a better option would be to just generate the single 5 man in memory on the fly from the 4 men tables. For tables with pawns you can restrict the pawns to their initial files as only progress captures can move them to another file in which case you've made it to a 4 man that you have an exact score for.

The other option would be to make your WDL table more generally useful with DTC information (such as C<20, C<35, C<50, not won as your 4 states for the bits (since the side trying for the win is generally obvious and the other side accidentally winning is generally findable as a quick tactic like 'stronger side just dropped their Q'). To convert this into a 100% accurate DTM search is still a chore, but perhaps actually manageable (perhaps not).

[Daniel Shawul]

For example, for KRNKB, the search can reach easily depths 10-12 in reasonable time, but then too slow to go deeper and I don't think it can reach to depth 50 which needed for that endgame even in hours.

I think you misunderstood the need for searching. It is not to resolve the endgame position by searching it to the end. 10-12 plies is more than enough to make progress. Here is what you need to do. For a WDL score, lets say you assign +5000,0,-5000 scores respectively, then at the leafs add your eval() to this score to help it make progress. Since you have hashtable, null move and all other stuff, you would need to adjust this score by the ply like we do mate scores. So before adding that and other stuff, it is better to test that simple idea first by turning off hashtable,null move etc..

[phhnguyen]

To reach depth 50 with alpha beta you're going to need massive amounts of pruning, an amount that's probably not attainable with just a WDL table for a generally won endgame.

Thank you. Now I feel confident with my current work (not doing something too silly).

Bitbase and WDL information seems be not magic for finding mates. I think using WDL may be much worse than using rules (even it is not easy to write rules) when searching because we can easily to add more information than only WDL to rules.

Perhaps, I will try to find another solution instead of insisting to search until mates - it is clearly hopeless for some endgames which DTM may be over 120.

Perhaps a better option would be to just generate the single 5 man in memory on the fly from the 4 men tables. For tables with pawns you can restrict the pawns to their initial files as only progress captures can move them to another file in which case you've made it to a 4 man that you have an exact score for.

Very interesting idea. However, from my experience, generating a 5 men endgame may take houses if not days (download them should be faster than generating them). Thus it is a big practical problem.

The other option would be to make your WDL table more generally useful with DTC information (such as C<20, C<35, C<50, not won as your 4 states for the bits (since the side trying for the win is generally obvious and the other side accidentally winning is generally findable as a quick tactic like 'stronger side just dropped their Q'). To convert this into a 100% accurate DTM search is still a chore, but perhaps actually manageable (perhaps not).

I think we may save for some endgames but not all if using DTC instead of DTM. The problem is still serious.

[phhnguyen]

For example, for KRNKB, the search can reach easily depths 10-12 in reasonable time, but then too slow to go deeper and I don't think it can reach to depth 50 which needed for that endgame even in hours.

I think you misunderstood the need for searching. It is not to resolve the endgame position by searching it to the end. 10-12 plies is more than enough to make progress. Here is what you need to do. For a WDL score, lets say you assign +5000,0,-5000 scores respectively, then at the leafs add your eval() to this score to help it make progress. Since you have hashtable, null move and all other stuff, you would need to adjust this score by the ply like we do mate scores. So before adding that and other stuff, it is better to test that simple idea first by turning off hashtable,null move etc..

Thank you.

I understand your idea. Actually I have no problem with searching progress even my score system is still simple because I keep all 4 men as full DTM and embedded already plies into every mating scores.

I think for chess endgame is OK for searching /making progress in few depths. However, my current attempt to build an app as an endgame dictionary/solver (show in bellow image). I need to show all DTM as suggestions for making moves. Thus WDL or slow searching are not good enough.

[syzygy]

I think we may save for some endgames but not all if using DTC instead of DTM. The problem is still serious.

If you loosen the requirement of finding the shortest path to mate to finding a winning path to mate, you can get rid of the large DTM tables and instead use a combination of bitbases (for probing during the search) and DTZ tables for probing at the root.

If DTZ tables are still too large, you can make them half-sided and throw away those for endgames that are easy to win by searching anyway.

With some effort and good compression, 1 GB is sufficient.

I need to show all DTM as suggestions for making moves.

If you insist on that, you'll just need full DTM tables. Well, half-sided tables should be ok too if it's not for use during search. Or host the tables on a server and probe over the internet.

[phhnguyen]

I think we may save for some endgames but not all if using DTC instead of DTM. The problem is still serious.

If you loosen the requirement of finding the shortest path to mate to finding a winning path to mate, you can get rid of the large DTM tables and instead use a combination of bitbases (for probing during the search) and DTZ tables for probing at the root.

If DTZ tables are still too large, you can make them half-sided and throw away those for endgames that are easy to win by searching anyway.

With some effort and good compression, 1 GB is sufficient.

Interesting idea. Thanks. I will take this number (1 GB) as the target for my next attempt to reduce the size of my EGTB.

I need to show all DTM as suggestions for making moves.

If you insist on that, you'll just need full DTM tables. Well, half-sided tables should be ok too if it's not for use during search. Or host the tables on a server and probe over the internet.

My solution is somewhat similar: I use only databases (full DTMs) for one side only. Some endgames (5 men) will be released with app, but user can download the rest from my server. I am just not the fan of online service because that is expensive in case of EGTB (if we need a stable and fast one) and my app will be a freeware.

[phhnguyen]

My new freeware for IOS devises using endgames 3-4 men has been just approved and now it could be download from Apple Store. It is named Koala chess endgame (find it with key words Koala chess endgame). It is kind of endgame solver / dictionary.

All 3-4 men tablebases are attached already with the app - it is ready to use without downloading any thing else. I have followed strictly Ernst Heinz's index system so the data should be one of the smallest ones in term of size. You may also consider all numbers you could read from app such as numbers of legal positions, wins, draws, losses are standard ones (if I don't do any bug) for such kind of index system.

IMO, it may be a useful tool for us to study, check, reference... when writing endgame code or develop a new EGTB.

More information about this freeware could be read from General Topics:

http://www.talkchess.com/forum/viewtopi ... 748#481748

Hope some will use and find it useful )

/Pham