MENACE Part 1: An Introduction to Reinforcement Learning with Matchboxes and Beads
Programming MENACE (A Reinforcement Learning AI) that learns to play tic-tac-toe using matchboxes and beads.
In this series of posts, we will recreate the worlds first reinforcement learning through a hands-on project: programming MENACE (Matchbox Educable Noughts and Crosses Engine), a simple AI that learns to play tic-tac-toe using matchboxes and beads.
Also in this i will show some basic python too for the 1st year students. Others can just skip those parts.
To the first years, there are some references to higher level topics too in the later parts (not this one), don’t get demotivated if you don’t get it, it doesn’t matter too much to code this up without knowing them fully. Send me doubts if needed.
Created by:
- @Quantum-Codes (Ankit Sinha, IIT Tirupati)
- @AnmolSinha42 (Anmol Sinha, NIT Puducherry)
Behaviour
MENACE doesn’t know the rules of Tic-Tac-Toe. It doesn’t know that three-in-a-row wins. It only picks out of a learned whitelist moves from each game board possibility. We need to teach it this whitelist (The ideal moves on every game board possible)
This is done by adding beads to a matchbox as it was done originally, and then pick a random bead corresponding to the move it needs to play (so there will be 9 coloured beads) Each matchbox in the system represents a unique state of the Tic-Tac-Toe board. The Memory: Inside each box are beads of different colours. Each colour corresponds to a potential move (an empty square) on the grid. There can be multiple beads of same colour indicating this move has been responsible for a lot of wins and the random picking will most likely pick that colour again.
On a Win: MENACE is rewarded. Each matchbox used in that game receives 3 additional beads of the colour that was played. This makes it much more likely to repeat those winning moves in the future.
On a Draw: It receives a small reward of 1 additional bead.
On a Loss: It is punished. The beads used in that game are removed from their boxes. This decreases the chance of the machine making that losing mistake again.
There is a possibility that a box empties itself in the process - this means that the game state always leads to a loss and there is no way to recover OR it was in early game and the bot had too much of a skill issue to win (and so we might either have to restart training or make sure each early game state always has 1 of each bead, we will decide which to choose later)
Also typically we always let the bot start so it only learns X’s moves or Y’s moves (these are disjoint to one another). I would want them to play against each other and improve each other, and due to this disjoint property I can just use the same set of matchboxes and in the end have a singular model that can play both X and O.
If you did not understand fully then watch this video by Stand-Up Maths youtube channel.
Creating the tictactoe game itself
We need to create a standard tictactoe game first and then put this system on it. In this part, we will just be making the 2 player game, and in the next parts we will add the AI to it.
1. Storing the game state
skim through this part if you already know basic python
So first we will decide how to store the game - 2D lists seem like a natural choice because of the 3x3 board. We can also use a length 9 string (and that will be better as we figure out later). So we will use the string method but for a few functions i will also share the 2D list method (but not use it in the main code)
If you are using strings then this is how you index: “012345678” and that corresponds to:
| col0 | col1 | col2 | |
|---|---|---|---|
| row0 | 0 | 1 | 2 |
| row1 | 3 | 4 | 5 |
| row2 | 6 | 7 | 8 |
You can see that
index = row * 3 + col
col = index % 3
row = index // 3
Also we will fill the table with X, O and “ “ (a space for empty cell)
Let us first create the board and printing function:
board = " " * 9 # This creates a string with 9 spaces representing an empty board
# this is a print board function for string version
def print_board(board: str):
print(f"""
{board[0]} | {board[1]} | {board[2]}
---------
{board[3]} | {board[4]} | {board[5]}
---------
{board[6]} | {board[7]} | {board[8]}""")
For the 2D list version: (which we will not use in main code)
board = [[" ", " ", " "] for _ in range(3)]
# This is list comprehension. This is the shorter version of:
board = []
for _ in range(3):
board.append([" ", " ", " "])
def print_board(board):
print()
print(" | ".join(board[0]))
print("-" * 9)
print(" | ".join(board[1]))
print("-" * 9)
print(" | ".join(board[2]))
Now let us create a function to get user input AND play the move (Standard tictactoe, no AI yet. See explanation below this code block for how it works):
def player_turn(board: str, player: str) -> tuple[str, int]: # string version
# returns 2 values = updated board and position played
while True:
try:
num = int(input(f"Player {player}, enter the cell number (0-8): "))
if board[num] == " ": # check if cell is empty
board = board[:num] + player + board[num+1:]
return board, num
else:
print("That position is already taken. Try again.")
except (ValueError, IndexError): # valueeerror= not an int, indexerror= not in 0-8
print("Invalid input. Please enter numbers between 0 and 8.")
Explanation of how the above function works:
Let us start with getting user input (make a new file and follow along):
num = int(input("Enter a number between 0 and 8: "))
print(f"You entered: {num}")
This is simple, asks input with the input() function and converts it to an integer using int(). input() returns a string so i need to convert to an integer for greaterthan (>) or lesserthan (<) operations.
BUT what if i enter 10 or 100 or -1? These are invalid. I need to ask user again if i get these values.
So what we will do is that we will keep asking user for input until we get a valid input. For this we can use a while True: loop which will run forever until we break out of it.
while True:
num = int(input("Enter a number between 0 and 8: "))
if 0 <= num <= 8:
print(f"You entered: {num}")
break
else:
print("Invalid input. Please try again.")
We have caught invalid integer inputs now. What if someone enters abc though? int() function cannot handle that, it will throw an error (try it, it gives a ValueError). So we need to catch that error. For this we use try-except blocks.
while True:
try:
num = int(input("Enter a number between 0 and 8: "))
if 0 <= num <= 8:
print(f"You entered: {num}")
break
else:
print("Invalid input. Please try again.")
except ValueError:
print("Invalid input. Please enter a valid integer.")
We have handled all bad inputs! While we are at try-except, try out what error will this code give in this input: abc
arr = [1,2,3]
num = int(input("Enter a number between 0 and 8: "))
print(arr[num])
This gives an IndexError since the index is out of range (range is 0-2, both 0 and 2 included). So we can catch both ValueError and IndexError in the same except block like this:
arr = [1,2,3]
while True:
try:
num = int(input("Enter a number between 0 and 8: "))
print(arr[num])
break
except (ValueError, IndexError):
print("Invalid input. Please enter numbers between 0 and 8.")
There was nothing wrong with the if loop earlier. I would say that previous one was better too! I just randomly wanted to show you how to catch multiple exceptions in one except block.
Now rather than just printing that number, we need to update the gameboard. Go back to your main file, and now let us think how to update the board.
We need to check if the cell is empty first. If it is empty, we put the player’s symbol there. If not, we ask for input again. We check that by if board[num] == " "
Updating the string:
String are immutable, cannot be changed. So something like board[num] = player will not work. We need to create a new string with the updated value.
Try this out:
board = "XOXX OOXX"
print(board[:4]) # prints indexes 0,1,2,3 (4 at end index, so prints upto that. Start index is not given so it just starts from 0 in this case)
print(board[5:]) # prints indexes 5,6,7,8 (start index is 5, end index not given so goes till end)
This is called string slicing. Experiment more with this if you want. We can use this for creating that new string. We can slice upto the index, then put the symbol, and put the rest of the characters.
board = "XOXX OOXX"
board = board[:num] + "X" + board[num+1:] # this gives "XOXXXOOXX"
Lets implement all this:
Also we make this a function that takes in the board and the player (X or O) that needs to be inserted. Finally we return the updated board and the position played.
def player_turn(board, player):
# returns 2 values = updated board and position played
while True:
try:
num = int(input(f"Player {player}, enter the cell number (0-8): "))
if board[num] == " ": # check if cell is empty
board = board[:num] + player + board[num+1:]
return board, num
else:
print("That position is already taken. Try again.")
except (ValueError, IndexError): # valueeerror= not an int, indexerror= not in 0-8
print("Invalid input. Please enter numbers between 0 and 8.")
2D list version: (which we will not use in main code)
def player_turn(board: list[list[str]], player: str) -> int:
while True:
try:
num = int(input(f"Player {player}, enter the cell number (0-8): "))
if board[num // 3][num % 3] == " ":
board[num // 3][num % 3] = player
return num # this function does changes in place on the list, so no need to return board
else:
print("That position is already taken. Try again.")
except (ValueError, IndexError):
print("Invalid input. Please enter numbers between 0 and 8.")
2. Game loop and player switching logic
skim if you already know basic python
Now we will create a game loop function that will print the board, get user input and return the move played
def game_loop(board, player):
print_board(board)
board, move = player_turn(board, player)
return board, move
if __name__ == "__main__":
# game always starts with X
board = " " * 9
player = 1 # 1 = X, 0 = O
while True:
board, move = game_loop(board, "X" if player == 1 else "O")
player = 1 - player # Switch player (1-1=0, 1-0=1)
compressed if loops
These two code snippets are equivalent:
if player == 1:
symbol = "X"
else:
symbol = "O"
board, move = game_loop(board, symbol)
# shortened:
symbol = "X" if player == 1 else "O"
board, move = game_loop(board, symbol)
If you are wondering how `board, move = player_turn(board, player)` works, click here
This is called tuple unpacking. When a function returns multiple values separated by commas, it is actually returning a tuple containing those values. You can unpack this tuple into separate variables in one line.
def example_function():
return 1, "hello", 3.14
print(type(example_function())) # prints <class 'tuple'> (type function returns the type of the data passed to it)
a, b, c = example_function()
print(a) # prints 1
print(b) # prints hello
print(c) # prints 3.14
Checkpoint 1
The code now should run a basic tictactoe game between 2 players. Next we will add win checking logic. Full code until now (click this to reveal)
def print_board(board: str):
print(f"""
{board[0]} | {board[1]} | {board[2]}
---------
{board[3]} | {board[4]} | {board[5]}
---------
{board[6]} | {board[7]} | {board[8]}""")
def player_turn(board: str, player: str) -> tuple[str, int]:
# returns 2 values = updated board and position played
while True:
try:
num = int(input(f"Player {player}, enter the cell number (0-8): "))
if board[num] == " ": # check if cell is empty
board = board[:num] + player + board[num+1:]
return board, num
else:
print("That position is already taken. Try again.")
except (ValueError, IndexError): # valueeerror= not an int, indexerror= not in 0-8
print("Invalid input. Please enter numbers between 0 and 8.")
def game_loop(board, player):
print_board(board)
board, move = player_turn(board, player)
return board, move
if __name__ == "__main__":
# game always starts with X
board = " " * 9
player = 1 # 1 = X, 0 = O
while True:
board, move = game_loop(board, "X" if player == 1 else "O")
player = 1 - player # Switch player (1-1=0, 1-0=1)
3. Win checking logic
skim if you already know basic python
For checking the winner we need to check all possible winning combinations:
- Line among rows (3 combinations)
- Line among columns (3 combinations)
- Line among diagonals (2 combinations)
Note: index = row * 3 + col
So for 1, we can check on each row if all 3 cells are same
On ith row, cells are: i*3+0, i*3+1, i*3+2 and they all should be same.
For 2, on ith column, cells are: 0*3+i, 1*3+i, 2*3+i and they all should be same.
Test these formulae/indexes out on these if you need to:
j=0 j=1 j=2
X | X | X O | X | X i=0 0 | 1 | 2
--------- --------- ---------
| O | O | O | i=1 3 | 4 | 5
--------- --------- ---------
| | X | | O i=2 6 | 7 | 8
Now we will create a function to check if there is a winner after each move
def check_winner(board: str):
# Check rows and columns
for i in range(3):
if board[i*3] == board[i*3+1] == board[i*3+2] != " ":
return board[i*3]
if board[i] == board[i+3] == board[i+6] != " ":
return board[i]
# Check diagonals
if board[0] == board[4] == board[8] != " ":
return board[0]
if board[2] == board[4] == board[6] != " ":
return board[2]
return None
2D list version (which we will not use in main code)
def check_winner(board):
# Check rows and columns
for i in range(3):
if board[i][0] == board[i][1] == board[i][2] != " ":
return board[i][0]
if board[0][i] == board[1][i] == board[2][i] != " ":
return board[0][i]
# Check diagonals
if board[0][0] == board[1][1] == board[2][2] != " ":
return board[0][0]
if board[0][2] == board[1][1] == board[2][0] != " ":
return board[0][2]
return None
2 player tictactoe game is now complete!!
Now we need to add the AI itself to play against us. (later against itself)
Checkpoint 2
We have our 2 player tictactoe game completed! This is how our main loop looks like now:
if __name__ == "__main__":
#game always starts with X
board = " " * 9
player = 1 # 1 = X, 0 = O
while True:
board, move = game_loop(board, "X" if player == 1 else "O")
winner = check_winner(board)
if winner:
print_board(board)
print(f"Player {winner} wins!")
break
player = 1 - player # Switch player
And this is the whole code:
def check_winner(board: str):
# Check rows and columns
for i in range(3):
if board[i*3] == board[i*3+1] == board[i*3+2] != " ":
return board[i*3]
if board[i] == board[i+3] == board[i+6] != " ":
return board[i]
# Check diagonals
if board[0] == board[4] == board[8] != " ":
return board[0]
if board[2] == board[4] == board[6] != " ":
return board[2]
return None
def print_board(board: str):
print(f"""
{board[0]} | {board[1]} | {board[2]}
---------
{board[3]} | {board[4]} | {board[5]}
---------
{board[6]} | {board[7]} | {board[8]}""")
def player_turn(board: str, player: str) -> tuple[str, int]:
# returns 2 values = updated board and position played
while True:
try:
num = int(input(f"Player {player}, enter the cell number (0-8): "))
if board[num] == " ": # check if cell is empty
board = board[:num] + player + board[num+1:]
return board, num
else:
print("That position is already taken. Try again.")
except (ValueError, IndexError): # valueeerror= not an int, indexerror= not in 0-8
print("Invalid input. Please enter numbers between 0 and 8.")
def game_loop(board, player):
print_board(board)
board, move = player_turn(board, player)
return board, move
if __name__ == "__main__":
#game always starts with X
board = " " * 9
player = 1 # 1 = X, 0 = O
while True:
board, move = game_loop(board, "X" if player == 1 else "O")
winner = check_winner(board)
if winner:
print_board(board)
print(f"Player {winner} wins!")
break
player = 1 - player # Switch player
Next Steps
In the next part, we will be writing some code to represent the matchboxes and beads, which means we will be generating all the 3^9 possible game states and then realising that we really only need 593 states (and get to the 304 matchbox count too that you might have read/seen)!
Also next part will be significantly harder than this.
Part 2 - MENACE Part 2: Building the Matchbox System and Generating Game States
