Time Comparisons


next up previous
Next: Further Optimizations Up: Parallel Implementation and Optimization Previous: Othello implementation

Time Comparisons

As expected, there is a noticeable speedup using the alpha-beta cutoffs as compared to straight minimax. As the Figure 5 shows, searching the same problem yields shorter run times, especially noticeable on more intense problems. This graph compares run times for searches on one board layout, searching to different depths. This board is shown in Appendix B. Time is recorded in seconds, and runs that took mere fractions of a second could not be accurately timed and are reflected by 0 seconds.

Looking at the results in a different way, dividing the completion time by the number of nodes searched, we see that both algorithms spend the same amount of time on each node searched (Figure 6). This is expected because, aside from alpha-beta cutoffs, both searches use the same functions and data management structures. Due to the poor granularity in timing, there is no information for small searches, but as the search becomes intensive enough to get adequate timing information, it is clear that both algorithms are using their time in the same way, which indicates that the main difference between the algorithms is simply the number of nodes searched.

 
Figure: Minimax and Alpha-Beta time comparisons for computationally intensive file

 
Figure: Minimax and Alpha-Beta time per node comparisons for computationally intensive file


next up previous
Next: Further Optimizations Up: Parallel Implementation and Optimization Previous: Othello implementation


abierman@cs.caltech.edu