We need to implement different strategies to play a game and test their performance against each other. The deadline is midnight tonight, 8 hours from the time of our discussion.
One of the strategies, minimax, looks two levels ahead when choosing a move. This involves a lot of calculations for the future states and thus makes running any tests using minimax much slower.
There is a shortcut to reduce two third of the running time for minimax. This is done by avoiding unnecessary calculations when certain boundary conditions are met. This shortcut is called alpha-beta pruning.
After some simple calculations, we had a good laugh and decided not to implement alpha-beta pruning.
Here is why.
Currently, each game that involves minimax strategy takes 10-20 seconds. Let’s assume that each game takes 15 seconds to run. We are looking at running a test of 1000 games for each strategy pair. So a test of minimax against any of the rest strategy will take
15 seconds per game * 1000 games = 15000 seconds which is about 4.17 hours.
If we have alpha-beta pruning implemented, we can reduce the test time to 1.38 hours per 1000 games.
However, implementing alpha-beta pruning surely takes more than 4 hours, since we were not familiar with prolog and debugging is hard. (We are not being lazy. We had already spent 4 hours together on the previously day trying to implement alpha-beta pruning but failed. We made no progress but got ourselves frustrated with headaches.)
As a result, it seems a better option to just let our computers work hard for four hours as we sip coffee instead of us working madly at prolog while the CPUs run idly!
P.S. Did I mention that the 1000 game test for minimax to play against minimax takes
170 seconds per game * 1000 games = 170000 seconds which is about 47 hours
Alpha-beta pruning will only reduce this time to 15.7 hours, which is almost 8 hours after the deadline at 12 midnight tonight!
You see, there is no way for us to finish running the tests after all. We might as well just lower our expectation and run 20-100 game tests! :P
Tests that are still running after 2 hours and 40 mins… Oh well… :P
