Печать

tic-tac-toe 2026

Крестики-нолики — логическая игра между двумя противниками на квадратном поле 3 на 3 клетки или большего размера. Цель игры, занять три  клетки в ряд, включая диагонали. Пишем программу игры крестики-нолики на Python с библиотекой Pygame Zero (pgzrun).

Кто решает задачи по комбинаторной геометрии, тот

впоследствии пишет короткие и сильные алгоритмы.

Алексей Савватеев.

Мы публикуем методическую разработку для занятий с детьми старше 10-ти лет в кружке программирование на Python. Цель - научить детей строить логические выражения и пользоваться условным оператором if (elif, else), использовать цикл for, вложенный цикл и операторы continue и break, а также, создавать собственные функции и возвращать из них результат. В конце статьи приведён пример использования алгоритма minimax рекурсивный алгоритм с возвратом (backtracking).

import warnings
warnings.filterwarnings("ignore", category=RuntimeWarning, message=".*AVX2.*")
import pgzrun, pygame
"""
Pygame Zero (pgzrun) - это обёртка над Pygame,
которая упрощает создание игр,
автоматизируя многие рутинные задачи.
"""


# Настройки игры, глобальные константы
TITLE = "tic-tac-toe"                           # Заголовок окна
WIDTH = HEIGHT = 400                            # Ширина и высота окна
CELL = WIDTH // 3                               # Размер клетки


# Игровые переменные
playground = [0] * 9                            # Виртуальное игровое поле
# Элементами списка playground могут быть числа -1, 0 и 1.
#  0 пустая клетка на игровом поле
# -1 в клетке установлен О
#  1 в клетке установлен Х


def won(pg):
    """
    Подсчёт сумм линий по 3
    возвращает вес хода -1, 0, 1
    """
    pass


def play(n):
    """
    Ход в игре
    """
    pass


