Tik-Tak-Toe
MinMax
In order to build an AI that can play simple games such as Tik Tak Toe or Connect-4, we are able to use an algorithm known as minmax.
MinMax is acts as an ideal player, and assumes it's playing against another idea player, i.e. at every stage, both players make the best possible move,
however to do this, it needs a way of determining the quality of a move.
The algorithm works by creating a list of possible moves, choosing one and passing the resulting game state to the opposing play, which will do the same.
This repeats until the resulting game state is terminal, meaning either a play has won or no more moves can be made, at this point, the player will return
-1 if the computer lost, 1 if the computer won, or 0 if it was a draw. In effect the algorithm has just evaluated a path of moves through the game, returning
the value says "this path is worth this much", then undoes that move so that the next move can be evaluated. Once all the moves have been evaluated the current
player will choose the best move for it (either the move with the maximum or minimum value) and return its value. This conintues until all the possible paths of
actions have been evaluated and finally the very top level of the algorithm choses the move with the highest value.
Note that this algorithm is only concerned about winning, not how quickly it will win, this means it may sometimes make descisions that won't result in an immediate
win, even if they are availbe, but if it does so, it will still always win. To value winning sooner rather than later, the depth of each action path should be used
to negatively impact the value of a game, this needs to be done carefully to ensure a loss at any point is always worse than a win (after any number of games).
My method (Not implemented in this version) does this dividing the scores by the depth, this causes the value of game sstates to approach 0 (a draw) as the number of
moves to reach them increases.