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.