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
Simple game where you try to survive as long as you can on screen.

Survival Game Simple game where you try to survive as long as you can on screen. Play To run, download the code and run the survival_game.py file. Fro

Logan Morris 1 Feb 10, 2022
A small, Pygame-based library project intended for personal use.

EzyGame Version 0.0.1 A simple library project intended for personal use with Pygame. Warning: I am a very amateur programmer, so the code will probab

Dorbell 1 Jan 08, 2022
Creates a landscape with more accurate river generation in Minecraft version 1.12 using python.

MinecraftLandRiverGen View the following youtube video to set up a world that can interact with the python programs

23 Dec 25, 2022
The repository that hosts the code that teaches a reinforcement learning - based bot to play 2048

The repository that hosts the code that teaches a reinforcement learning - based bot (based on policy gradients method) to play 2048

Maxim Rud 1 Dec 16, 2021
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
CTF (Capture The Flag) started from DEFCON CTF, a competitive game among computer security enthusiasts

CTF Wiki 中文 English Welcome to CTF Wiki! CTF (Capture The Flag) started from DEFCON CTF, a competitive game among computer security enthusiasts, origi

CTF Wiki 6.4k Jan 03, 2023
Brax is a differentiable physics engine that simulates environments made up of rigid bodies, joints, and actuators

Brax is a differentiable physics engine that simulates environments made up of rigid bodies, joints, and actuators. It's also a suite of learning algorithms to train agents to operate in these enviro

Google 1.5k Dec 31, 2022
Tic-Tac-Toe - Tic-Tac-Toe game build With Python

Tic Tac Toe This game is very popular amongst all of us and even fun to build as

PyLaboratory 0 Feb 06, 2022
This is a simple game made using pygame.

Ball breaker This is a simple game made using pygame game view The game view have been updated wait for the new view to be uploaded Game_show.mp4 Lear

Rishikesh Kumar 3 Nov 05, 2021
Jogo Flappy Bird com phyton e phygame

Flappy-Bird Tecnologias usadas Requisitos para inicializar o jogo: Python faça o download em: https://www.python.org/ Pygame faça o download em: https

João Guilherme 1 Dec 06, 2021
A stat tracker for the bedwars hypixel game in python

A hypixel bedwars stat tracker. Features Get stats in your current lobby Get stats in a guild Installation & Configuration git clone https://github.co

Le_Grand_Mannitout 3 Dec 25, 2021
Hagia is a 2D game engine and toolset for Python.

HAGIA What is Hagia? Hagia is a 2D game engine and toolset for Python. Hagia has

star 3 Jun 01, 2022
For the Exapunk minigame, ПАСЬЯНС

Exapunks Automation This repository solves Exapunk's Solitaire minigame, ПАСЬЯНС. This repository is useable, but only with specific display condition

Will C 5 Jul 29, 2022
Chess-commandline - Chess in the Command Line using the Chess Module Can detect Checkmates

chess-commandline Chess in the Command Line using the Chess Module Can detect Ch

Harry Hopkinson 1 Jan 10, 2022
WordleHelper suggests words to help players better enjoy the hit game Wordle

WordleHelper Introduction WordleHelper suggests words to help players better enjoy the hit game Wordle. Both the general mode and the hard mode are su

Shao-Yu, Chu 5 Jun 02, 2022
This project is an exciting fun game for beginners to build up

This project is an exciting fun game for beginners to build up. The program generates a random number from 1 to 10, or 1 to 100 any range that is specified and the user must guess the number after a

PyLaboratory 0 Feb 07, 2022
Rock-Paper-Scissors - Rock Paper Scissors With Python

Rock-Paper-Scissors The familiar game of Rock, Paper, Scissors is played like th

Lateefah Ajadi 0 Jan 15, 2022
🕹️ Jeu Azul en Python avec 4 IAs 🤖 implémentées, jouable de 1 à 4 joueurs

Projet jeu Azul 🕹️ Jeu Azul en Python avec 4 IAs 🤖 implémentées, jouable de 1 à 4 joueurs Par : Berachem MARKRIA et Tristan MARTINEZ Projet réalisé

Berachem Markria 2 Jun 07, 2022
Netskrafl - an Icelandic crossword game website

Netskrafl - an Icelandic crossword game website English summary This repository contains the implementation of an Icelandic crossword game in the genr

Miðeind ehf 30 May 09, 2022
2d war game single player

WarGame-third-version-0.0.4- 2d war game single player Hi ! Today, I publish on GitHub the version 0.0.4 of "WarGame". In this version, you can find a

Edouard Vincent 2 Apr 08, 2022