You might still remember the times when you played Tic-Tac-Toe (a.k.a. noughts and crosses) in your childhood:
In a series of blog posts I want to apply neural networks on this well-known game. But before we may do that, we need to do some preparations.
Eventually, we want to teach a neural network to determine:
- if a board has a winner,
- who the winner is, and
- after which move the winner has won the board.
To be able to properly describe such a board, we need to define an order on the board. I decided to take the order “top-left to bottom-right” like this:
You may also apply a different, more sophisticated scheme for defining the position, but let’s keep it simple.
With this nomenclature, we now can describe the board mentioned initially using a set of integers: 1,6,9,5,4,7,3,8,2. Even more interesting this become, if you consider this not being a set but a list (including order). That is important, because a board may have two “winners”, depending on which player came first. Note that
- by definition, let us assume that X starts the game,
- every other round, it is the other’s player to move (even positions are ‘O’ moves, odd positions are ‘X’ moves), and
- that there are always exactly nine positions in total until the board is fully populated (also called an assignment).
Moreover, the list must not have any duplicates: 1,1,1,1,1,1,1,1,2 may also be a list of numbers, but this does not describe a proper Tic-Tac-Toe game, because the position 1 appears more than once. Therefore, the generation of the list represents a system of choosing without repetition. That brings us to another aspect: We first need to determine, if a list of integers is a valid board after all.
[to be continued on the next page]
Continue reading ‘Preparations: Tic-Tac-Toe and AI (Part 1)’ »