Metrics used to study
We studied various metrics to evaluate the optimizations like :
1. Number of nodes generated
2. Total number of nodes generated
3. Average number of nodes generated
4. Time taken for each move ( in milliseconds )
5. Total time till now.
6. Average time per move
Different Cases :
1. Optimization of generation of moves
From the stats we see, that Player 2 is optimized. We can see the difference in the average number of nodes generated is 4 : 1. And it is also much faster than the other player. ( 321 ms vs 1153 ms average move time )
Improving Alpha-Beta Pruning
2. Best Move first
The player with the best move first generated much less number of nodes due to heavy alpha-beta pruning ( 4353 vs 10802). It is faster also
3. Sorting the generated moves
The player 2 first sorts all of its moves. We see that this results in heavy alpha-beta pruning. ( 3254 vs 11116 avg. no of nodes ). It is also very fast ( 156 ms vs 315 ms on the average )
4. Best move vs Sorted Moves
We see that sorting of moves results in more alpha-beta pruning than the best move first approach. The tradeoff is the Order n2 sorting algorithm vs the order n best move first. Still sorting performs better as it results in more alpha-beta pruning and thus decrease in number of nodes generated.
Comparison of Heuristics
We see that as the intelligence improves, the computer moves better and better. It is very difficult for a human player to beat the computer with Heuristic 4 or 5.