Как улучшить оценочную функцию minimax для сложных крестики-нолики
Файл main.py
import threading
import pygame as pg
import sys
from game import Game
from minimax import Minimax
pg.init() # Инициализация Pygame
margin = 5 # Отступ
board_size = 180 # Размер доски
button_size = 55 # Размер кнопки
width = height = board_size * 3 + margin * 4 # Размеры окна
size_window = (width, height) # Размер окна
screen = pg.display.set_mode(size_window) # Создание окна
pg.display.set_caption("Сложные крестики нолики") # Установка заголовка окна
# Цвета
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
BLUE = (0, 0, 255)
game = Game() # Создание новой игры
def run_minimax(game): # Функция для запуска алгоритма Minimax
alg_minimax = Minimax(game, 100) # Создание экземпляра алгоритма Minimax
_, best_move = alg_minimax.minimax(0, False, -float('inf'), float('inf')) # Выполнение алгоритма Minimax
if best_move is not None: # Если найден лучший ход
if game.make_move(alg_minimax.next_game_board, best_move): # Если ход возможен
# Вывод информации о сделанном ходе
print(
f"Компьютер сделал ход на доске"
f" {alg_minimax.next_game_board[0] * 3 + alg_minimax.next_game_board[1] + 1} "
f"в ячейке {best_move[0] + 1}, {best_move[1] + 1}")
print(f"Следующий ход на доске {game.next_board[0] * 3 + game.next_board[1] + 1}")
def draw_endgame_message(result): # Функция для отображения сообщения о конце игры
if result == 'X':
message = "Победили крестики!"
elif result == 'O':
message = "Победили нолики!"
else:
message = "Ничья!"
font = pg.font.Font(None, 50) # Создание шрифта
text = font.render(message, True, (0, 0, 0)) # Создание текста
# Отображение текста в центре экрана
screen.blit(text, (width // 2 - text.get_width() // 2, height // 2 - text.get_height() // 2))
def reset_game(): # Функция для сброса игры
global game
game = Game() # Создание новой игры
while True: # Главный цикл игры
for event in pg.event.get(): # Обработка событий
if event.type == pg.QUIT:
pg.quit()
sys.exit(0) # Завершение работы программы
if event.type == pg.MOUSEBUTTONDOWN: # Если событие - нажатие кнопки мыши
x, y = pg.mouse.get_pos() # Получение координат мыши
board_col = x // board_size # Определение столбца доски
board_row = y // board_size # Определение строки доски
button_col = (x % board_size) // button_size # Определение столбца кнопки
button_row = (y % board_size) // button_size # Определение строки кнопки
if game.make_move((board_row, board_col), (button_row, button_col)): # Если ход возможен
# Вывод информации о сделанном ходе
print(f"Ход сделан на доске {board_row * 3 + board_col + 1} в ячейке {button_row + 1},{button_col + 1}")
print(f"Следующий ход на доске {game.next_board[0] * 3 + game.next_board[1] + 1}")
if game.current_player == 'O': # Если текущий игрок - 'O'
minimax_thread = threading.Thread(target=run_minimax, args=(game,)) # Создание потока для алгоритма Minimax
minimax_thread.start() # Запуск потока
minimax_thread.join() # Ожидание завершения потока
if game.game_over(): # Если игра окончена
result = game.game_over() # Получение результата игры
draw_endgame_message(result) # Отображение сообщения о конце игры
pg.display.update() # Обновление дисплея
pg.time.wait(2000) # Задержка в 2 секунды
reset_game() # Сброс игры
else: # Если ход невозможен
print(f"Ход невозможен")
font = pg.font.Font(None, 24) # Создание шрифта
for board_row in range(3): # Для каждой строки доски
for board_col in range(3): # Для каждого столбца доски
for row in range(3): # Для каждой строки клетки
for col in range(3): # Для каждого столбца клетки
x = (col * button_size + (col + 1) * margin) + (
board_col * (board_size + margin)) # Вычисление координаты x клетки
y = (row * button_size + (row + 1) * margin) + (
board_row * (board_size + margin)) # Вычисление координаты y клетки
cell_row = row % 3 # Определение строки клетки
cell_col = col % 3 # Определение столбца клетки
symbol = game.board[board_row][board_col][cell_row][cell_col] # Получение символа клетки
if symbol == 'X': # Если символ - 'X'
color = GREEN # Цвет клетки - зеленый
elif symbol == 'O': # Если символ - 'O'
color = RED # Цвет клетки - красный
else: # Если клетка пуста
color = WHITE # Цвет клетки - белый
pg.draw.rect(screen, color, (x, y, button_size, button_size)) # Отрисовка клетки
if symbol != '_': # Если клетка не пуста
font = pg.font.Font(None, 36) # Создание шрифта
text = font.render(symbol, True, BLACK) # Создание текста
text_rect = text.get_rect(center=(x + button_size // 2, y + button_size // 2)) # Создание прямоугольника для текста
screen.blit(text, text_rect) # Отрисовка текста
pg.display.update() # Обновление дисплея
Файл game.py
class Game:
def __init__(self):
self.board = [[[['_'] * 3 for _ in range(3)] for _ in range(3)] for _ in range(3)] # Инициализация доски игры
self.current_player = 'X' # Установка текущего игрока
self.next_board = None # Установка следующей доски
def make_move(self, board, cell): # Функция для выполнения хода
board_row, board_col = board # Получение координат доски
button_row, button_col = cell # Получение координат клетки
# Проверка, можно ли сделать ход на данной доске
if self.next_board is not None and self.next_board != (board_row, board_col):
return False
try:
# Проверка, свободна ли клетка
if self.board[board_row][board_col][button_row][button_col] != '_':
return False
# Выполнение хода
self.board[board_row][board_col][button_row][button_col] = self.current_player
self.next_board = (button_row, button_col)
# Переключение игрока
self.current_player = 'O' if self.current_player == 'X' else 'X'
return True
except IndexError:
pass
def check_winner(self, player): # Функция для проверки, выиграл ли игрок
for board_row in range(3):
for board_col in range(3):
for i in range(3):
# Проверка строк и столбцов на выигрыш
if self.board[board_row][board_col][i][0] == self.board[board_row][board_col][i][1] == \
self.board[board_row][board_col][i][2] == player:
return True
if self.board[board_row][board_col][0][i] == self.board[board_row][board_col][1][i] == \
self.board[board_row][board_col][2][i] == player:
return True
# Проверка диагоналей на выигрыш
if self.board[board_row][board_col][0][0] == self.board[board_row][board_col][1][1] == \
self.board[board_row][board_col][2][2] == player:
return True
if self.board[board_row][board_col][0][2] == self.board[board_row][board_col][1][1] == \
self.board[board_row][board_col][2][0] == player:
return True
return False
def game_over(self): # Функция для проверки, окончена ли игра
# Проверяем, выиграл ли кто-нибудь
if self.check_winner('X'):
return 'X'
if self.check_winner('O'):
return 'O'
# Проверяем, есть ли еще доступные ходы
for board_row in range(3):
for board_col in range(3):
for button_row in range(3):
for button_col in range(3):
if self.board[board_row][board_col][button_row][button_col] == '_':
return None
# Если ни один из игроков не выиграл и нет доступных ходов, игра закончена
return 'Draw'
файл minimax.py
class Minimax:
def __init__(self, game, max_depth):
self.game_boards = game.board # Инициализация доски игры
self.next_game_board = game.next_board # Инициализация следующей доски
self.max_depth = max_depth # Установка максимальной глубины
self.start_time = time.time() # Установка начального времени
def evaluate(self, player, depth): # Функция оценки
score = 0 # Инициализация счета
opponent = 'O' if player == 'X' else 'X' # Определение противника
for board_row in range(3): # Для каждой строки доски
for board_col in range(3): # Для каждого столбца доски
for i in range(3): # Для каждой строки клетки
# Проверяем строки и столбцы
for line in [self.game_boards[board_row][board_col][i],
[self.game_boards[board_row][board_col][j][i] for j in range(3)]]:
if line.count(player) == 2 and line.count('_') == 1:
score += 10 / depth # Близость к победе
if line.count(opponent) == 2 and line.count('_') == 1:
score -= 20 / depth # Угроза
# Проверяем диагонали
for diag in [[self.game_boards[board_row][board_col][i][i] for i in range(3)],
[self.game_boards[board_row][board_col][i][2 - i] for i in range(3)]]:
if diag.count(player) == 2 and diag.count('_') == 1:
score += 30 / depth # Близость к победе
if diag.count(opponent) == 2 and diag.count('_') == 1:
score -= 20 / depth # Угроза
# Центральные клетки
if self.game_boards[board_row][board_col][1][1] == player:
score += 1
# Угловые клетки
for i, j in [(0, 0), (0, 2), (2, 0), (2, 2)]:
if self.game_boards[board_row][board_col][i][j] == player:
score += 1
# Блокирование противника
for i in range(3):
for j in range(3):
if self.game_boards[board_row][board_col][i][j] == player and any(
line.count(opponent) == 1 and line.count('_') == 2 for line in
[self.game_boards[board_row][board_col][i],
[self.game_boards[board_row][board_col][k][j] for k in range(3)],
[self.game_boards[board_row][board_col][k][k] for k in range(3)],
[self.game_boards[board_row][board_col][k][2 - k] for k in range(3)]]):
score += 5 # Блокирование противника
return score, None # Возвращение оценки
def minimax(self, depth, isMaximizing, alpha, beta):
# Если достигнута максимальная глубина или превышено время, возвращаем оценку текущего состояния игры
if depth == self.max_depth or time.time() - self.start_time > 10:
return self.evaluate('X' if isMaximizing else 'O', depth)
board_row, board_col = self.next_game_board # Получаем координаты следующей доски
if isMaximizing: # Если текущий игрок максимизирует оценку
best = -1000 # Инициализация лучшего значения
best_move = None # Инициализация лучшего хода
for i in range(3): # Перебор всех клеток на доске
for j in range(3):
if self.game_boards[board_row][board_col][i][j] == '_': # Если клетка свободна
self.game_boards[board_row][board_col][i][j] = 'X' # Совершаем ход
original_next_board = self.next_game_board # Сохраняем оригинальную следующую доску
self.next_game_board = (i, j) # Обновляем следующую доску
score, _ = self.minimax(depth + 1, not isMaximizing, alpha, beta) # Рекурсивный вызов minimax
self.game_boards[board_row][board_col][i][j] = '_' # Отменяем ход
self.next_game_board = original_next_board # Восстанавливаем следующую доску
if score > best: # Если новый счет лучше предыдущего лучшего
best = score # Обновляем лучший счет
best_move = (i, j) # Обновляем лучший ход
alpha = max(alpha, best) # Обновляем значение alpha
if beta <= alpha: # Если beta меньше или равно alpha, прерываем цикл
break
return best, best_move # Возвращаем лучший счет и лучший ход
else: # Если текущий игрок минимизирует оценку
best = 1000 # Инициализация лучшего значения
best_move = None # Инициализация лучшего хода
for i in range(3): # Перебор всех клеток на доске
for j in range(3):
if self.game_boards[board_row][board_col][i][j] == '_': # Если клетка свободна
self.game_boards[board_row][board_col][i][j] = 'O' # Совершаем ход
original_next_board = self.next_game_board # Сохраняем оригинальную следующую доску
self.next_game_board = (i, j) # Обновляем следующую доску
score, _ = self.minimax(depth + 1, not isMaximizing, alpha, beta) # Рекурсивный вызов minimax
self.game_boards[board_row][board_col][i][j] = '_' # Отменяем ход
self.next_game_board = original_next_board # Восстанавливаем следующую доску
if score < best: # Если новый счет лучше предыдущего лучшего
best = score # Обновляем лучший счет
best_move = (i, j) # Обновляем лучший ход
beta = min(beta, best) # Обновляем значение beta
if beta <= alpha: # Если beta меньше или равно alpha, прерываем цикл
break
return best, best_move # Возвращаем лучший счет и лучший ход
Написал сложную версию крестики-нолики.
Игра состоит из 9 досок, каждая из которых имеет размер 3х3. Это создает дополнительный уровень сложности по сравнению с классической игрой в крестики-нолики.
Игроки ходят по очереди, ставя свой символ (крестик или нолик) в свободную ячейку на одной из досок. Первый игрок может сделать ход на любой доске. После этого следующий ход должен быть сделан на доске, которая соответствует ячейке, выбранной в предыдущем ходе. Например, если первый игрок сделал ход в центральной ячейке на одной из досок, следующий ход должен быть сделан на центральной доске.
Бот реализован с помощью алгоритма minimax с альфа бета отсечением, но вот в чём проблема, это функция оценки, вроде все варианты перебрал, но хз какие оценки ставить для непобедимого бота, помогите пожалуйста