To solve games using AI, we will introduce the concept of a game tree followed by minimax algorithm.

Overview

Tic Tac Toe

forthebadge forthebadge forthebadge

Running Tic-Tac-Toe:

  1. Make sure Python 3.6+ is installed.
  2. Install Flask Web Framework.
  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.

Owner
Vaibhaw
A passionate thinker, techno freak, comic lover, a curious computer engineering student. Machine Learning, Artificial Intelligence, Linux, Web Development.
Vaibhaw
It just a cli based snake game written in Python.

Snake Game in Python Things that I learned in this project: OOP in Python. Clean code. The curses library. How to run the game You need to clone this

Kevin Marques 7 Oct 01, 2022
A bot that deletes any embeds sent by a tropical webhook containing hex #000000 rancher's boots

tropical-webhook-cleanup how to use download the source code as zip get your discord bot token from https://discord.com/developers/applications put yo

carreb 0 Nov 25, 2022
PyGame-Tutorial - Refrence for building games in pygame

PyGame-Tutorial How to build games using the python library PyGame End result Ho

St. Mark's Computer Science Club 2 Jan 09, 2022
Chess - A python gui application

Chess Python version 3.10 or greater is required to play. Note This is a gui application, and as such will not run inside WSL.

Jonxslays 1 Dec 16, 2021
Battle of Saiyans: Goku v Vegeta is a 1 v 1, (Player vs CPU) 2D Martial arts fighting game

Battle of Saiyans: Goku v Vegeta is a 1 v 1, (Player vs CPU) 2D Martial arts fighting game inspired by the popular anime series Dragon Ball Z The game

ARZ 3 Feb 16, 2022
For educational purposes, a simple script that assists in solving the word game Wordle.

WordleSolver For educational purposes, a simple script that assists in solving the word game Wordle. Instructions Pick your first word from the sugges

Christian De Leon 2 Mar 25, 2022
Quiz Game: answering questions naturally with a friendly UI to enjoy the game

About Quiz Game : The Game is about answering questions naturally with a friendl

4 Jan 19, 2022
AutoPilot is a game where the player controls a car and tries to get the highest score he can while not dying under falling cement blocks.

AutoPilot AutoPilot is a game where the player controls a car and tries to get the highest score he can while not dying under falling cement blocks. C

Enoc Mena 1 Nov 17, 2021
Solo CLF project about the creation of the FlickColor game in Python with very precise instructions.

Solo CLF project about the creation of the FlickColor game in Python with very precise instructions.

COZAX 1 Dec 09, 2022
A tool to design a planet for Galaxy Life Reborn game.

GLRBaseDesigner A program to design your planet for Galaxy Life Reborn game. Description Do you want to share your base design with friends? Now it's

jjay31 9 Dec 16, 2022
source codes for my(small indie game developer) games

My repository for most of my finished && unfinished games Table of Contents Getting Started Prerequisites Installation Usage License Contact Prerequis

Gustavs Jākobsons 1 Jan 30, 2022
This is a python bot to automate BombCrypto game

This is a python bot to automate BombCrypto game. Logs in to the game, reconnects when needed, closes error warnings, sends heroes to work or home automatically, has Telegram integration and lets you

AFKAPP 39 Sep 28, 2022
Game-of-life - A simple python program to simulate and visualise the Conway's Game of life

Conway's game of life A simple python program to simulate and visualise the Conw

Dhravya Shah 3 Feb 20, 2022
A simple yet powerful Snake Game made with myPygameWorkflow

snakeGame A simple yet powerful Snake Game made with myPygameWorkflow. Requirments python3 Python.org myPygameWorkflow Github Ripo Usage $ cd main $ p

DuskyElf 1 Dec 26, 2021
Script to remap minecraft 1.12 java classes.

Remapper Script to remap minecraft 1.12 java classes. Usage You must have Python installed. You must have the script, mappings, and files / folders in

8 Dec 02, 2022
🐍 Conway's Game of Life cellular automaton implemented in PyGame

Conway's Game of Life My PyGame implementation of Conway's Game of Life. This implementation involves treating all edges of the grid as stitched toget

Mateusz Żebrak 1 May 29, 2022
A Tetris Game for programming education

Tetris Game プログラミング学習を目的とした、ブロックを操作してスコアを競うゲームです。 FAQはこちら。 tutorialはこちら。 実行環境準備 Mac環境 Finder→Application→Utility→Terminalから、ターミナルを起動して以下コマンドを実行する。 # i

11 Dec 01, 2022
Repository containing documentation about the Minecraft Legacy FUI file structure

Repository containing documentation about the Minecraft Legacy FUI file structure

Miku-666 6 Dec 29, 2022
Tic Tac Toe Game build with Python

Tic Tac Toe Game Description two players who take turns marking the spaces in a three-by-three grid with X or O. The player who succeeds in placing th

Kemal Kochekov 2 Jan 21, 2022
It calculates the Nim sum of a nim game.

nim-sum-calculator It calculates the Nim sum of a nim game. The rules of Nim The traditional game of Nim is played with a number of coins arranged in

2 Jan 02, 2022