11.06.2024 09:19
erogov 0 1100 Источник

Или, точнее, задача, поскольку в этом году мы попробовали другой формат: задача была всего одна, но большая. Требовалось написать SQL-запрос, играющий в крестики-нолики «пять в ряд».

Условие задачи

Общие правила игры

Игра ведется на поле размером 19×19 клеток, пронумерованных от 1 до 19 по горизонтали и вертикали. Два игрока по очереди ставят на любую из свободных клеток свой знак: первый игрок ставит крестики, второй — нолики. Побеждает игрок, первым построивший пять знаков в ряд по вертикали, горизонтали или диагонали.

Если игрок не может сделать ход из-за отсутствия на поле пустых клеток, он проигрывает.

Каждому игроку отведено на партию 5 минут (время отдельных ходов не ограничивается). Игрок, не успевший совершить свой ход, проигрывает.

Требования к решению

Решение должно состоять из одного SQL-запроса. Запрос имеет доступ к единственной таблице: 

CREATE TABLE field (
  x integer NOT NULL CHECK (x BETWEEN 1 AND 19),
  y integer NOT NULL CHECK (y BETWEEN 1 AND 19),
  my boolean NOT NULL,
  UNIQUE (x, y)
);

Запрос должен вернуть одну строку с двумя координатами x и y очередного хода. Названия столбцов не играют роли. Если координаты нарушают ограничения целостности таблицы, игрок проигрывает.

Веб-приложение

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

Пользуясь случаем, хочу сказать спасибо за приложение и всю лежащую за ним систему проведения игр моему коллеге Илье Баштанову. Без такой автоматизации финал прошел бы гораздо скучнее.

Разбор решения

Я расскажу про алгоритм, который мы назвали XO-ботом и с которым можно было играть в приложении.

Но давайте забудем пока про SQL и подумаем, как вообще решают такие задачи.

Базовый алгоритм для подобных игр называется минимаксом. Все возможные ходы представляют в виде дерева. Корень — текущая позиция, следующий уровень — возможные ходы крестиков (будем считать, что мы играем за них), следующий — возможные ответы ноликов и так далее. В листьях этого дерева будут финальные позиции, которым можно дать числовую оценку: чем больше, тем лучше («плюс бесконечность» — наш выигрыш, «минус бесконечность» — выигрыш противника). Исходят из того, что делается лучший ход: соперник минимизирует оценку, а мы — максимизируем (отсюда и название алгоритма).

Дерево получается гигантским, так что до конца его построить не удается и приходится остановиться на какой-то глубине, оценивая получающиеся позиции по той же шкале. Кроме того, придуманы способы отсекать заведомо лишние ветви (альфа-бета-отсечение).

Все это легко гуглится, даже если не знать заранее нужных слов. У участников был полный доступ к интернету.

Но тут, конечно, надо призадуматься. Реалистично ли за восемь часов реализовать такой алгоритм на SQL, да еще и так, чтобы вписаться в ограничение на время партии? Вот и участники решили, что не надо — никто не стал пытаться.

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

Давайте для удобства иллюстрации сразу предположим, что какие-то крестики и нолики уже стоят:

INSERT INTO field(x, y, my) VALUES
  (10,10,false), (10,9,false), (9,9,true);

Вот эта позиция на поле (я обозначил наш знак буквой X, знак противника — буквой O, а точкой . я просто выделил десятую вертикаль и горизонталь):

J |         .
I |         .
H |         .
G |         .
F |         .
E |         .
D |         .
C |         .
B |         .
A |.........O..........
9 |        XO
8 |         . 
7 |         .
6 |         .      
5 |         .
4 |         .
3 |         .
2 |         .
1 |         .
   -------------------
   123456789ABCDEFGHIJ

Начнем с того, что учтем два соображения:

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

  2. Исключаем из рассмотрения уже занятые клетки.

Получается примерно такой запрос:

