Или, точнее, задача, поскольку в этом году мы попробовали другой формат: задача была всего одна, но большая. Требовалось написать 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), устроим еще один турнир.
