Tic-Tac-Toe AlgorithmBy: Ronil Chaudhary Have you ever tried to master the game of Tic-Tac-Toe so you would never lose. “How can I make a unwinnable game of Tic-Tac-Toe?” is my QED problem. I am investigating Minimax game theory. Minimax game theory works by thinking multiple steps ahead of the game and is typically applied to strategic scenarios. Also Minimax code works by seeing many steps ahead but for the game of tic tac toe I can try to see two steps ahead. Like professional Chess players.

Minimax will put itself in the opponent’s place to look at every possible solution. To code Minimax you must first define the playable areas on the board in an array. This is how it looks at the start of the game of tic tac toeDisplay = “_”, “_”, “_”, “_”, “_”,”_”, “_”,” “,” “,” “. Its an empty array. On the other hand Display=”O”,”X”,”O”,”X”,”X”,”O”,”O”,”X”,”O” is a full board with 9/9 spaces filled in. Furthermore Minimax checks each square on the board and look for winning moves. My code also uses Minimax because if there are no current winning moves it will check for threats using the defensive procedure. It looks like a tree diagram which branches spread out until they reach a final culmination.

Additionally I  referred to “Introduction to minimax” by V. F. Demyanov and V.

N. Malozemov but it was not that helpful Minimax first originated from John Von Neumann and Oskar Morgenstern in 1944. Back then it had many limitations which made it hard to apply to more practical situations like Economics. Now the situation has changed drastically because it has been greatly refined by modern mathematicians. Modern Minimax can be referred to as “strategic decision making” as stated by Cwoebker in 2012 post about the topic.

I wanted to apply Minimax to Tic-Tac-Toe. Minimax seemed like the perfect solution to producing a code that wouldn’t let the players win  regardless of who started first. My final Tic-Tac-Toe  python program can only be tied with.At first, I tried to use a much more simple way of thinking. I made a simple algorithm to block player from winning. However this was rather easy to beat by using “checkmate moves”, which gives the player two opportunities at winning, these moves, therefore cannot be blocked because you only have one turn in the game. To counter checkmate moves, I created a special logic within my  computer move function that would block these moves ahead of time. At this time I was coding it in a language which was easy to write; Scratch.

Although Scratch works, it was a huge mess and very hard to explain to others. My solution to this was to code in a program that would allow me to define the board visually, let me make functions, and be more organized overall. When I began to write my code I first needed to put down some standards:1.Give an option to either player or computer to take first turn2. Give Player ‘O’ and Computer to ‘X’ 3.

To be unbeatable means to not be able to lose.4.Ties do not count as losses.

5.If the program is set against itself it can only tie.At the start of my code I had referenced http://neverstopbuilding.com/minimax and https://inventwithpython.

com/tictactoe.py which has some of the steps I refer to finalise my program. In this article it better defines the Minimax algorithm and how to make it work better than the book,”Introduction to minimax.” But the first code was in  javascript and second was in python so it gave me an idea. So, I decided to translate my functions from Scratch to Python. Then I made my display_board with some help from my dad and finally I was able to start testing the code. Next I had to debug and I was essentially done with the project.

In conclusion I was able to make a unwinnable game of Tic-Tac-Toe by utilizing Minimax. Now my code is as close as possible  unbeatable regardless of whoever goes first. ——————————————————————————————————-Functions and LogicStart of the gameA small logic to see who takes the first turn and passes control to the display board function.Example Welcome To Ronil’s Game of Tic Tac Toe …Would you like to go First? (Y/N)If you choose Y, this is how your board will look.

_|_|__|_|__|_|_              Choose your Spot 1-9: Display board.This function prints the initial blank board.It knows  who is taking first turn (player or computer)It pass the control to either player move function or the computer move function.Player moveAsk the player to choose a spot on the boardChecks to make sure the player chooses the correct spot b/w the given parameters.

Mark the player spot with a ‘O’Turn the board to computer after player playsPass the control to check who has won the game (winning_move_check) Winning Move Check This will check for a move that could complete a row of 3, thus winning the game. For example:      _|_|X    _|X|0    X|_|0    O|_|X     _|O|_     X|_|O   O|X|X    X|O|O    X|X|OThis function is a for-loop. It will loop after every move to check for winning moves.It will go through the following combinations to check for winning moves.