WITH neighbors(x,y) AS (
  -- ближайшие к занятым пустые клетки или центр пустого поля
  SELECT x, y 
  FROM (
    SELECT x+dx x, y+dy y 
    FROM field f, generate_series(-1,1) dx, generate_series(-1,1) dy  
    UNION -- убираем дубликаты
    SELECT 10, 10
  )
  WHERE (x,y) NOT IN (SELECT x,y FROM field)
  AND x BETWEEN 1 AND 19
  AND y BETWEEN 1 AND 19
)
SELECT * FROM neighbors;

Подзапрос neighbors сдвигает все заполненные клетки по всем направлениям и добавляет центральную клетку (10,10) на тот случай, если еще не сделано ни одного хода. Затем из получившихся вариантов клеток удаляются уже занятые и выходящие за пределы поля.

Вот полученные поля на картинке:

J |
I |
H |
G |
F |
E |
D |
C |
B |        ...
A |       ..O.
9 |       .XO.
8 |       ....
7 |
6 |
5 |
4 |
3 |
2 |
1 |
   -------------------
   123456789ABCDEFGHIJ

(Не факт, что все лучшие ходы расположены именно вплотную к уже сделанным, так что можно попробовать сдвиг и на две клетки: generate_series(-2,2)).

Что ж, начало положено. Теперь нам надо научиться оценивать ходы.

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

  1. Если к четырем нашим крестикам можно пристроить пятый, надо ставить и выигрывать. Тут могут быть разные конфигурации: XXXX*, XXX*X или XX*XX.

  2. Если на поле стоят четыре нолика, надо помешать сопернику поставить пятый: OOOO* и т. п.

  3. Если на поле стоят три крестика, и к ним можно поставить четвертый так, чтобы они оставались открытыми с двух сторон, это надо сделать — на следующем ходу выиграем. Тут тоже возможны разные конфигурации типа .XXX*. или .XX*X..

  4. Если на поле стоят три нолика, надо помешать им дорасти до четырех.

  5. И так далее по убыванию количества знаков.

Если просуммировать веса всех найденных конфигураций, то «вилки» будут естественным образом получать больше баллов. Но надо следить за тем, чтобы несколько шаблонов типа .XXX*. не перевесили OOOO*.

Эти рассуждения наводят на мысль, что с поиском шаблонов должен неплохо справляться обычный LIKE, если представить горизонтали, вертикали и диагонали в виде текстовых строк. Многие участники пытались анализировать длины непрерывных цепочек знаков в традиционно-реляционном стиле, но это очень громоздко и не позволяет легко оперировать шаблонами типа XX.*X.

Первый шаг к текстовому представлению — дополнить поле пустыми клетками и каждую клетку представить каким-нибудь символом (я обозначил наш знак буквой X, знак противника — буквой O, а пустую клетку — точкой .).

WITH neighbors(x,y) AS (
  ...
), filled(x,y,pos) AS (
  -- поле, дополненное пустыми клетками
  -- и представленное символами вместо boolean
  SELECT xx, yy, CASE WHEN my THEN 'X' WHEN NOT my THEN 'O' ELSE '.' END
  FROM generate_series(1,19) xx
    CROSS JOIN generate_series(1,19) yy
    LEFT JOIN field f ON f.x = xx AND f.y = yy
)
...

Следующий шаг — сформировать все возможные ряды: горизонтали, вертикали и диагонали. Потом нам придется находить в этих длинных рядах клетку с заданными координатами, поэтому вместе с рядом я сохраняю координаты его «головы» (x,y) и направление (dx,dy) к «хвосту». (Вместо этого можно было бы сразу нарезать короткие ряды отдельно для каждой клетки, но подозреваю, что так выйдет затратнее.)

С горизонталями и вертикалями все просто, а диагонали, конечно, придется немного порисовать на листочке в клетку, пока все цифры не сойдутся. Диагонали длиной меньше пяти клеток (в углах поля) учитывать не надо, поскольку пять в ряд на них не построить.

