Правила игры

На поле размером 3 на 3 по-очереди ходят два игрока. Один играет за '0', другой за 'Х'.

Ход заключается в размещении своего символа на любой свободной клетке доски. Побеждает тот, кто первый составит три своих символа в ряд: по вертикали, горизотали или диагонали.

Реализацию будем делать на python 3.

Поле будем представлять в виде списка списков:

board = [ [ '_', '_', '_' ], [ '_', '_', '_' ], [ '_', '_', '_' ] ]

'_' - пустая клетка
'x' - ход крестиком
'o' - ход ноликом

индексация с нуля. При обращении первый индекс это строка, второй столбец, например, board[row][col], board[0][1] - это нулевая строка второй столбец.

Для оценивания позиции в игре введем простую оценочную функцию, которая если есть три в ряд крестика, а значит победили крестики будет ровна 10, а если есть три в ряд нолика, -10. Если трех в ряд ни у кого нет, то оценка ровна 0.

На вход оценочной функции будет подаваться позиция в виде поля board.

def evaluate(b):
    player = 'x'
    opponent = 'o'
    for row in range(3):     
        if (b[row][0] == b[row][1] and b[row][1] == b[row][2]):        
            if (b[row][0] == player):
                return 10
            elif (b[row][0] == opponent):
                return -10
 
    for col in range(3) :      
        if (b[0][col] == b[1][col] and b[1][col] == b[2][col]):      
            if (b[0][col] == player):
                return 10
            elif (b[0][col] == opponent):
                return -10
 
    if (b[0][0] == b[1][1] and b[1][1] == b[2][2]):     
        if (b[0][0] == player):
            return 10
        elif (b[0][0] == opponent):
            return -10
 
    if (b[0][2] == b[1][1] and b[1][1] == b[2][0]):    
        if (b[0][2] == player):
            return 10
        elif (b[0][2] == opponent):
            return -10
 
    return 0

Полный пример кода.

#!/usr/bin/env python
# -*- coding: utf-8 -*
# tic_tac_toe_minimax.py
player, opponent = 'x', 'o'

def isMovesLeft(board) : 
    for i in range(3) :
        for j in range(3) :
            if (board[i][j] == '_') :
                return True
    return False
 
def evaluate(b) :
    for row in range(3) :     
        if (b[row][0] == b[row][1] and b[row][1] == b[row][2]) :        
            if (b[row][0] == player) :
                return 10
            elif (b[row][0] == opponent) :
                return -10
 
    for col in range(3) :      
        if (b[0][col] == b[1][col] and b[1][col] == b[2][col]) :      
            if (b[0][col] == player) :
                return 10
            elif (b[0][col] == opponent) :
                return -10
 
    if (b[0][0] == b[1][1] and b[1][1] == b[2][2]) :     
        if (b[0][0] == player) :
            return 10
        elif (b[0][0] == opponent) :
            return -10
 
    if (b[0][2] == b[1][1] and b[1][1] == b[2][0]) :    
        if (b[0][2] == player) :
            return 10
        elif (b[0][2] == opponent) :
            return -10
 
    return 0
 
def minimax(board, depth, isMax):
    score = evaluate(board)
    if (score == 10):
        return score
    if (score == -10):
        return score 
    if (isMovesLeft(board) == False):
        return 0
 
    if (isMax):     
        best = -1000
        for i in range(3) :         
            for j in range(3) :
                if (board[i][j]=='_') :
                    board[i][j] = player 
                    best = max(best, minimax(board, depth + 1, not isMax))
                    board[i][j] = '_'
        return best
 
    else :
        best = 1000 
        for i in range(3) :         
            for j in range(3) :
                if (board[i][j] == '_') :
                    board[i][j] = opponent 
                    best = min(best, minimax(board, depth + 1, not isMax))
                    board[i][j] = '_'
        return best
 
def findBestMove(board) : 
    bestVal = -1000
    bestMove = (-1, -1) 

    for i in range(3) :     
        for j in range(3) :
            if (board[i][j] == '_') : 
                board[i][j] = player
                moveVal = minimax(board, 0, False) 
                board[i][j] = '_'
                if (moveVal > bestVal) :                
                    bestMove = (i, j)
                    bestVal = moveVal
 
    print("The value of the best Move is :", bestVal)
    return bestMove

if __name__ == "__main__":
    board = [
        [ '_', '_', '_' ], 
        [ '_', '_', '_' ], 
        [ '_', '_', '_' ] 
    ]
 
    bestMove = findBestMove(board) 
 
    print("The Optimal Move is :") 
    print("ROW:", bestMove[0], " COL:", bestMove[1])

Как учебный - данный пример хорош, но на практике при использовании рекурсии мы можем столкнуться с ограничением величины стека вызовов. Поэтому нужно переписать наш пример без рекурсии.

Алгоритм минимакс на примере игры tic-tak-toe.

Правила игры

Ссылки по теме