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

Optimization Results

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


Player 1 vs Player 2 Heuristic 2 Heuristic 3 Heuristic 4 Heuristic 5
Heuristic 2 X 3 4 5
Heuristic 3 3 X 4 5
Heuristic 4 4 4 X 5
Heuristic 5 5 5 5 X


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.