def n_to_xy(n):
    """
    Конвертирует номер клетки в пару координат
    в центре этой клетки
    
    """
    return (CELL // 2, CELL // 2)


def xy_to_n(x, y):
    """
    Конвертирует пару координат x, y
    в номер клетки
    """
    return 0


def draw_playground():
    """
    Рисует по клеткам игровое поле в клетку и
    символы в соответствии с игровой ситуацией
    """
    pass


def draw():
    """
    draw() особая функция, вызывается автоматически каждый кадр,
    обычно, 60 FPS. Доступны объекты: screen, actors и др.
    Назначение: отрисовка всего, что должно быть на экране.
    """
    pygame.display.set_caption(TITLE)           # Обновление заголовка
    draw_playground()                           # Нарисовать игровое поле


def on_mouse_down(pos):
    """
    on_mouse_down(pos) особая функция, вызывается автоматически при клике мыши
    Через параметр pos в функцию передаётся кортеж из пары координат (x, y)
    """
    play(xy_to_n(*pos))                         # Сделать ход в выбранную клетку


pgzrun.go()                                     # Запускается главный игровой цикл

Лист. 1.

import warnings
warnings.filterwarnings("ignore", category=RuntimeWarning, message=".*AVX2.*")
import pgzrun, pygame
"""
Pygame Zero (pgzrun) - это обёртка над Pygame,
которая упрощает создание игр,
автоматизируя многие рутинные задачи.
"""


# Настройки игры, глобальные константы
TITLE = "tic-tac-toe"                           # Заголовок окна
WIDTH = HEIGHT = 400                            # Ширина и высота окна
CELL = WIDTH // 3                               # Размер клетки
FONT_SIZE = WIDTH // 4                          # Размер цифр
FONT_COLOR = 'sienna'                           # Цвет букв
font_params = {'color': FONT_COLOR,'fontsize': FONT_SIZE}
BTN_COLOR = 'khaki'                             # Цвет кнопки
GRID_COLOR = 'dimgray'                          # Цвет сетки
BORDER_COLOR = 'gold'                           # Цвет бордюра клеток


# Игровые переменные
playground = [0] * 9                            # Виртуальное игровое поле
# Элементами списка playground могут быть числа -1, 0 и 1.
#  0 пустая клетка на игровом поле
# -1 в клетке установлен О
#  1 в клетке установлен Х


def won(pg):
    """
    Подсчёт сумм линий по 3
    возвращает вес хода -1, 0, 1
    """
    pass


def play(n):
    """
    Ход в игре
    """
    pass


def n_to_xy(n):
    """
    Конвертирует номер клетки в пару координат
    в центре этой клетки
    
    """
    col = n % 3
    row = n // 3
    x = col * CELL
    y = row * CELL
    return (x + CELL // 2, y + CELL // 2)


def xy_to_n(x, y):
    """
    Конвертирует пару координат x, y
    в номер клетки
    """
    col = x // CELL
    row = y // CELL
    return row * 3 + col


def draw_playground():
    """
    Рисует по клеткам игровое поле в клетку и
    символы в соответствии с игровой ситуацией
    """
    for n in range(9):
        x = n_to_xy(n)[0] - CELL // 2
        y = n_to_xy(n)[1] - CELL // 2
        screen.draw.filled_rect(Rect(x, y, CELL, CELL), GRID_COLOR)
        screen.draw.filled_rect(Rect(x+1, y+1, CELL-1, CELL-1), BORDER_COLOR)
        screen.draw.filled_rect(Rect(x+7, y+7, CELL-14, CELL-14), BTN_COLOR)
        txt = "X" if playground[n] == 1 else "O"
        if playground[n] == 0: continue
        screen.draw.text(txt, center = n_to_xy(n), **font_params)


def draw():
    """
    draw() особая функция, вызывается автоматически каждый кадр,
    обычно, 60 FPS. Доступны объекты: screen, actors и др.
    Назначение: отрисовка всего, что должно быть на экране.
    """
    pygame.display.set_caption(TITLE)           # Обновление заголовка
    draw_playground()                           # Нарисовать игровое поле


def on_mouse_down(pos):
    """
    on_mouse_down(pos) особая функция, вызывается автоматически при клике мыши
    Через параметр pos в функцию передаётся кортеж из пары координат (x, y)
    """
    play(xy_to_n(*pos))                         # Сделать ход в выбранную клетку


pgzrun.go()                                     # Запускается главный игровой цикл

Лист. 2.

import warnings
warnings.filterwarnings("ignore", category=RuntimeWarning, message=".*AVX2.*")
import pgzrun, pygame
"""
Pygame Zero (pgzrun) - это обёртка над Pygame,
которая упрощает создание игр,
автоматизируя многие рутинные задачи.
"""


# Настройки игры, глобальные константы
TITLE = "tic-tac-toe"                           # Заголовок окна
WIDTH = HEIGHT = 400                            # Ширина и высота окна
CELL = WIDTH // 3                               # Размер клетки
FONT_SIZE = WIDTH // 4                          # Размер цифр
FONT_COLOR = 'sienna'                           # Цвет букв
font_params = {'color': FONT_COLOR,'fontsize': FONT_SIZE}
BTN_COLOR = 'khaki'                             # Цвет кнопки
GRID_COLOR = 'dimgray'                          # Цвет сетки
BORDER_COLOR = 'gold'                           # Цвет бордюра клеток


# Игровые переменные
playground = [0] * 9                            # Виртуальное игровое поле
# Элементами списка playground могут быть числа -1, 0 и 1.
#  0 пустая клетка на игровом поле
# -1 в клетке установлен О
#  1 в клетке установлен Х
who = 1                                         # Чей ход


def won(pg):
    """
    Подсчёт сумм линий по 3
    возвращает вес хода -1, 0, 1
    """
    pass


def play(n):
    """
    Ход в игре
    """
    global who
    playground[n] = who
    who *= -1


def n_to_xy(n):
    """
    Конвертирует номер клетки в пару координат
    в центре этой клетки
    
    """
    col = n % 3
    row = n // 3
    x = col * CELL
    y = row * CELL
    return (x + CELL // 2, y + CELL // 2)


def xy_to_n(x, y):
    """
    Конвертирует пару координат x, y
    в номер клетки
    """
    col = x // CELL
    row = y // CELL
    return row * 3 + col


def draw_playground():
    """
    Рисует по клеткам игровое поле в клетку и
    символы в соответствии с игровой ситуацией
    """
    for n in range(9):
        x = n_to_xy(n)[0] - CELL // 2
        y = n_to_xy(n)[1] - CELL // 2
        screen.draw.filled_rect(Rect(x, y, CELL, CELL), GRID_COLOR)
        screen.draw.filled_rect(Rect(x+1, y+1, CELL-1, CELL-1), BORDER_COLOR)
        screen.draw.filled_rect(Rect(x+7, y+7, CELL-14, CELL-14), BTN_COLOR)
        txt = "X" if playground[n] == 1 else "O"
        if playground[n] == 0: continue
        screen.draw.text(txt, center = n_to_xy(n), **font_params)


def draw():
    """
    draw() особая функция, вызывается автоматически каждый кадр,
    обычно, 60 FPS. Доступны объекты: screen, actors и др.
    Назначение: отрисовка всего, что должно быть на экране.
    """
    pygame.display.set_caption(TITLE)           # Обновление заголовка
    draw_playground()                           # Нарисовать игровое поле


def on_mouse_down(pos):
    """
    on_mouse_down(pos) особая функция, вызывается автоматически при клике мыши
    Через параметр pos в функцию передаётся кортеж из пары координат (x, y)
    """
    play(xy_to_n(*pos))                         # Сделать ход в выбранную клетку


pgzrun.go()                                     # Запускается главный игровой цикл

Лист. 3.

import warnings
warnings.filterwarnings("ignore", category=RuntimeWarning, message=".*AVX2.*")
import pgzrun, pygame
"""
Pygame Zero (pgzrun) - это обёртка над Pygame,
которая упрощает создание игр,
автоматизируя многие рутинные задачи.
"""


# Настройки игры, глобальные константы
TITLE = "tic-tac-toe"                           # Заголовок окна
WIDTH = HEIGHT = 400                            # Ширина и высота окна
CELL = WIDTH // 3                               # Размер клетки
FONT_SIZE = WIDTH // 4                          # Размер цифр
FONT_COLOR = 'sienna'                           # Цвет букв
font_params = {'color': FONT_COLOR,'fontsize': FONT_SIZE}
BTN_COLOR = 'khaki'                             # Цвет кнопки
GRID_COLOR = 'dimgray'                          # Цвет сетки
BORDER_COLOR = 'gold'                           # Цвет бордюра клеток


# Игровые переменные
playground = [0] * 9                            # Виртуальное игровое поле
# Элементами списка playground могут быть числа -1, 0 и 1.
#  0 пустая клетка на игровом поле
# -1 в клетке установлен О
#  1 в клетке установлен Х
#playground[4] = -1                             # Первый ход О


def won(pg):
    """
    Подсчёт сумм линий по 3
    возвращает вес хода -1, 0, 1
    """
    standings = [0]*8
    for i in range(3):
        standings[i] = pg[i*3] + pg[i*3+1] + pg[i*3+2]
        standings[i+3] = pg[i] + pg[i+3] + pg[i+6]
    standings[6] = pg[0] + pg[4] + pg[8]
    standings[7] = pg[2] + pg[4] + pg[6]
    if 3 in standings : return 1                # Победа Х
    if -3 in standings : return -1              # Победа О
    return 0                                    # Вес нейтральный


def play(n):
    """
    Ход в игре
    """
    global TITLE
    if playground[n] != 0: return               # Если выбрана не пустая клетка
    if won(playground) != 0: return             # Прекратить игру в случае победы
    for i in (1, -1):
        playground[n] = i                       # Ход на виртуальном поле
        if won(playground) == -1:               # Победа O
            TITLE = 'Победа O'
        elif not 0 in playground:               # Если не осталось пустых клеток
            TITLE = 'Ничья'
            break
        n = minmax(playground, -1)[1]


def minmax(pg, step):
    """
    Поиск лучшего хода. pg список игровое поле из 9 элементов.
    step = 1 ход крестика, step = -1 ход О.
    Возвращает списсок [оценка позиции, индекс лучшего хода]
    """
    best = [-2 * step, None]
    if won(pg) != 0: return [won(pg), None]
    if 0 not in pg: return [0, None]
    for i in range(9):
        if pg[i] != 0: continue
        pgcp = pg.copy()
        pgcp[i] = step
        x = minmax(pgcp, -1 * step)[0]
        if (step == 1 and x > best[0]) or (step == -1 and x < best[0]):
            best = [x, i]
    return best


def n_to_xy(n):
    """
    Конвертирует номер клетки в пару координат
    в центре этой клетки
    
    """
    col = n % 3
    row = n // 3
    x = col * CELL
    y = row * CELL
    return (x + CELL // 2, y + CELL // 2)


def xy_to_n(x, y):
    """
    Конвертирует пару координат x, y
    в номер клетки
    """
    col = x // CELL
    row = y // CELL
    return row * 3 + col


def draw_playground():
    """
    Рисует по клеткам игровое поле в клетку и
    символы в соответствии с игровой ситуацией
    """
    for n in range(9):
        x = n_to_xy(n)[0] - CELL // 2
        y = n_to_xy(n)[1] - CELL // 2
        screen.draw.filled_rect(Rect(x, y, CELL, CELL), GRID_COLOR)
        screen.draw.filled_rect(Rect(x+1, y+1, CELL-1, CELL-1), BORDER_COLOR)
        screen.draw.filled_rect(Rect(x+7, y+7, CELL-14, CELL-14), BTN_COLOR)
        txt = "X" if playground[n] == 1 else "O"
        if playground[n] == 0: continue
        screen.draw.text(txt, center = n_to_xy(n), **font_params)


def draw():
    """
    draw() особая функция, вызывается автоматически каждый кадр,
    обычно, 60 FPS. Доступны объекты: screen, actors и др.
    Назначение: отрисовка всего, что должно быть на экране.
    """
    pygame.display.set_caption(TITLE)           # Обновление заголовка
    draw_playground()                           # Нарисовать игровое поле


def on_mouse_down(pos):
    """
    on_mouse_down(pos) особая функция, вызывается автоматически при клике мыши
    Через параметр pos в функцию передаётся кортеж из пары координат (x, y)
    """
    play(xy_to_n(*pos))                         # Сделать ход в выбранную клетку


pgzrun.go()                                     # Запускается главный игровой цикл

Лист. 10.

Детальное описание функции minmax()

Теоретическая основа

Функция реализует алгоритм минимакс для игры в крестики-нолики. Этот алгоритм используется для нахождения оптимального хода в играх с нулевой суммой (что выигрывает один игрок, то проигрывает другой).

Основные концепции:

  1. Дерево игры - все возможные последовательности ходов

  2. Эвристическая оценка - числовая оценка позиции

  3. Рекурсивный перебор - исследование возможных вариантов

  4. Альфа-бета отсечения (в данном коде нет, но принцип похож)

Подробный разбор кода с комментариями

python
def minmax(pg, step):
    """
    Алгоритм минимакс для поиска оптимального хода
    pg: playground - текущее состояние поля (список из 9 элементов)
    step: 1 (крестик/X) или -1 (нолик/O) - чей сейчас ход оценивается
    Возвращает: [оценка_позиции, индекс_лучшего_хода]
    """
    
    # Инициализируем лучший результат
    # Ключевой момент: для крестика (step=1) начинаем с -2, для нолика с 2
    # Это гарантирует, что первый найденный вариант будет "лучшим"
    # -2 и 2 выбраны как значения за пределами возможных оценок [-1, 0, 1]
    best = [-2 * step, None]
    
    # Базовый случай 1: игра уже завершена
    # Если кто-то уже выиграл, возвращаем результат игры
    game_result = won(pg)
    if game_result != 0: 
        return [game_result, None]  # 1 - победа X, -1 - победа O
    
    # Базовый случай 2: ничья (нет пустых клеток)
    if 0 not in pg: 
        return [0, None]  # 0 означает ничью
    
    # Рекурсивный случай: перебираем все возможные ходы
    for i in range(9):
        # Пропускаем занятые клетки
        if pg[i] != 0: 
            continue
        
        # Создаем копию поля для моделирования хода
        pgcp = pg.copy()
        
        # Моделируем ход текущего игрока в клетку i
        pgcp[i] = step
        
        # Рекурсивно вызываем minmax для противника
        # Ключевой момент: передаем -step для смены игрока
        # Получаем оценку позиции после этого хода
        x = minmax(pgcp, -1 * step)[0]
        
        # Обновляем лучший результат в зависимости от игрока:
        # 1. Для крестика (step=1): ищем МАКСИМАЛЬНУЮ оценку (x > best[0])
        #    Крестик хочет максимизировать свой выигрыш
        # 2. Для нолика (step=-1): ищем МИНИМАЛЬНУЮ оценку (x < best[0])
        #    Нолик хочет минимизировать выигрыш крестика (максимизировать свой)
        if (step == 1 and x > best[0]) or (step == -1 and x < best[0]):
            best = [x, i]  # Сохраняем новую лучшую оценку и ход
    
    # Возвращаем лучшую найденную оценку и соответствующий ход
    return best

Как работает оценка позиции

Функция won(pg) возвращает:

Логика выбора хода:

Для крестика (step = 1):

text
Дерево решений:
Крестик смотрит: "Если я пойду сюда, то нолик ответит туда..."
Он выбирает ход, который дает максимальную оценку
при условии, что нолик будет играть оптимально

Для нолика (step = -1):

text
Нолик смотрит: "Если крестик пойдет сюда, то я должен ответить туда..."
Он выбирает ход, который минимизирует оценку для крестика
(максимизирует свои шансы)

Пример работы на практике

Рассмотрим упрощенный пример с 2 возможными ходами:

python
# Текущее поле: [0, 0, 0, 0, -1, 0, 0, 0, 0] (нолик в центре)
# Ход крестика (step=1)

# Вариант 1: Ход в клетку 0 (левый верх)
# minmax() моделирует: X в 0 → O в ... → и т.д.
# Предположим, оценка = 0 (ничья)

# Вариант 2: Ход в клетку 8 (правый низ)  
# minmax() моделирует: X в 8 → O в 0 → X в 2 → ...
# Предположим, оценка = 1 (победа X)

# Крестик выберет вариант 2 (оценка 1 > 0)

Рекурсивная структура вызовов

text
minmax(поле, игрок)
    ├── Проверяем: игра окончена? → возвращаем результат
    ├── Для каждой свободной клетки:
    │     ├── Копируем поле
    │     ├── Делаем ход
    │     └── Рекурсивно вызываем minmax() для противника
    │
    └── Выбираем лучший ход:
          - Для X: максимальная оценка
          - Для O: минимальная оценка

Почему такой подход оптимален?

  1. Полный перебор - алгоритм рассматривает ВСЕ возможные варианты до конца игры

  2. Оптимальность - гарантирует лучший возможный результат при оптимальной игре противника

  3. Предвидение - учитывает, что противник тоже будет играть оптимально

Визуализация процесса

text
Текущая позиция (X ходит)
   │
   ├── Ход в A → оценка -1 (O выигрывает)
   ├── Ход в B → оценка 0 (ничья)  
   └── Ход в C → оценка 1 (X выигрывает)
        │
        └── X выбирает ход C

Ключевые моменты реализации

  1. Инициализация best: [-2 * step, None] гарантирует, что первый найденный ход станет лучшим

  2. Рекурсивный вызов: minmax(pgcp, -1 * step) меняет игрока на каждом уровне

  3. Условие выбора: разная логика для X и O из-за противоположных целей

  4. Отсутствие отсечений: простейший минимакс без оптимизаций (альфа-бета)

Сложность алгоритма

Для крестиков-ноликов:

Как это используется в игре

python
def play(n):
    # ...
    # Компьютер (нолик) ищет лучший ход:
    n = minmax(playground, -1)[1]  # -1 означает "ход нолика"
    # Получаем индекс лучшей клетки и ходим туда

Этот алгоритм гарантирует, что компьютер будет играть в крестики-нолики безупречно - либо выиграет, либо сведет игру к ничьей.