MENACE Part 2 - Generating all board states and optimizing by removing invalid and symmetric states
Programming MENACE (A Reinforcement Learning AI) that learns to play tic-tac-toe using matchboxes and beads. Generation of states and optimization by removing invalid and symmetric states.
Part 1 - Introduction to MENACE and setting up the project
We need to generate all possible board states for tic-tac-toe and then remove the invalid and symmetric states to optimize our AI’s learning process. These will act as labels on the matchboxes so we can change the number of beads (the moves we play next time on the current state) based on the result of the game.
This is the general plan for the whole project:
- We create an AI class for all the AI logic.
- Save every move played in a game (to reward/punish later) using lists.
- Create all possible board states and initialize matchboxes for them
- After each game, reward/punish the moves played based on win/draw/loss
- Integrate the AI to play against human
- Make the AI play against itself to train
And somewhere in the middle we need a system to save whatever it learnt and load back on startup; also need to optimize the matchbox storage so that we dont store symmetric board states separately (since they are equivalent).
Let us start with item 3.
Generating all possible board states
I will show 3 methods
Need to create all possible combinations of X, O, and empty spaces in a 3x3 grid = (3 possibilities)^(9 positions) = 19683 states
Method 1: Iterative approach using loops
def generate_all_boards():
boards = []
for i in range(3**9): # total 3^9 combinations
# you remember how you did this modulus and floor division thingy to convert decimal to other bases? This is the same, we are converting i to base 3 and mapping 0->X, 1->O, 2->" "
board = ""
num = i
for _ in range(9):
rem = num % 3
if rem == 0:
board += "X"
elif rem == 1:
board += "O"
else:
board += " "
num //= 3
boards.append(board)
return boards
Method 2: Recursive approach
Here we will use recursion to fill the board position by position. At each position we will try all 3 possibilities and then call the function recursively for the next position.
def fill_board(board, index, boards):
board = board.copy()
if index == 9: # index 9 is out of bounds. we had 0-8 index. So we have permuted all positions
return
for symbol in ["X", "O", " "]:
board[index] = symbol # change current index to symbol (create a permutation)
boards.append("".join(board)) # make it into string and add to boards permutation lists
fill_board(board, index + 1, boards) # now we permute at the next index
def generate_all_boards():
boards = []
board = [" "] * 9 # we init with empty, then at index we permute the possibilities
fill_board(board, 0, boards) # permute at index 0 initially
return boards
We start with index 0, try X, O, “ “ at index 0 one by one. For each of these, we call the function recursively for index 1.
At index 1, we again try X, O, “ “ one by one. For each of these, we call the function recursively for index 2.
BUT it doesnt work the same way as it looks.
This is how all the permutations are generated:
" " -> "X " -> "XX " -> "XXX " -> … -> "XXXXXXXXX" -> (then here index 9 so stop)
"XXXXXXXXX" -> "XXXXXXXXO" -> "XXXXXXXX " -> (then here index 9 so stop)
"XXXXXXXX " -> "XXXXXXXO " -> "XXXXXXXOX"” -> "XXXXXXXOO" -> "XXXXXXXO " -> (then here index 9 so stop)
"XXXXXXXO " -> "XXXXXXX " -> … and so on
It’s fine if you weren’t able to follow. Just look at the following simplified animation: (simplification = 2 positions instead of 9, and I’ve marked blank as B for better visibility)
These are the generated states (return value of the leaves) 
Method 3: Iterative using recursive relationships
Recurrence relation: (T = string of gamestates, n = number of moves made)
Base case: T(0) = ""
T(n) = T(n-1) + " "
= T(n-1) + "X"
= T(n-1) + "O"
We end at n = 9. So loop with 9 iterations
Code:
Technically this is recursion too, just another version that uses loops instead of function calls. Also more memory efficient than method 2. (i like this one)
def generator(possibilities):
states = []
for possibility in possibilities:
states.extend([possibility + " ", possibility + "X", possibility + "O"]) # for each existing state, just add 3 possibilities of the new next character.
return states
def generate_all_states():
all_states = [""]
for _ in range(9):
all_states = generator(all_states) # run 9 times to add 9 characters
return all_states
Removing invalid and symmetric states
Note that this is simply an optimization step to reduce the number of matchboxes we need to store and to make the AI learn a lot quicker. We can skip this step and just have MENACE learn all states but that would be inefficient. MENACE will anyway skip invalid boards since it will never encounter them.
You can skip this section and still have the AI work, just slower.
Note that doing anything with these roations is a bit tricky so take your time to understand it.
Invalid states
Out of these 3^9 states, there are many that we will never encounter. The following are invalid states:
- States where the difference between number of X’s and O’s is more than 1 (since players alternate turns)
- States where O has more X’s than O’s (since X always starts first)
- States where both X and O have winning lines (impossible in a real game)
- Already won. Nothing to learn in here and game stops at this.
Here are some examples of invalid states:
X | X | X O | X | X
--------- ---------
| O | | O |
--------- ---------
| | | | O
Condition 1 and 2 can be checked together by the condition: if ((count_X - count_O) > 1 OR (count_O > count_X)) then reject
Condition 3 can be checked by using the check_winner function modified to count how many conditions within it are met. Note that 2 of X or O winning lines are possible.
BUT 2 of X parallel winning lines are impossible since the game would have ended on the first winning line. AND if you do that even then you have 6X and at max 3Os which anywaty violates condition 1.
But if we simlpy implement condition 4 then we never had to think all this, nothing to learn in already won states. No double win needed to be considered.
Code for 1 and 2:
def filter_game_states():
all_states = generate_all_states()
#remove all where (number of X) - (number of O) > 1 since we can only have alternating moves and X always starts
# we can just make a new list that only has valid states
new_all_states = []
for state in all_states:
if 1 >= (state.count("X") - state.count("O")) >= 0:
new_all_states.append(state)
Code for 3 and 4:
I will just add this to check if any of the state is a winner
if check_winner(state):
continue
Like this:
def filter_game_states():
all_states = generate_all_states()
#remove all where (number of X) - (number of O) > 1 since we can only have alternating moves and X always starts
# we can just make a new list that only has valid states
new_all_states = []
for state in all_states:
if 1 >= (state.count("X") - state.count("O")) >= 0:
new_all_states.append(state)
all_states = new_all_states
unique_states = [] # we add all non winning valid states here
for state in all_states:
if check_winner(state):
continue # skip already won states
unique_states.append(state) # add if not already won
return unique_states
Why remove symmetric states?
Many board states are symmetric to one another (rotations and mirror images). We can remove these symmetric states by picking a state one at a time, generating all its rotations and mirrored versions, and then checking if any of those already exist in new_states. IF not we add them.
but why even care?
Would you agree all these states are equivalent?
X | O | O X | | X O | O | X
--------- --------- ---------
| O | X | O | O | O |
--------- --------- ---------
X | X | | | O | X | X
2nd one is a clockwise 90 deg rotation of 1st one
3rd one is a mirror image of 1st one along y axis
But in all of them, player X just need to play the same move (same to us humans - complete the X line).
Wouldn’t you be mad if the AI wins in one of them but then plays dumb in the other? I would (especially after all this coding).
So just training the AI on one of these should teach it how to handle ALL of them.
This is why we remove equivalent symmetric states. And later when we find these during a game, we convert these states by rotations or reflections to match one of these for picking the move and later training.
Removing symmetric states
We first need to find out a way to rotate a board and mirror it too.
Let us see how the rotated board looks like:
Original indexes: 0 1 2
3 4 5
6 7 8
Rotated indexes: 6 3 0
(Clockwise) 7 4 1
8 5 2
Mirror along y-axis indexes:
2 1 0
5 4 3
8 7 6
Mirror along x-axis indexes:
6 7 8
3 4 5
0 1 2
We can have mathematical fomulaes here too, like you can just transpose+reverse every row to rotate 90deg anticlockwise but that is more complex to code and understand. (especially combining the fact that we are not working with a 2D array but a 1D string so we need to use that index = f(i,j) formula earlier)
The simplest way of rotating i can see is to create an index map for each transformation and then use that to create the new string.
What do i mean by that? look at this:
sample = "ABCDE" # original index: 01234
index_map = [4,3,2,1,0] # this is reversed original index
reversed_string = ''
for index in index_map:
reversed_string += sample[index]
# we are getting indexes from index_mapm getting the corresponding character from sample string and adding to new string
print(reversed_string) # prints EDCBA
# another example, with the compressed for loop and a <str>.join(<iterable>) method
index_map2 = [1,0,2,3,4] # interchange first 2 characters
swapped_string = ''.join([sample[index] for index in index_map2])
print(swapped_string) # prints BACDE
We can use the same for rotations. We already have the index maps from the rotated board I showed above.
original_board = [0,1,2,3,4,5,6,7,8]
rotated_board = [6,3,0,7,4,1,8,5,2]
x_mirrored_board = [6,7,8,3,4,5,0,1,2]
y_mirrored_board = [2,1,0,5,4,3,8,7,6]
We can now use these index maps to generate all similar states (rotations and mirror images) of a given board state.
Why didnt i make maps for 180 and 270 deg rotations? Because we can just keep rotating the 90 deg rotated board again and again to get those.
Rotation of board again and again:
original_board = "XOX OX "
to_rotate = original_board # just renaming. this does not make a copy and it will change original_board too. (remember pointers from C? both of these vars point to the same list in memory)
print(to_rotate)
for _ in range(3):
to_rotate = [to_rotate[index] for index in rotated_board]
print(to_rotate)
This prints all 4 rotations of the original board.
We similarly can do for mirrored boards too.
Let us implement this. For every state, we generate all its similar states and check if any of those already exist in unique_states. If not we add them.
def filter_game_states():
all_states = generate_all_states()
# ---
new_all_states = []
for state in all_states:
if 1 >= state.count("X") - state.count("O") >= 0:
new_all_states.append(state)
all_states = new_all_states
# ---
# By the way, all the code in the above block wrapped by these "---" can be written in one line as:
# all_states = [state for state in all_states if 0 <= state.count("X") - state.count("O") <= 1]
# I wont actually use that in the explanation further so you can ignore this fact if too complex
#remove rotations and mirrored states.
# For this we pick a state one at a time, generate all its rotations and mirrored versions, and then check if any of those already exist in new_states. IF not we add them.
unique_states = []
index_map = [6,3,0,7,4,1,8,5,2] # 90 deg rotated indexes. we can repeat this rotation again and again for every rotation.
mirror_y_map = [2,1,0,5,4,3,8,7,6] # mirrored indexes along y axis
mirror_x_map = [6,7,8,3,4,5,0,1,2] # mirrored indexes along x axis
for state in all_states:
# If already won, skip. Dont waste processing time.
if check_winner(state):
continue
# make mirror images
y_mirror = ''.join([state[index] for index in mirror_y_map])
x_mirror = ''.join([state[index] for index in mirror_x_map])
similar_states = [state, x_mirror, y_mirror]
# generate rotations (90 deg at a time)
to_rotate = state
to_rotate_y = y_mirror
to_rotate_x = x_mirror
for _ in range(3):
to_rotate = ''.join([to_rotate[index] for index in index_map])
to_rotate_y = ''.join([to_rotate_y[index] for index in index_map])
to_rotate_x = ''.join([to_rotate_x[index] for index in index_map])
similar_states.append(to_rotate)
similar_states.append(to_rotate_y)
similar_states.append(to_rotate_x)
# check if any of the similar states already exist in unique_states
for item in similar_states:
if item in unique_states:
break
else:
unique_states.append(state) #if none matches then for loop is not broken and the state is added (for-else loop)
return unique_states
How do we know this is right?
We do know that the original guy got 304 matchboxes after all this. Let us try to get that number after applying his extra conditions. Conditions he had that we did not implement:
- Only X plays. (we added both X and O)
- Ignore states where we only have 1 empty cell left (since game would end before that) [we didnt do this because we would anyway have only 1 bead in there so it wouldnt matter at all]
For 1, we say that after O plays, there is always equal number of Xs and Os.
For 2, we can make sure that number of " " (blanks) are more than 1.
We change
if 1 >= state.count("X") - state.count("O") >= 0:
to
if (state.count("X") - state.count("O")) == 0 and state.count(" ") > 1:
Full code for filtering invalid states with these 2 extra conditions (i will run this, you can run this too in a whole new file)
def generator(possibilities):
states = []
for possibility in possibilities:
states.extend([possibility + " ", possibility + "X", possibility + "O"])
return states
def generate_all_states():
# all game states in string format
# Recurrence relation: (T = string of gamestates, n = number of moves made)
# Base case: T(0) = ""
# T(n) = T(n-1) + " "
# = T(n-1) + "X"
# = T(n-1) + "O"
# We end at n = 9. So loop with 9 iterations
# this will give us all possible combinations of X, O, and empty spaces in a 3x3 grid = (3 possibilities)^(9 positions) = 19683 states
all_states = [""]
for _ in range(9):
all_states = generator(all_states)
return all_states
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 filter_game_states():
all_states = generate_all_states()
new_all_states = []
for state in all_states:
if (state.count("X") - state.count("O")) == 0 and state.count(" ") > 1:
new_all_states.append(state)
all_states = new_all_states
#remove rotations and mirrored states.
# For this we pick a state one at a time, generate all its rotations and mirrored versions, and then check if any of those already exist in new_states. IF not we add them.
unique_states = []
index_map = [6,3,0,7,4,1,8,5,2] # 90 deg rotated indexes. we can repeat this rotation again and again for every rotation.
mirror_y_map = [2,1,0,5,4,3,8,7,6] # mirrored indexes along y axis
mirror_x_map = [6,7,8,3,4,5,0,1,2] # mirrored indexes along x axis
for state in all_states:
# If already won, skip. Dont waste processing time.
if check_winner(state):
continue
# make mirror images
y_mirror = ''.join([state[index] for index in mirror_y_map])
x_mirror = ''.join([state[index] for index in mirror_x_map])
similar_states = [state, x_mirror, y_mirror]
# generate rotations (90 deg at a time)
to_rotate = state
to_rotate_y = y_mirror
to_rotate_x = x_mirror
for _ in range(3):
to_rotate = ''.join([to_rotate[index] for index in index_map])
to_rotate_y = ''.join([to_rotate_y[index] for index in index_map])
to_rotate_x = ''.join([to_rotate_x[index] for index in index_map])
similar_states.append(to_rotate)
similar_states.append(to_rotate_y)
similar_states.append(to_rotate_x)
# check if any of the similar states already exist in unique_states
for item in similar_states:
if item in unique_states:
break
else:
unique_states.append(state) #if none matches then for loop is not broken and the state is added (for-else loop)
return unique_states
if __name__ == "__main__":
print(len(filter_game_states()))
AND… The output:
(menace-py3.12) ankit@LAPTOP-T90NGO2F:~/python/MENACE$ python3 menace.py
304
Yay!
And actually adding condition 2 is pretty nice; i couldnt think about it before i went around searching why my count was 338 prior to this, so i will keep the condition 2, the blanks > 1, (see the filtering code below to see) but then reintroduce both X and Os
Here is my current code for filtering invalid states
def filter_game_states():
all_states = generate_all_states()
#remove all where (number of X) - (number of O) > 1 since we can only have alternating moves and X always starts
# same as generating a new list with only valid states
all_states = [state for state in all_states if 0 <= state.count("X") - state.count("O") <= 1 and state.count(" ") > 1]
#remove rotations and mirrored states.
# For this we pick a state one at a time, generate all its rotations and mirrored versions, and then check if any of those already exist in new_states. IF not we add them.
unique_states = []
index_map = [6,3,0,7,4,1,8,5,2] # 90 deg rotated indexes. we can repeat this rotation again and again for every rotation.
mirror_y_map = [2,1,0,5,4,3,8,7,6] # mirrored indexes along y axis
mirror_x_map = [6,7,8,3,4,5,0,1,2] # mirrored indexes along x axis
for state in all_states:
# If already won, skip. Dont waste processing time.
if check_winner(state):
continue
# make mirror images
y_mirror = ''.join([state[mirror_y_map[i]] for i in range(9)])
x_mirror = ''.join([state[mirror_x_map[i]] for i in range(9)])
similar_states = [state, x_mirror, y_mirror]
# generate rotations (90 deg at a time)
to_rotate = state
to_rotate_y = y_mirror
to_rotate_x = x_mirror
for _ in range(3):
to_rotate = ''.join([to_rotate[index_map[j]] for j in range(9)])
to_rotate_y = ''.join([to_rotate_y[index_map[j]] for j in range(9)])
to_rotate_x = ''.join([to_rotate_x[index_map[j]] for j in range(9)])
similar_states.append(to_rotate)
similar_states.append(to_rotate_y)
similar_states.append(to_rotate_x)
# check if any of the similar states already exist in unique_states
for item in similar_states:
if item in unique_states:
break
else:
unique_states.append(state) #if none matches then for loop is not broken and the state is added (for-else loop)
return unique_states
if __name__ == "__main__":
print(len(filter_game_states()))
Now we need to map it to matchboxes and initialize beads in them.
We can use a dictionary for this purpose. Also accessing a dictionary item is O(1) on average due to hashmaps (meaning fast regardless of number of items stored) unlike lists where searching is O(n) (meaning time taken increases linearly with number of items stored).
Also rehashing cost does not negate the O(1) since we max only add approx 600 items and we access its items more than that.
If we want to exploit this speed in the filtering thing too then we could’ve made a dict rather than a list for unique_states and then just do if item in unique_states_dict:and also we would already have a dict so no need to convert to dict later; but since this is a one time operation and we have only 304 items, it doesnt matter much. I would do it but imagine spending a minute on this optimisation that saves a little time once a while
Actually let me do that. If we time our current code with:
if __name__ == "__main__":
import time
start_time = time.time()
print(len(filter_game_states()))
print(f"Time taken: {time.time() - start_time} seconds")
We get this time:
(menace-py3.12) ankit@LAPTOP-T90NGO2F:~/python/MENACE$ python3 menace.py
593
Time taken: 0.3060119152069092 seconds
AND.. if we change the definition of unique_states = [] to unique_states = {} and then change the code to add items to dict rather than list like this:
for item in similar_states:
if item in unique_states:
break
else:
unique_states[state] = True #if none matches then for loop is not broken and the state is added (for-else loop)
Then we get this time:
(menace-py3.12) ankit@LAPTOP-T90NGO2F:~/python/MENACE$ python3 menace.py
593
Time taken: 0.06501245498657227 seconds
NICE!
I wonder what happens when we use sets for both unique_states and similar_states since we dont care about order and we just want to check if any of the similar states are in unique states. I will leave that as an exercise for you. (hint: you can use set intersection to check if any of the similar states are in unique states and get rid of one of the for loops.)
Answer: You do get another speedup! Time now was 0.015 seconds for one of the runs.
You can message me if you need the code and cant change yourself
I will keep the dictionary version since it is convenient for the next steps.
Hotfix:
Forgot to add detection for draw games. Modify check_winner() function to return “Draw” if there are no blank spaces left and no winner. And then in the main loop, we check for draw too and break the loop if it is a draw.
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]
if board.count(" ") == 0:
return "draw"
return None
Main loop:
if __name__ == "__main__":
#game always starts with X
ai = AI()
board = " " * 9
player = 1 # 1 = X, 0 = O
while True:
board, move = game_loop(board, "X" if player == 1 else "O")
result = check_winner(board)
if result:
print_board(board)
if result == "draw":
print("draw!")
else:
print(f"Player {result} wins!")
break
player = 1 - player # Switch player