WITH neighbors(x,y) AS (
  ...
), filled(x,y,pos) AS (
  ...
), lines(x,y,dx,dy,line) AS (
  -- линии клеток:
  -- горизонтали
  SELECT 1, y, 1, 0, string_agg(pos,'' ORDER BY x) FROM filled GROUP BY y
  UNION ALL 
  -- вертикали
  SELECT x, 1, 0, 1, string_agg(pos,'' ORDER BY y) FROM filled GROUP BY x
  UNION ALL 
  -- диагонали
  SELECT CASE WHEN x+y > 20 THEN x+y-19 ELSE 1 END,
         CASE WHEN x+y > 20 THEN 19 ELSE x+y-1 END,
         1, -1, string_agg(pos,'' ORDER BY x) FROM filled GROUP BY x+y HAVING x+y BETWEEN 6 AND 34
  UNION ALL 
  SELECT CASE WHEN x-y >= 0 THEN 1+(x-y) ELSE 1 END,
         CASE WHEN x-y >= 0 THEN 1 ELSE 1-(x-y) END,
         1, 1, string_agg(pos,'' ORDER BY x) FROM filled GROUP BY x-y HAVING x-y BETWEEN -14 AND 14
)
SELECT * FROM lines
WHERE line !~ '^\.*$'; -- показываю только непустые ряды
 x  | y  | dx | dy |        line         
----+----+----+----+---------------------
  1 |  9 |  1 |  0 | ........XO.........  горизонтали
  1 | 10 |  1 |  0 | .........O.........
  9 |  1 |  0 |  1 | ........X..........  вертикали
 10 |  1 |  0 |  1 | ........OO.........
  1 | 17 |  1 | -1 | ........X........    диагонали в одну стторону
  1 | 18 |  1 | -1 | .........O........
  1 | 19 |  1 | -1 | .........O.........
  1 |  1 |  1 |  1 | ........XO.........  диагонали в другую сторону
  2 |  1 |  1 |  1 | ........O.........
(9 rows)

Вот эти ряды на картинке, чтобы было понятнее. Символом @ я обозначил «головы» рядов c координатами (x, y).

J |        ||            J |@                 /
I |        ||            I |@\               //
H |        ||            H |@\\             //
G |        ||            G | \\\           //
F |        ||            F |  \\\         //
E |        ||            E |   \\\       //
D |        ||            D |    \\\     //
C |        ||            C |     \\\   //
B |        ||            B |      \\\ //
A |@-------+O---------   A |       \\O/
9 |@-------XO---------   9 |        XO\
8 |        ||            8 |       //\\\
7 |        ||            7 |      //  \\\
6 |        ||            6 |     //    \\\
5 |        ||            5 |    //      \\\
4 |        ||            4 |   //        \\\
3 |        ||            3 |  //          \\\
2 |        ||            2 | //            \\\
1 |        @@            1 |@@              \\\
   -------------------      -------------------
   123456789ABCDEFGHIJ      123456789ABCDEFGHIJ

Теперь собираем для каждого потенциального хода из neighbours набор проходящих через него рядов. Потенциальный ход приходится на пустую клетку (.), сразу заменяем ее маркером рассматриваемого хода (я выбрал *). Для этого подбираем нужное количество клеток от «головы» ряда (delta):

WITH neighbors(x,y) AS (
  ...
), filled(x,y,pos) AS (
  ...
), lines(x,y,dx,dy,line) AS (
  ...
), lines_per_move(x,y,delta,dx,dy,line) AS (
  -- линии в группировке по потенциальным ходам
  SELECT n.x, n.y, delta, l.dx, l.dy, overlay(l.line PLACING '*' FROM delta+1)
  FROM neighbors n
    CROSS JOIN generate_series(0,18) delta
    JOIN lines l ON n.x = l.x + l.dx*delta AND n.y = l.y + l.dy*delta
)
SELECT * FROM lines_per_move
WHERE x = 10 AND y = 8; -- показываю только для одной клетки
 x  | y | delta | dx | dy |        line         