1, 4, 7, 2, 5, 8, 3, 6, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 5, 9, 3, 5, 7Example If 3=5=7 and 3=’X’  the algorithm will print that the computer won and pass the control to finish_the_game functionHowever if neither computer nor player won and all the 9 spaces are filled,  the algorithm will print that its a Tie and pass the control to finish_the_game functionIf all the 9 spaces are not filled the control goes back to game.Computer move If it’s the computer’s first turn and if the middle spot is not chosen the computer will select it by preference and pass control to the player because its turn has ended.Example:           _|_|_         _|x|_        _|_|0If the middle spot is taken and it is the computers first turn or second turn it will activate the edge_choice function.

The edge_choice function will choose an edge spot at randomExample:           _|_|_         _|O|_        _|_|XIf this is not computer first turn then the logic is more complicated.  The logic will decide which spot to pick. First the winning logic and then defensive logic will activate as needed.Winning LogicThe logic loops through the row and column to find two spots where the computer has already placed ‘X’ and the third spot is not ‘O’Example it takes first list 1,4,7Checks if 1 and 4 is ‘X’ and 7 is not ‘O’ put X on 7.

Checks if 4 and 7 is ‘X’ and 1 is not ‘O’ put X on 1.Checks if 1 and 7 is ‘X’ and 4 is not ‘O’ put X on 4.   X|_|O              _|O|_         X|_|_X|_|X              _|O|_         O|_|_It runs through all these combinations (1, 4, 7, 2, 5, 8, 3, 6, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 5, 9, 3, 5, 7)If it finds a spot it uses with ‘X” .

Mark the computer move,Then pass the logic the function winning_move_check will check who has won the game.Defensive LogicIf the winning logic doesn’t get executed as the computer move flag is still set to false instead of true then it is activated.The logic loops through the row and column to find two spots where the Player has placed ‘O’ to check the same combination as in the winning logic but this time it is to block the player from winningExample it takes first list 1,4,7Checks if 1 and 4 is ‘O’ and 7 is not ‘X’ put ‘X’ on 7.Checks if 4 and 7 is ‘O’ and 1 is not ‘X’ put ‘X’ on 1.Checks if 1 and 7 is ‘O’ and 4 is not ‘X’ put ‘X’ on 4.

O|_|_              _|X|_         O|_|XO|_|O              _|X|_         X|_|_It runs through all these combinations (1, 4, 7, 2, 5, 8, 3, 6, 9, 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 5, 9, 3, 5, 7)If it finds a spot it uses it. Mark the computer move flag to true.Pass the control to check who has won the game (winning_move_check).Checkmate Moves             _|_|O        _|X|_        O|_|_                  O|_|_        _|X|_        _|_|OFor above two special cases it is the Computer’s second turn we can’t have the computer choose a corner spot, as this will lead to a loss.For this to we have to put a logic block to choose any of the 2,4,6.8 position’s randomly.

        _|O|_         _|X|_         O|_|         _|_|O         _|X|_         _|O|_These two above cases are really complex as neither corners work nor 2,4,6,8 will work,For this to we have to put logic to choose any of 2,8 or 4,6 position randomly.After all these are checked then the program will select the best spot and give the player a turn.Finish the game The purpose of this is to display the final board and exit the program. Reference ListFox, J. (2013, December 13). Tic Tac Toe: Understanding The Minimax Algorithm.

Retrieved November 27, 2017, from http://neverstopbuilding.com/minimaxAbdolsaheb, A. (2017, February 18). How to make your Tic Tac Toe game unbeatable by using the minimax algorithm. Retrieved November 27, 2017, from https://medium.freecodecamp.org/how-to-make-your-tic-tac-toe-game-unbeatable-by-using-the-minimax-algorithm-9d690bad4b37Minimax.

(2017, November 14). Retrieved November 27, 2017, from https://en.wikipedia.org/wiki/Minimax