/Automated-TicTacToe

A Simple program which enables the user to play TicTacToe with the computer

Primary LanguagePythonMIT LicenseMIT

Automated TicTacToe

A Program which allows user to play tic-tac-toe against the computer. The project was completed as a part of CS50 AI course. The Files runner.py (including but not limited to GUI implementation) and OpenSans-Regular.ttf was provided by the instructing team, however tictactoe.py which contains the logic which the computer uses has been implemented by me (@infinitecoder1729).

To Run the program :

  1. Download the program files at this link and unzip or make a clone of the repo on local machine using git clone https://github.com/infinitecoder1729/Automated-TicTacToe.git
  2. Open the folder containing the files in terminal cd <The path of folder here> and run the python runner.py or python3 runner.py

Explanation of Logic implmented in tictactoe.py :

Automated-TicTacToe/tictactoe.py

Lines 7 to 9 in 6d46781

X = "X"
O = "O"
EMPTY = None

These are constants used to represent players in the Tic Tac Toe game. X and O are used to identify the players, and EMPTY is used to indicate an empty cell on the game board.

Automated-TicTacToe/tictactoe.py

Lines 12 to 18 in 6d46781

def initial_state():
"""
Returns starting state of the board.
"""
return [[EMPTY, EMPTY, EMPTY],
[EMPTY, EMPTY, EMPTY],
[EMPTY, EMPTY, EMPTY]]

The initial_state() function returns a 3x3 list representing the initial state of the Tic Tac Toe board, where all cells are empty.

Automated-TicTacToe/tictactoe.py

Lines 21 to 43 in 6d46781

def player(board):
"""
Returns player who has the next turn on a board.
"""
countX=0
countO=0
countEmpty=0
for i in board:
for j in i:
if j==X:
countX+=1
elif j==O:
countO+=1
else :
countEmpty+=1
if countX>countO:
return O
elif countEmpty==9:
return X
elif countX==countO:
return X
else :
return None

The player(board) function determines which player has the next turn based on the current state of the board. It counts the number of Xs, Os, and empty cells on the board to make this decision. If X has played more moves than O, it's O's turn. If the board is empty, it's X's turn. Otherwise, if X and O have played the same number of moves, it's X's turn. If the board is full (no empty cells), the function returns None.

Automated-TicTacToe/tictactoe.py

Lines 46 to 55 in 6d46781

def actions(board):
"""
Returns set of all possible actions (i, j) available on the board.
"""
act=[]
for i in range(0,3):
for j in range(0,3):
if board[i][j]==EMPTY:
act.append((i,j))
return act

The actions(board) function returns a list of all possible moves (actions) that a player can make on the given board. It iterates over all cells of the board, and if a cell is empty (represented by EMPTY), it adds the cell coordinates (i, j) to the list of possible actions.

Automated-TicTacToe/tictactoe.py

Lines 58 to 65 in 6d46781

def result(board, action):
"""
Returns the board that results from making move (i, j) on the board.
"""
move=player(board)
new_board=deepcopy(board)
new_board[action[0]][action[1]]=move
return new_board

The result(board, action) function returns a new board that results from making a move (action) on the given board. It first determines the player making the move using the player() function, and then it creates a deep copy of the original board to avoid modifying it directly. It places the player's move at the specified action (i, j) on the new board and returns it.

Automated-TicTacToe/tictactoe.py

Lines 68 to 84 in 6d46781

def winner(board):
"""
Returns the winner of the game, if there is one.
"""
for mark in (X, O):
for row in board:
if row == [mark] * 3:
return mark
for i in range(3):
column = [board[x][i] for x in range(3)]
if column == [mark] * 3:
return mark
if [board[i][i] for i in range(0, 3)] == [mark] * 3:
return mark
elif [board[i][~i] for i in range(0, 3)] == [mark] * 3:
return mark
return None