----+---+-------+----+----+---------------------
 10 | 8 |     9 |  1 |  0 | .........*.........
 10 | 8 |     7 |  0 |  1 | .......*OO.........
 10 | 8 |     9 |  1 | -1 | ........X*.......
 10 | 8 |     7 |  1 |  1 | .......*.........
(4 rows)

Вот они на картинке:

J |         .
I |         .
H |.        .        .
G | .       .       .
F |  .      .      .
E |   .     .     .
D |    .    .    .
C |     .   .   .
B |      .  .  .
A |       . O .
9 |        XO.
8 |.........*.........
7 |        ...
6 |       . . .
5 |      .  .  .
4 |     .   .   .
3 |    .    .    .
2 |   .     .     .
1 |  .      .      .
   -------------------
   123456789ABCDEFGHIJ

Теперь займемся весами. Я на скорую руку набросал такие:

WITH templates(weight,template) AS (
  -- шаблоны с весами
  VALUES
    (100000,  '*XXXX'), (100000,  'X*XXX'), (100000,  'XX*XX'),
    ( 31000,  '*OOOO'), ( 31000,  'O*OOO'), ( 31000,  'OO*OO'),
    ( 10000, '.*XXX.'), ( 10000, '.X*XX.'),
    (  3100, '.*OOO.'), (  3100, '.O*OO.'),
    (  1000, '.*XXXO'), (  1000, '.X*XXO'), (  1000, '.XX*XO'), (  1000, '.XXX*O'),
    (   310, '.*OOOX'), (   310, '.O*OOX'), (   310, '.OO*OX'), (   310, '.OOO*X'),
    (   800, '.*XX.'),  (   800, '.X*X.'),
    (   250, '.*OO.'),  (   250, '.O*O.'),
    (   500, '.*XXO'),  (   500, '.X*XO'),  (   500, '.XX*O'),
    (   150, '.*OOX'),  (   150, '.O*OX'),  (   150, '.OO*X'),
    (   100, '.*X.'),
    (    31, '.*O.'),
    (    10, '.*OX'),   (    10, '.O*X'),
    (     5, '.*.'),
    (     2, '.*O')
), templates_rev(weight,template) AS (
  SELECT weight, template FROM templates
  UNION
  SELECT weight, reverse(template) FROM templates
)
...

У каждого шаблона есть перевернутый парный; они, конечно, добавляются запросом (templates_rev).

Настройка весов и шаблонов — самая важная часть алгоритма. Я этим совсем не занимался, а вот победительница конкурса, Александра Сухотина, отнеслась к задаче серьезно. В результате ее алгоритм, в остальном практически повторяющий тот, что я показываю, не дал ХО-боту ни одного шанса.

Все, что нам осталось, — это просуммировать веса для каждого хода и выбрать наилучший:

