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
Minecraft clone using Python Ursina game engine!

Minecraft clone using Python Ursina game engine!

Taehee Lee 35 Jan 03, 2023
Repository with console python implementation of Simple Artificial Life (simplified MAS) and Conway's game of life

artificial-life-game Repository with console python implementation of Simple Artificial Life (simplified MAS) and Conway's game of life Installation c

Vladislav 6 Nov 14, 2022
Multi minecraft server helper for python

呐 Yuki 您的群组服操作小助手。 使用Python3编写。使用 .yaml 配置文件记录子服,配合Screen管理Linux系统上的Minecraft子服,支持MCDR子服与非MCDR子服。 功能: 开启所有子服 关闭所有子服 重载所有子服MCDR 重载所有子服ChatBridge 使用方法:

3 Mar 17, 2022
Online battleships game on python and JS

Battleships Online battleships game Using websockets to connect to the client. SQLite database for storing account data and game logs (for players top

5 Nov 11, 2021
AI plays games with python

AI-plays-games- To use it, you first need to create an img file and save the pic

Murat Ali Avcu 7 Oct 16, 2022
Useful tools for Minecraft worlds such as remove unused chunks, find blocks or entities.

Useful tools for Minecraft worlds such as removing unused chunks and finding blocks, command blocks or entities.

Rapha149 1 Feb 17, 2022
A very simple 3D maze game with ray tracing.

PytracingMaze MOST RECENT VERSION: Pytracing Maze.py Also, executable for Windows available on itch.io Simple ray tracing game in Python, based on my

FinFET 15 Dec 20, 2022
An open-world game made in Python.

Dragon Realms Notes Windows OS only Contributors This project follows the all-contributors specification (emoji key, command Issue). See what you can

Dragon Realms 2 Jul 28, 2022
pyLodeRunner - Classic Lode Runner clone made in pyxel (Python)

pyLodeRunner Classic Lode Runner clone made in pyxel (Python) Controls arrow key : move the player X : dig right side Z : dig left side ESC : quit gam

2 Feb 12, 2022
2D Minecraft Clone made with Python & Pygame & OpenGL

2D Minecraft Clone This is a 2D clone of the well-known game Minecraft made in Python using Pygame and ModernGL I started this mostly as a self-improv

Kadir Aksoy 2 Sep 25, 2022
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

Marcus Chiam 4 Nov 19, 2022
Overview: copain, your friendly AI framework to learn and play games

Overview: copain, your friendly AI framework to learn and play games Interface fceux with python and run reinforcement learning. Compatibility Current

fcharras 1 Dec 16, 2021
An interactive pygame implementation of Conway's Game of Life

Game of Life An interactive pygame implementation of Conway's Game of Life Installation Clone the repo and navigate into it. git clone https://github.

Ethan 1 Dec 05, 2021
Typing Game : from nob to good

Fast and Curious A game to learn/improve keyboard typing skills. The main idea is to improve your typing skills and at the same time learn fun facts (

Raffaele Fiorillo 7 Jun 13, 2022
The DOS game from the 80s re-written in Python from Scratch!

Drugwars The DOS game from the 80s re-written in Python from Scratch! Play in your browser Here Installation Recommended: Using pip pip3 install drugw

Max Bridgland 45 Jan 03, 2023
Adventure-Game - Adventure Game which is created using Python

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

ArinjoyTheDev 1 Mar 19, 2022
2DMC is an abrrieviation for 2 Dimensional Minecraft.

2DMC 2DMC is an abrrieviation for 2 Dimensional Minecraft. This idea is originally created and implemented by Griffpatch on Scratch. This is a persona

DaNub 5 Nov 06, 2022
Allows you to email people wordle spoilers. Very beta, not as many features

wordlespoiler Allows you to email people wordle spoilers. Very beta, not as many features How to Use 1.) Make a new gmail account. Go to settings (Man

0 Jan 04, 2023
The original Tetris tile-matching game as adopted by IBM PC.

🕹️ Tetris Game The original Tetris tile-matching game as adopted by IBM PC. Game developed purely on python using the Dear PyGui Framework. 📖 Instru

14 Nov 12, 2022
Disables the chat in League of Legends for Windows.

Disables the chat in League of Legends for Windows. If you simply can't stop yourself from typing LeagueStop will play KEKW.mp3 each time you try. The sound will stack & becomes horribly annoying.

1 Nov 24, 2021