The winner(board) function checks if there is a winner in the game. It does this by checking all rows, columns, and diagonals to see if they are occupied by the same player (X or O). If it finds a row, column, or diagonal where all cells have the same player's mark, it returns the mark of the player who won. If there is no winner, it returns None.

Automated-TicTacToe/tictactoe.py

Lines 87 to 98 in 6d46781

def terminal(board):
"""
Returns True if game is over, False otherwise.
"""
if winner(board) != None:
return True
for i in board:
for j in i:
if j==EMPTY:
return False
return True

The terminal(board) function checks if the game is over. It returns True if there is a winner (by calling winner(board)) or if the board is completely filled (no empty cells). Otherwise, it returns False.

Automated-TicTacToe/tictactoe.py

Lines 101 to 111 in 6d46781

def utility(board):
"""
Returns 1 if X has won the game, -1 if O has won, 0 otherwise.
"""
playerwin = winner(board)
if playerwin == X:
return 1
elif playerwin == O:
return -1
else:
return 0

The utility(board) function determines the utility value of the terminal state (i.e., the final outcome of the game) for the maximizing player (X). If X wins, it returns 1, if O wins, it returns -1, and if it's a draw, it returns 0.

Automated-TicTacToe/tictactoe.py

Lines 113 to 149 in 6d46781

def minimax(board):
"""
Returns the optimal action for the current player on the board.
"""
def maximum(board):
move=()
if terminal(board):
return utility(board),move
else:
min_thresh=-100
for act in actions(board):
mini=(minimum(result(board,act))[0])
if mini>min_thresh:
min_thresh=mini
move=act
return min_thresh,move
def minimum(board):
move=()
if terminal(board):
return utility(board),move
else:
max_thresh=100
for act in actions(board):
maxi=(maximum(result(board,act))[0])
if maxi<max_thresh:
max_thresh=maxi
move=act
return max_thresh,move
turn=player(board)
if terminal(board):
return None
if turn==O:
return minimum(board)[1]
elif turn==X:
return maximum(board)[1]
return None

The minimax(board) function uses two helper functions, maximum(board) and minimum(board), to implement the minimax algorithm. The minimax algorithm is a recursive search algorithm used for decision-making in two-player zero-sum games, such as Tic Tac Toe.

The maximum(board) function calculates the maximum utility value for the maximizing player (X). If the board is in a terminal state (i.e., the game is over), it returns the utility value and an empty move. Otherwise, it initializes a threshold min_thresh to a very low value and iterates over all possible actions (moves) that X can make on the board. For each action, it calls the minimum() function with the resulting board and obtains the minimum utility value that the minimizing player (O) can achieve. It then updates min_thresh and the corresponding move if the minimum utility value is greater than the current min_thresh. Finally, it returns the min_thresh (maximum utility value) and the corresponding move that X should make to achieve that maximum utility.

The minimum(board) function calculates the minimum utility value for the minimizing player (O). If the board is in a terminal state, it returns the utility value and an empty move. Otherwise, it initializes a threshold max_thresh to a very high value and iterates over all possible actions (moves) that O can make on the board. For each action, it calls the maximum() function with the resulting board and obtains the maximum utility value that the maximizing player (X) can achieve. It then updates max_thresh and the corresponding move if the maximum utility value is smaller than the current max_thresh. Finally, it returns the max_thresh (minimum utility value) and the corresponding move that O should make to achieve that minimum utility.

In the minimax(board) function, the variable turn is used to determine whose turn it is (X or O). If the board is in a terminal state, it returns None since no further moves can be made. If it's O's turn, it calls the minimum() function to find the best move for O and returns that move. If it's X's turn, it calls the maximum() function to find the best move for X and returns that move.

This way, the minimax(board) function allows the AI player to choose the best possible move based on the minimax algorithm, ensuring that it maximizes its chances of winning or minimizing its chances of losing the game. It explores all possible moves and outcomes recursively to make an informed decision.

Working :

2023-07-28.12-09-39_Trim.mp4