0 comments

Minimax implemented via a Tic-Tac-Toe variant using a 6x6 grid where 4 in a row wins.

You go first. Simply click on any square to start. Please give the computer up to 10 seconds to respond.

A Minimax algorithm drives the play of the computer. I've recently added alpha-beta pruning, reducing computation times from 20 seconds to below 10. The current ply depth is only 3. Even with alpha-beta pruning, increasing the ply to 4 pushes first move response times to 60 seconds. This is due to game tree bredth, not depth. At a ply of 3, after the first human move, the max game tree is 39,270 (35x34x33). However, with a ply of 4, the tree size grows to ~1.2 million (35x34x33x32). Bredth is the enemy of minimax, not depth.

Minimax is a Depth-first search algorithm. It starts at the current state (e.g. game board) and for each legal move, it makes it, and then does the same for the opponent, continuing to either a max depth (ply) or until a win/draw/loss position arrises. At the bottom of the tree lies all possible game positions. Each position is then scored.

From there, backtracking occurs and the best move for each player is chosen. This continues all the way back to the root (current state) and the final max value is the best possible move that can be made (given all the possible permutations which can arise after it's made).

Below is the algorithm and an example of how it's called. The second example is the same algorithm, but with Indirect recursion, which is easier to understand for those new to Minimax.

Please contact me if you're interested in the rest of the code and RSpecs.