Complexity

The inference was compiled using two evaluation functions, the first a two attribute function and the second a four attribute function, the hypothesis being that that they should exhibit similar results. Each of the strategies must then be run for a game, keeping in mind that the chosen strategy will be run twice, once when chosen and then when used for comparison. This means six chess games must be run for a particular game to have its search strategy found. On average, there are 35 moves to choose from so for a four ply search of all values, there are more than 1,500,000 moves to scour. This number might be reduced significantly by searching non-quiescent positions, but it would be safe to say, that on average, for inferring one move's search depth, 50,000 moves must be evaluated (the total amount of moves for each strategy). Assuming there are about 50 turns in a game, then 2,500,000 moves need to be evaluated per game. For the study, there were 100 of each type of inference (1 game, 2 game, 5 game and 10 game) so for the 10 game inference for each of the 5 strategies 5,000 games needed to be played. This makes the total number of moves that needed to be evaluated for each of the two evaluation functions in the analysis greater than 1.25 x 10¹⁰. Keeping in mind that this is a conservative estimate and it is possible to have most of the average 35 moves in a non-quiescent position, this then is a very large number and is the reason it necessitated running the program for a week to obtain results.