How I built an unbeatable AI algorithm for Tic-Tac-Toe game in Ruby

Humans have always been fascinated by the idea that machines could beat them at their own strategy game and which had made creating realistic gaming experiences incorporated by AI, the future of the gaming industry. The rise and dominance of AI have shown to be a consequential advancement in creating games that are smarter and more interactive and capable of piquing a player’s interest and satisfaction over a long time.

Before I developed my first AI game, the word Artificial Intelligence seemed somewhat abstruse to me. I construe its integration as a herculean piece of a task in which computer programs or computer-controlled robots are built with lots of intricate codes, back-breaking computations, and simulations to perform tasks commonly associated with intelligent beings. It could be that complicated actually but it could also be as simple as building an algorithm such as the minimax that takes a simple decision policy of minimizing losses and maximizing gains in all cases. And building games with it such as the tic-tac-toe can provide a fun motivation to learn how to do it; and that was exactly how it happened for me.

In the Ruby section of the curriculum in Microverse programming school, each student is required to build a tic-tac-toe game playable via the CLI. It was quite fun and intriguing to do, and after the project, the eccentric part of me set in and I decided to take the game logic a little further by implementing a computer/player gameplay since the initial game was just for two physical players. And I built a pseudo minimax AI algorithm!

You can play the game and see its full logic HERE.

Understanding the AI logic

One of the ways we can think about playing a tic-tac-toe game is as a list with all the possible moves of what the game board looks like. For example, if this is the current game state, and let’s say the computer player is Dan Bot. Its Dan Bot’s turn and he’s using Xs. There are three places he can place his marker.

We can take all possible outcomes for Dan Bot’s option and all of the options his opponent can take. Because computers are controlled, each outcome for Dan Bot is only a win or a tie. To decide which choice to make, Dan Bot will assume that in each move, both he and his opponent will make the best possible choices. So, his grounds for making decisions will alternate between choosing a path that will maximize the outcome of winning his turn and minimize the outcome of his opponent winning on their turn. And at any time, when presented the choice of a winning path or a draw path, Dan Bot will always pick the first option and win the game. By laying out all these possibilities and taking the path that leads to a win, Dan Bot can solve a tic-tac-toe game and beat a human player at it. This means it will always achieve the best possible winning outcome, either a win or tie no matter how his opponent plays.

Programming the AI game-logic in four steps

The following are the steps taken by our computer player to make one decision on what board cell to place its marker. To make the game realistic, our bot still goes by the name Dan.

Collates possible moves

The first decision rule Dan Bot makes is to collate every possible move on the game board at every of his turn. He will need to know what positions on the board are available to him to make a rational decision.

Predertermine winning position

Next, Dan Bot uses the information collected to predetermine if there is a winning case. He performs swift hidden moves on the available board cells, first with his marker and then with his opponent’s marker. If placing his marker on any available spot gets him a winning move, then the game is over and he wins or he checkmates and automatically wins the game if there was no other possible move for his opponent. But if there isn’t any winning case, he applies the next line of action.

Check best moves

Dan Bot checks the center position [5] and all corner positions [1, 3, 7, 9] against his previously collated list of available positions. He knows that placing a marker on any of these positions — center and corner positions offers a player a better opportunity of winning the game or stifling his opponent’s chances of winning. First, he checks for the availability of position 5, which has the most opportunity amongst all. If the slot is open and not marked by his opponent, he goes for it and if not, he picks the next available slot from the list of the corner positions. He checks for their availabilities and picks any one of them at random. This is to mimic human spontaneity and make the game more realistic. So, Dan Bot is allowed to be impulsive for a few moments. And if none of these actions were possible, he moves further.

Check other moves

At this point, Dan Bot replicates the same action as above but this time with the center position [5] and all middle-edge positions [2, 4, 6, 8]. He retraces the same steps until he finds an available spot and unmarked by his opponent.

With these steps, we are been taken through an AI decision path programmed for the computer player to follow. In the end, decisions are made which leads to a winning game for Dan Bot (computer player) or a tie game for both players.

In Conclusion

Computers definitely seem to struggle with the part of human language like humor, irony and also are not great at understanding real people but AI systems are finding gradual successes in bluffing such assertions and so should not be underestimated. We can say that Artificial Intelligence will keep on creating a huge impact on the gaming industry. Since information is continually being accessed and massive bounty of data are produced, these create complex and fascinating capabilities to train AI algorithms; to give them ‘smartness’ to respond to human stimuli and create realistic feelings. It is evident that AI will keep on revolutionizing and giving exciting opportunities for game developers to broaden their creativity.