Christoph Gockel

4x4 Tic Tac Toe

23 Jul 2014

The 4x4 Tic Tac Toe implementation (Human vs. Computer) is working now. In the end the changes needed were simple, but getting to these changes took more time than I had anticipated.

In order to have the Negamax algorithm return a move in a reasonable amount of time – the acceptance criteria was < 3 seconds – some adjustments to the existing implementation were needed. It’s okay to calculate every possible board constellations when playing a 3x3 board (which is 9! for the first move). But going through all 16! possible moves on a 4x4 is neither really possible, nor feasible, with the current hardware.

So in order to speed up the implementation a bit, I figured that for the first 5 moves on the board, it’s irrelevant which locations the computer player chooses. Since the real “need” to block a possible winning move of a player, only occurs when that player has at least 3 marks set in one row.

So 3 marks for player one and 2 marks for player two (since they mark the board in turns). Now, when there are less than 5 moves on the board, the computer player just pics a random free location (e.g. board.free_locations.sample).

Only after at least 5 moves are made the locations will be based on Negamax. Which brings me to the second optimisation. There is also no real need to calculate all possible boards – just enough is sufficient. So currently the lookup for the “next best move” will only recurse 5 times. In my scenario, that is sufficient to get a reasonable next move. With only 4 levels you could still beat the computer player, so increasing the level by one made the trick.

After that story was done, I started with my Qt spike on the Coin Changer application. I have a very basic UI working for that, and I have to admit that I didn’t expect it to go this smooth. I thought getting Qt up and running would take more time. So tomorrow the initial story for the Qt Tic Tac Toe GUI can be re-estimated.