Или, точнее, задача, поскольку в этом году мы попробовали другой формат: задача была всего одна, но большая. Требовалось написать 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Начнем с того, что учтем два соображения:
Первый ход лучше делать в центр поля, а лучшие ответные ходы будут располагаться где-то неподалеку от уже поставленных знаков. На анализ других позиций можно не тратить время.
Исключаем из рассмотрения уже занятые клетки.
Получается примерно такой запрос:
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)).
Что ж, начало положено. Теперь нам надо научиться оценивать ходы.
Немного подумав (или погуглив), можно прийти к тому, что надо анализировать определенные шаблоны стоящих подряд (по горизонталям, вертикалям или диагоналям) знаков. Они образуют иерархию, которую можно преобразовать в веса:
Если к четырем нашим крестикам можно пристроить пятый, надо ставить и выигрывать. Тут могут быть разные конфигурации:
XXXX*,XXX*XилиXX*XX.Если на поле стоят четыре нолика, надо помешать сопернику поставить пятый:
OOOO*и т. п.Если на поле стоят три крестика, и к ним можно поставить четвертый так, чтобы они оставались открытыми с двух сторон, это надо сделать — на следующем ходу выиграем. Тут тоже возможны разные конфигурации типа
.XXX*.или.XX*X..Если на поле стоят три нолика, надо помешать им дорасти до четырех.
И так далее по убыванию количества знаков.
Если просуммировать веса всех найденных конфигураций, то «вилки» будут естественным образом получать больше баллов. Но надо следить за тем, чтобы несколько шаблонов типа .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), устроим еще один турнир.