WITH neighbors(x,y) AS (
  ...
), filled(x,y,pos) AS (
  ...
), lines(x,y,dx,dy,line) AS (
  ...
), lines_per_move(x,y,delta,dx,dy,line) AS (
  ...
), templates(weight,template) AS (
  ...
), templates_rev(weight,template) AS (
  ...
), costs(x,y,weight) as (
  SELECT l.x, l.y, sum(t.weight)
  FROM lines_per_move l
    JOIN templates_rev t ON l.line LIKE '%'||t.template||'%'
  GROUP BY x, y
)
SELECT x, y FROM costs
ORDER BY weight DESC, random()
LIMIT 1;
Весь запрос целиком
WITH neighbors(x,y) AS (
  -- ближайшие к занятым пустые клетки или центр пустого поля
  SELECT x, y 
  FROM (
    SELECT x+dx x, y+dy y 
    FROM field f, generate_series(-1,1) dx, generate_series(-1,1) dy  
    UNION -- убираем дубликаты
    SELECT 10, 10
  )
  WHERE (x,y) NOT IN (SELECT x,y FROM field)
  AND x BETWEEN 1 AND 19
  AND y BETWEEN 1 AND 19
), filled(x,y,pos) AS (
  -- поле, дополненное пустыми клетками
  -- и представленное символами вместо boolean
  SELECT xx, yy, CASE WHEN my THEN 'X' WHEN NOT my THEN 'O' ELSE '.' END
  FROM generate_series(1,19) xx
    CROSS JOIN generate_series(1,19) yy
    LEFT JOIN field f ON f.x = xx AND f.y = yy
), lines(x,y,dx,dy,line) AS (
  -- линии клеток:
  -- горизонтали
  SELECT 1, y, 1, 0, string_agg(pos,'' ORDER BY x) FROM filled GROUP BY y
  UNION ALL 
  -- вертикали
  SELECT x, 1, 0, 1, string_agg(pos,'' ORDER BY y) FROM filled GROUP BY x
  UNION ALL 
  -- диагонали
  SELECT CASE WHEN x+y > 20 THEN x+y-19 ELSE 1 END,
         CASE WHEN x+y > 20 THEN 19 ELSE x+y-1 END,
         1, -1, string_agg(pos,'' ORDER BY x) FROM filled GROUP BY x+y HAVING x+y BETWEEN 6 AND 34
  UNION ALL 
  SELECT CASE WHEN x-y >= 0 THEN 1+(x-y) ELSE 1 END,
         CASE WHEN x-y >= 0 THEN 1 ELSE 1-(x-y) END,
         1, 1, string_agg(pos,'' ORDER BY x) FROM filled GROUP BY x-y HAVING x-y BETWEEN -14 AND 14
), lines_per_move(x,y,delta,dx,dy,line) AS (
  -- линии в группировке по потенциальным ходам
  SELECT n.x, n.y, delta, l.dx, l.dy, overlay(l.line PLACING '*' FROM delta+1)
  FROM neighbors n
    CROSS JOIN generate_series(0,18) delta
    JOIN lines l ON n.x = l.x + l.dx*delta AND n.y = l.y + l.dy*delta
), templates(weight,template) AS (
  -- шаблоны с весами
  VALUES
    (100000,  '*XXXX'), (100000,  'X*XXX'), (100000,  'XX*XX'),
    ( 31000,  '*OOOO'), ( 31000,  'O*OOO'), ( 31000,  'OO*OO'),
    ( 10000, '.*XXX.'), ( 10000, '.X*XX.'),
    (  3100, '.*OOO.'), (  3100, '.O*OO.'),
    (  1000, '.*XXXO'), (  1000, '.X*XXO'), (  1000, '.XX*XO'), (  1000, '.XXX*O'),
    (   310, '.*OOOX'), (   310, '.O*OOX'), (   310, '.OO*OX'), (   310, '.OOO*X'),
    (   800, '.*XX.'),  (   800, '.X*X.'),
    (   250, '.*OO.'),  (   250, '.O*O.'),
    (   500, '.*XXO'),  (   500, '.X*XO'),  (   500, '.XX*O'),
    (   150, '.*OOX'),  (   150, '.O*OX'),  (   150, '.OO*X'),
    (   100, '.*X.'),
    (    31, '.*O.'),
    (    10, '.*OX'),   (    10, '.O*X'),
    (     5, '.*.'),
    (     2, '.*O')
), templates_rev(weight,template) AS (
  SELECT weight, template FROM templates
  UNION
  SELECT weight, reverse(template) FROM templates
), costs(x,y,weight) as (
  SELECT l.x, l.y, sum(t.weight)
  FROM lines_per_move l
    JOIN templates_rev t ON l.line LIKE '%'||t.template||'%'
  GROUP BY x, y
)
SELECT x, y FROM costs
ORDER BY weight DESC, random()
LIMIT 1;

Как продвинуться дальше

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

Я попробовал сделать это бесхитростным способом, но полный перебор даже на три хода работает непозволительно долго, слишком много получается вариантов. А преимуществ это не дает никаких при такой небольшой глубине. Так что вопрос в том, чтобы аккуратно реализовать процедуру отсечения.

А вам слабо? Присылайте ваши варианты (в комментарии или на edu@postgrespro.ru), устроим еще один турнир.

Комментарии (0)