Tic Tac Toe ✨

Running Tic-Tac-Toe:

1. Make sure Python 3.6+ is installed.
3. Install requirements
``````    \$ pip install requirements.txt
``````
1. Running the program:
``````	\$ git clone https://github.com/krvaibhaw/tic-tac-toe.git
\$ cd tic-tac-toe
\$ python runner.py
``````

Introduction

To solve games using AI, we will introduce the concept of a game tree followed by minimax algorithm. The different states of the game are represented by nodes in the game tree, very similar to the above planning problems. The idea is just slightly different. In the game tree, the nodes are arranged in levels that correspond to each player's turns in the game so that the “root” node of the tree (usually depicted at the top of the diagram) is the beginning position in the game. In tic-tac-toe, this would be the empty grid with no Xs or Os played yet. Under root, on the second level, there are the possible states that can result from the first player’s moves, be it X or O. We call these nodes the “children” of the root node.

Each node on the second level, would further have as its children nodes the states that can be reached from it by the opposing player's moves. This is continued, level by level, until reaching states where the game is over. In tic-tac-toe, this means that either one of the players gets a line of three and wins, or the board is full and the game ends in a tie.

What is Minimax?

Minimax is a artificial intelligence applied in two player games, such as tic-tac-toe, checkers, chess and go. This games are known as zero-sum games, because in a mathematical representation: one player wins (+1) and other player loses (-1) or both of anyone not to win (0).

How does it works?

The algorithm search, recursively, the best move that leads the Max player to win or not lose (draw). It consider the current state of the game and the available moves at that state, then for each valid move it plays (alternating min and max) until it finds a terminal state (win, draw or lose).

Understanding the Algorithm

The algorithm was studied by the book Algorithms in a Nutshell (George Heineman; Gary Pollice; Stanley Selkow, 2009). Pseudocode (adapted):

``````minimax(state, depth, player)

if (player = max) then
best = [null, -infinity]
else
best = [null, +infinity]

if (depth = 0 or gameover) then
score = evaluate this state for player
return [null, score]

for each valid move m for player in state s do
execute move m on s
[move, score] = minimax(s, depth - 1, -player)
undo move m on s

if (player = max) then
if score > best.score then best = [move, score]
else
if score < best.score then best = [move, score]

return best
end
``````

Where,

• state: the current board in tic-tac-toe (node)
• depth: index of the node in the game tree
• player: may be a MAX player or MIN player

The Python implementation of initial state, i.e. the initial state of the board. First of all, consider it:

```def initial_state():

return [[EMPTY, EMPTY, EMPTY],
[EMPTY, EMPTY, EMPTY],
[EMPTY, EMPTY, EMPTY]]```

Both players start with your worst score. If player is MAX, its score is -infinity. Else if player is MIN, its score is +infinity. Note: infinity is an alias for inf (from math module, in Python).

```if player(board) == X:
value = -math.inf

elseif player(board) == o:
value = math.inf```

If the depth is equal zero, then the board hasn't new empty cells to play. Or, if a player wins, then the game ended for MAX or MIN. So the score for that state will be returned.

```def utility(board):

if winner(board) == 'X':
return 1

elif winner(board) == 'O':
return -1

else:
return 0```
• If MAX won: return +1
• If MIN won: return -1
• Else: return 0 (draw)

The action function will take the board as input and returns set of all possible actions (i, j) that are available on the board for the player to place his/her marker on.

```def actions(board):

possible_actions = []

for i in range(3):
for j in range(3):
if board[i][j] == EMPTY:
possible_actions.append((i,j))

return possible_actions```

For MAX player, a bigger score will be received. For a MIN player, a lower score will be received. And in the end, the best move is returned. It will loop through all the possible actions to find the optimal action and take it. Final algorithm:

