In this series of posts, we will evolve a Tic-tac-toe player through an artificial evolutionary algorithm.
When we are done with this series, we will have witnessed the birth of a tic-tac-toe player who can play on a 5x5 tic-tac-toe grid and can play against itself/its clone to get better.
Let's try to semi-formally describe tic-tac-toe:-
1. We have a board with 9 "slots".
2. We have the two "objects" X and 0; and _ representing an empty space.
3. This game has only one valid move; we will call it PLACE[slot, object]. So, PLACE[0, X] would mean we are placing X on the 0th slot.
4. The current board state would then be an array of slots with information about what is in the slot. As an example let's take board state S1: [_,_,X,_,0,_,X,_,_]. This is a valid board state description. For ease, let's lay the board state differently:
S1: | _ _ X |
| _ 0 _ |
| X _ _ |
The mind of the player would be very simple. We will not use neural networks which would make this more complicated (as I like to build them from scratch xD). Instead, we will use the simplest technique of decision-making: Mapping! The mind would map the board state to the best move for that state. It is the simplest form of decision-making with no temporal feedback; no way to learn new stuff. Also, note that the mind of the player would not be separate from its genetic information. Hence, the only way this mind can learn new stuff is through genetic evolution.
Again, I will emphasize that the mind is the same as the genome in this case (the genome is the genetic sequence). In other cases, the mind may be affected by the genome, but stands/forms above it. As is the case with most biological creatures who have a mind.
Here is a valid Mind (which I will name MM1):
MM1: [ S1 -> PLACE[0, X] ]
(Note: S1 was described above).
Now we can see that mind MM1 is a really bad candidate for this game description. This mind only understands 1 board state which is S1, and even for that board state, it only knows one move. It's incapable of playing this game. Of course, this is just an example of a mind. The final mind will be much more robust and would know the complete game.
The mind will be composed by the mapping technique, so let's just call it a Mindmap for simplicity (that's why I had named the mind described above MM1 and not M1 *wink*).
Let's name the species which will grow out of this exercise: 3T. Please don't judge my naming sense. Thanks.
Now only one thing remains and that is the information about which object the player is assigned, X or 0. This would not be a part of the genetic information but would be assigned at the game start to the player.
Here is a valid member of the 3T organism/species:-
3T1: [ X, MM1 ]
3T1 is assigned the X object and has the mind MM1. Note however that 3T1 is not particularly healthy. I am basing the health on how well 3T1 can play the game, and by the looks of MM1, not very well.
With this, we have defined the 3T1 organism in a sort of formal sense. Also note that the object parameter of 3T1 (X in this case) would be used to fill the object parameter of every PLACE[slot, object] move performed by 3T1.
You may realize that the mindmap doesn't necessarily need to distinguish between the X and 0; it just needs to know which object is its object; so for instance, if the objects are switched between players mid-game, it technically makes no difference. However, in this case, I think it would be simpler to just let the mindmap learn both ways of playing separately. It is redundant, yes, but it also brings in interesting scenarios where a certain player is a master when playing with X, but a noob when playing with 0. Isn't that funny?
So now we know our aim. It is to generate 3T's mind map using an evolutionary algorithm, design a way so that 3T and its brethren can play and/or compete, and then see the results of this exercise.
Now, let us get started!
In the next part, we will have a look at Artificial Evolutionary algorithms first.
By the way here's a fun fact: You can play tic-tac-toe on google by just searching "tic-tac-toe"!