People may think that making your own artificial intelligence (AI) is difficult or technical. However, for certain tasks like playing a simple game, it is not hard to build your own self-learning AI. What’s more, you do not even need a computer or electronic device to do this!
A simple yet challenging game is the two-player game called Nim. In Nim, there are counters arranged in at least two piles. At each turn, a player chooses one pile and takes as many counters as they want from it. The player taking the last counter loses the game. The objective of the game, then, is to force your opponent to take the last counter.
For example, suppose our Nim game has two piles, Pile A, containing four counters, and Pile B, containing three counters. A game may go like this: Player 1, starting first, takes one counter from Pile A. Player 2 takes two counters from Pile A. Player 1 takes all three counters from Pile B. Now Player 2 must take the last remaining counter from Pile A, losing the game.
To create an AI that plays Nim, one first needs to figure out all its distinct possible states. In the game described above, there are 13 different states; thus, we require 13 containers, for example paper cups, each representing a distinct game state. Each cup would then contain every possible legal move that can be made from that particular game state; these can be represented by folded pieces of paper, each depicting a legal move that can be made at that game state.
When it is the AI’s turn to play, a paper is drawn at random from the cup representing the game’s current state, and the move depicted on that piece of paper is played. If the AI eventually wins, all the papers drawn are folded and put back in their respective cups. If the AI loses, however, all the papers except the one representing the last move are put back in their cup. However, if by doing so, a cup remains empty, then that paper is still put back in its cup, and the paper representing the game’s previous move is discarded instead.
It is a fascinating experience witnessing a ‘device’ that has no knowledge of the strategies of a game, eventually learning from its mistakes until it masters that game. I invite you to create your own AI and to experience this yourselves!
Alexander Farrugia is a mathematics lecturer at the University of Malta Junior College.
Sound Bites
* In 2017, DeepMind, an AI research lab serving as a subsidiary of Google, released a paper preprint describing AlphaZero, an AI that learns the strategies of three games (chess, Shogi and Go) by playing against itself. After training for a maximum of 34 hours, AlphaZero managed to comprehensively beat the best AI for each game at that point in time – Stockfish, Elmo and AlphaGo respectively. A newer version of AlphaZero was released by DeepMind in 2022 that discovered a faster way to perform matrix multiplication. Also in 2022, another programme, muZero, was released by DeepMind that plays against itself to learn how to play chess, Shogi, Go and ATARI 2600 games without even knowing the rules of any of these games!
For more science news, listen to Radio Mocha on www.fb.com/RadioMochaMalta/.
DID YOU KNOW?
* The game of Nim is solved, that is, the best strategy for each player is known for any number of piles and for any number of counters in each pile.
* There are several variants of Nim. In one variant, the player taking the last counter wins the game, instead of loses the game. In another variant, each player must take counters from the pile containing the largest number of counters in that turn.
* Chess is not a solved game. Although most chess experts agree that a chess game would end in a draw if both players play the best possible move at every turn, this has not been proven mathematically yet. However, chess is solved for positions having up to seven pieces.
* Game-playing AIs aid in discovering innovations in other fields of AI, especially those utilising reinforcement learning, such as natural language processing and robotics.