Program 1
Solve the Tic-Tac-Toe problem using the Depth First Search technique.
CODE:
import copy
# Constants
PLAYER_X = "X"
PLAYER_O = "O"
EMPTY = " "
def print_board(board):
for row in board:
print(" | ".join(row))
print("-" * 5)
def is_winner(board, player):
# Check rows, columns, and diagonals for a win
for row in board:
if all(cell == player for cell in row):
return True
for col in range(3):
if all(board[row][col] == player for row in range(3)):
return True
if all(board[i][i] == player for i in range(3)) or all(board[i][2 - i] == player for i in range(3)):
return True
return False
def is_draw(board):
return all(cell != EMPTY for row in board for cell in row)
def get_empty_cells(board):
empty_cells = []
for row in range(3):
for col in range(3):
if board[row][col] == EMPTY:
empty_cells.append((row, col))
return empty_cells
def dfs(board, player):
if is_winner(board, PLAYER_X):
return -1
if is_winner(board, PLAYER_O):
return 1
if is_draw(board):
return 0
best_score = -float('inf') if player == PLAYER_O else float('inf')
for row, col in get_empty_cells(board):
new_board = copy.deepcopy(board)
new_board[row][col] = player
score = dfs(new_board, PLAYER_X if player == PLAYER_O else PLAYER_O)
if player == PLAYER_O:
best_score = max(best_score, score)
else:
best_score = min(best_score, score)
return best_score
def best_move(board, player):
best_score = -float('inf') if player == PLAYER_O else float('inf')
move = None
for row, col in get_empty_cells(board):
new_board = copy.deepcopy(board)
new_board[row][col] = player
score = dfs(new_board, PLAYER_X if player == PLAYER_O else PLAYER_O)
if (player == PLAYER_O and score > best_score) or (player == PLAYER_X and score < best_score):
best_score = score
move = (row, col)
return move
# Main game loop
board = [
[EMPTY, EMPTY, EMPTY],
[EMPTY, EMPTY, EMPTY],
[EMPTY, EMPTY, EMPTY],
current_player = PLAYER_X
while True:
print_board(board)
if current_player == PLAYER_X:
row, col = map(int, input("Enter your move (row and column): ").split())
board[row][col] = PLAYER_X
else:
row, col = best_move(board, PLAYER_O)
board[row][col] = PLAYER_O
if is_winner(board, PLAYER_X):
print_board(board)
print("Player X wins!")
break
if is_winner(board, PLAYER_O):
print_board(board)
print("Player O wins!")
break
if is_draw(board):
print_board(board)
print("It's a draw!")
break
current_player = PLAYER_O if current_player == PLAYER_X else PLAYER_X
OUTPUT:
Explanations:
This script allows you to play a game of Tic-Tac-Toe against the computer, which uses the DFS
algorithm to determine the best move. The dfs function explores all possible moves and returns a
score based on the outcome. The best_move function uses these scores to choose the optimal move
for the computer.
DFS is a recursive algorithm to search all the vertices of a tree data structure or a graph. The depth
first search (DFS) algorithm starts with the initial node of graph G and goes deeper until we find the
goal node or the node with no children. Because of the recursive nature, stack data structure can be
used to implement the DFS algorithm.
Steps:
1. *Represent the Game State:*
- Represent the Tic-Tac-Toe board as a 3x3 grid.
- Each state can be represented as a string or a list of lists, e.g., [['X', 'O', ''], ['', 'X', ''], ['', '', 'O']].
2. *Generate Possible Moves:*
- From the current state, generate all possible next moves for the player (either 'X' or 'O').
3. *DFS Traversal:*
- Recursively explore each possible move until the game reaches a terminal state (win, lose, or
draw).
- Backtrack after reaching a terminal state.
4. *Evaluate Terminal States:*
- If the terminal state is a win for the current player, return a positive score.
- If it's a loss, return a negative score.
- If it's a draw, return a neutral score.
5. *Choose the Best Move:*
- For each possible move, evaluate the outcome using DFS and choose the move with the best
score
Thank You
Sonali Mishra
Assistant professor
ECE Department
