Simulating the Search Space of Chess

[rjgibert]

Has anyone tried simulating the search space of chess? The idea is that move generation and position evaluation (also simulated to approximate an actual program) would then take a negligible amount of time, so that search changes could be evaluated to greater depth much more quickly.

Adapting the simulator to new changes in an actual chess playing program would be done by an automated process by statistical sampling of the actual program.

BTW, this could also be an effective way to validate an alpha-beta search. You would simulate a game with a constant branching factor to see if the number of nodes searched corresponds exactly to the formula: floor(d^b/2) + ceil(d^b/2) - 1 with perfect move ordering. In theory, you should also be able to validate PVS this way too. You don't need the corresponding formula for PVS. You just need an empirically determined node count for each corresponding depth determined from another (hopefully) correctly coded program.

[Volker Annuss]

Hello Ricardo,

this has been done by Valavan Manohararajah in Parallel alpha-beta search on shared memory multiprocessors, Chapter 4: Artificial game trees.