```def minimax(board):

if terminal(board):
return None

move = None

alpha = -math.inf
beta = math.inf

if player(board) == X:
value = -math.inf

for action in actions(board):
updated_value = minmax_values(result(board, action),alpha, beta, O)

alpha = max(value, updated_value)

if updated_value > value:

value = updated_value
move = action

else:
value = math.inf

for action in actions(board):
updated_value = minmax_values(result(board, action),alpha, beta, X)

beta = min(value, updated_value)

if updated_value < value:

value = updated_value
move = action

return move```

Feel free to follow along the code provided along with mentioned comments for
better understanding of the project, if any issues feel free to reach me out.

Contributing

Contributions are welcome!
Please feel free to submit a Pull Request.

You might also like...

Adventure Game 🌇 This is a Adventure Game which is created using Python. Featur

A very bad wordle solver to help me solve the daily wordle

Wordle Solver A very bad wordle solver to help me solve the daily wordle on https://www.powerlanguage.co.uk/wordle/ TODO list take into account letter

A small script to help me solve Wordle because I'm that lazy

Wordle Solver A small script to help me solve Wordle because I'm that lazy. Warning: I didn't write this to be efficient nor elegant at all, so you'll

A python script to solve Wordle puzzles

Wordle solver A python script to solve Wordle puzzles.

Attempts to solve Wordle-like puzzles.

Attempts to solve Wordle-like puzzles.

Chess turnament organizer (short construct concept)

Turnament Organizer Chess turnament organizer (short construct concept). It is my hobby app I want to write to support lightweight tool for smart roun

learn and have fun developing 2D retro games using python and pygame

Retro 2D Game Development Using Python + PyGame Skill up your programming skills with a walk down the memory lane. Learn how to create a retro 2D game

Several implementations of classical games (ex: FlappyBird, Minesweeper etc.) using Python (pygame)

Mini Games with Pygame This projects implement several classic and popular games in Python, using python package -- pygame. Currently, 4 games are alr

Finding a method to objectively quantify skill expression in games, using reinforcement learning

Analyzing Skill Expression in Games This is a repo where I describe a method to measure the amount of skill expression games have. Table of Contents M

Vaibhaw
A passionate thinker, techno freak, comic lover, a curious computer engineering student. Machine Learning, Artificial Intelligence, Linux, Web Development.
A Gomoku game GUI using pygame where the user can choose to play against another player or an AI using minimax with alpha-beta pruning

Gomoku A GUI based Gomoku game using pygame where the user can choose to play against another player or an AI using minimax with alpha-beta pruning. R

1 Oct 30, 2021
A launcher to launch games from Riot Games under Linux

rito-launcher A launcher to launch games from Riot Games under Linux Requirements: Python 3, with the following pip plugins: 'configparser, pathlib, w

6 Mar 7, 2022
Datamining of 15 Days of (free) Games at the Epic Games Store (EGS).

EGS: 15 Days of Games This repository contains Python code to data-mine the 15 Days of (free) Games at the Epic Games Store (EGS). Requirements Instal

9 Dec 27, 2022
Algorithm to solve Wordle correctly 100% of the time within 6 attempts.

WordleSolver © Zulkarnine, 2022. Algorithm to solve Wordle 100% of the time within 6 attempts. You can go ahead and run main.py to run it for all 2315

69 Dec 11, 2022
Launch any Heroic-Games-Launcher game using bash scripts without having to open Heroic.

HeroicBashLauncher Ever wanted to launch your EGS games installed through Heroic Games Launcher directly from the terminal, Lutris or any other fronte

288 Dec 27, 2022
Blender Game Engine Game Type Templates Logic Bricks (and Python script) based Game Templates for Blender

Blender-Game-Engine-Templates Blender Game Engine Game Type Templates Logic Bric

3 Oct 25, 2022
An algorithm to reach a correlated equilibrium in multiplayer games.

Correlatedpy: a python library for distributed learning of correlated equilibrium in multiplayer strategic games. View Demo · Report Bug · Request Fea

2 Feb 1, 2022