Как написать простую решалку тсумего

Примерно год назад друг показал мне что такое го и как в него играют. Хорошо помню как в одной из первых партий я гордо построил цепочку из камней которая соединяла нижнюю сторону доски с верхней, а также цепочку соединяющую левую сторону с правой, на что друг мне сказал, что это конечно хорошо, но я проиграл. У меня тогда ушло много времени, чтобы понять почему. С тех пор я продвинулся до примерно первого дана KGS, а друг перестал со мной играть 🙂

Чтобы хорошо играть в го надо видеть на несколько ходов вперед, а этот навык хорошо развивает решение тсумего коих много на goproblems. Естественно, однажды меня посетила мысль, что неплохо было бы написать решалку этих тсумего и, в идеале, встроить её в goproblems, тем более, что adum эту идею одобряет. Поскольку сам я решаю тсумего методом очень неспешного перебора более-менее осмысленных ходов со скоростью где то 1 ход в пару секунд, при этом регулярно забывая с чего начинался перебор (и этого достаточно, чтобы уверенно решать задачи 3 дана), я прикинул с какой невероятной скоростью и точностью будет работать простейший поиск в глубину, то бишь dfs, и оценил сложность задачи как «на пару дней». Тут же я попробовал по быстрому написать эту решалку «в лоб» через простейший dfs и наткнулся на мелкую неприятность: в процессе поиска одни и те же позиции встречались много раз и пересчитывать их заново было как то совсем неоптимально даже для решалки написанной по быстрому. Недолго думая я завел кеш для храния уже решенных позиций и тут же наткнулся на другую неприятность: решение найденное однажды может быть неправильным если в эту позицию прийти другой последовательностью ходов. Здесь я завис, не зная что делать, но решил, что эта неприятность легко решаемая — надо лишь немного подумать. Думал я довольно долго и решил, что есть смысл посмотреть, что уже есть готового на данную тему — статьи, алгоритмы и т.п. Первым делом мне на глаза попался некий «lambda depth first proof number search» и посмотрев, что размер статьи всего то несколько страниц, я обрадованно начал читать. В статье оказались ссылки на другие подобные статьи Мартина Мюллера и Акиро Кишимото, в тех статьях ещё ссылки, там появилась ссылка на 200-страничную диссертацию Кишимото и тут то я осознал масштаб проблемы: решение даже весьма простых тсумего было настолько алгоритмически сложным, что в большинстве случаев вопрос стоит даже не в том, как перебрать все варианты, а как вообще найти тсумего на доске (что даже начинающий игрок делает за секунду), как понять что там надо захватывать или защищать (тоже тривиально для человека) и какие ходы имеют смысл (тоже в большинстве случаев очевидно) и если дело дошло до собственно перебора вариантов, то тсумего можно сказать решено (хотя эффективный алгоритм перебора чрезвычайно заковырист). Вообщем я понял, что моего IQ явно не хватит, чтобы решить такую задачу с ходу и я решил, что будет неплохо если получится хотя бы написать решалку для простейшего случая когда все осмысленные ходы и цель задаются заранее — даже это будет весьма полезно на goproblems.

Насколько я знаю есть совсем немного программ которые решают тсумего:

— GoTools Томаса Вольфа: до 15 возможных ходов, закрытый код, прямолинейный dfs с очень продвинутым статическим анализом.
— Tsumego Explorer Мартина Мюллера (который, кстати, 7 дан): до 30 возможных ходов, открытый код на Java (хотя непонятно где взять), продвинутый l-df-pn-r поиск с очень продвинутым статическим анализом описанным в статьях Мюллера и диссертации Кишимото.
— Fuego Мартина Мюллера: полноценный бот 2+ дана (я не могу оценить его силу поскольку он меня явно сильнее) с открытым кодом на C++ (можно скачать на SourceForge).

Ни Мюллер ни adum не слышали о каких либо js решалках (а решалка должна быть на js, чтобы её можно было встроить в goproblems), а раз так, то есть смысл попробовать её написать — тем более, что Мюллер и Кишимото написали много статей и даже программ на эту тему.

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

Для простоты, будем считать, что есть некий способ посмотреть на доску и узнать все осмысленные ходы которые надо перебрать для решения (фактически это означает то, что все такие ходы будут заданы вручную). Определим функцию R которая говорит кто выигрывает на доске b:

• если чёрные начинают и выигрывают.
• если чёрные начинают и проигрывают.

По определению R, чёрные обязаны сделать первый ход даже если он нарушает баланс в секи — это позволяет устранить ситуацию в которой белые и чёрные постоянно пасуют. Аналогично для белых. Если проигрывают и чёрные и белые — это секи. Тогда эту функцию можно рекурсивно определить так:

Выглядит немного запутанно, но суть у неё простая:

1. По определению R, чёрные вынуждены сделать какой нибудь ход, поэтому они выбирают лучший среди всех возможных ходов. Отсюда максимум по всем ходам m.
2. Затем ход переходит к белым и они могут решать делать ход или не делать — отсюда минимум. Если белые делают ход, то результат будет где b+m это доска b к которой добавили черный камень m.
3. Если же белые ход пропускают (и это не противоречит определению R), то у чёрных есть выбор: сделать ход или тоже спасовать, что завершит партию — отсюда второй максимум. Если чёрные делают ход, то получается , а если пасуют, то R(b+m) определяет кто победил (на практике это всего лишь проверка того есть ли на доске камень который надо было захватить).

Симметричная формула получается для белых. Если её посчитать «в лоб» то получится прямолинейный dfs с перебором всех вариантов, что даже для простейшего накаде из 5 точек работает весьма неспешно. Написать это можно примерно так:

function solve(board: Board, color: Color): Result {     var result = -color; // that's a loss      for (const move of board.getMovesFor(color)) {         const nextBoard = board.fork().play(move);          result = bestFor(color, // it's +color's turn, so he chooses             result,             bestFor(-color, // now it's -color's turn                 solve(nextBoard, -color), // -color makes a move                 bestFor(color, // -color can pass, but then it's +color's turn again                     solve(nextBoard, color), // +color makes two moves in a row                     estimate(nextBoard)))); // neither player makes a move     }      return result; } 

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

Теперь надо сделать так, чтобы одна и та же доска два раза не решалась. Например, найдя один раз решение для накаде из 5 точек, можно его повторно использовать если другая позиция сводится к этому накаде. Такой кеш решений обычно называется transposition table (tt). Ключом в этой таблице будет хеш доски + цвет того, кто ходит первым. Поначалу я наивно реализовал это как то так:

const tt: { [key: string]: Result } = {};  function solve(board: Board, color: Color): Result {     const key = color + board.hash();     var result = -color; // that's a loss      if (key in tt)         return tt[key];      for (const move of board.getMovesFor(color)) {         const nextBoard = board.fork().play(move);          result = bestFor(color, // it's +color's turn, so he chooses             result,             bestFor(-color, // now it's -color's turn                 solve(nextBoard, -color), // -color makes a move                 bestFor(color, // -color can pass, but then it's +color's turn again                     solve(nextBoard, color), // +color makes two moves in a row                     estimate(nextBoard)))); // neither player makes a move     }      return tt[key] = result; } 

Проблема с этим кодом в том, что есть позиции решение которых нельзя определить просто посмотрев на расположение камней. Вот например слева ход белых, но понять кто выигрывает — нельзя, потому что непонятно может ли белый захватить камень чёрных (т.е. типичное ко или цикл длиной в два хода). Эта мелкая поправка к правилам — повторять позицию нельзя — воспринимается как нечто само собой разумеющееся во время игры и не доставляет никаких сложностей, а правило супер-ко (т.е. запрет циклов длиной в несколько ходов) вообще придумано для разрешения ситуации которая может не встретиться за всю жизнь даже если каждый день играть по десять партий. Как ни странно, даже гипотетическая возможность существования циклов длиной в несколько ходов (ходов этак в 5-7) непременно реализуется во время алгоритмического перебора и если это не учитывать, то либо результат будет неправильным, либо алгоритм зациклится. Так что эта, казалось бы, виртуальная проблема удостоилась диссертации Кишимото «Correct and Efficient Search Algorithms in The Presence of Repetitions» аж на 200 страниц (собственно её то я и пытаюсь осилить).

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

Для иллюстрации я бессовестно скопировал у кого то картинку 🙂 Граф возможных ходов обычно выглядит как это дерево на картинке. Вершина в этом графе представляет собой расположение камней на доске, а цвет говорит о том, кто делает ход. Для простоты (и не нарушая общности) будем считать, что позиция 13 была решена ранее и оказалось, что черные начинают и выигрывают, при этом в процессе поиска не было обнаружено циклов. Решением является дерево (циклов ведь нет), в котором из каждой чёрной вершины ведёт один ход (больше и не надо потому как суть решения в том, что показать правильный ход в любой позиции), а из каждой белой вершины ведут все возможные ходы (решение должно доказывать, что на каждый ход белых найдётся ход чёрных который приводит к победе чёрных). Теперь допустим, что утверждение не верно и найденное решение для позиции 13 зависит от пути которым в него попадают, т.е. есть некий путь который неким образом делает решение неправильным. Если бы такой путь не пересекался с деревом решения, то он бы не мог на него повлиять — значит этот гипотетический путь содержит хотя бы одну вершину дерева. Возьмём эту какую нибудь вершину и попробуем пройти по этому пути в вершину 13 не забывая о том, что

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

Допустим, что мы начинаем из вершины 17 и пытаемся попасть в 13. Суть доказательства в том, что раз в дереве решения нет циклов, то для соединения 17 с 13 надо выйти за пределы дерева, что невозможно. Вершина 17 — белая (ну да, она красная, но будем считать, что белая) и потому все ходы из неё находятся в дереве: делаем любой ход из 17 и по прежнему остаёмся в дереве решения. Допустим мы попали в 25 — чёрную вершину. Раз вершина чёрная, то решение (правильный ход) для неё записано в кеше (из которого никогда ничего не удаляется) и поскольку мы идём по этому гипотетическому пути уже после того, что решение для 25 было найдено, мы вынуждены взять готовое решение из кеша и попасть в белую вершину которая по прежнему находится в дереве. Так мы и идём по этому гипотетическому пути пока не оказываемся в тупике откуда нет ходов.

Как видно, для того, чтобы решить проблему с циклами надо совсем немного:

1. Искать решение для пути, а не для позиции: solve(path: Board[], color: Color).
2. Если в процессе поиска натыкаемся на повторение, считаем это за поражение, но вместе с этим указываем на вершину в пути которая повторяется (достаточно запомнить индекс в пути). Смысл пары (результат, индекс) в том, что решение не безусловное, а зависит от повторения с определённой позицией.
3. Если среди всех возможных ходов все ведут к поражению, находим минимум среди всех индексов указывающих на повторение и возвращаем этот минимум.
4. Если есть выигрышные ходы, то предпочтительнее выбрать тот у которого индекс повторения как можно больше. В лучшем случае выигрыш будет безусловным, т.е. не зависеть от пути.

Этого (и простой эвристики которая максимизирует свободы своих камней и минимизирует свободы чужих) достаточно, что решить простейший carpenter square.

Чтобы решать что то более интересное, вроде первого тсумего, надо уметь учитывать ко. Один возможный подход это учитывать ко «динамически», т.е. если в процессе поиска возникает повторение, разветвлять поиск на два случая (когда есть ко угроза и когда её нет), но для этого придётся основательно перелопатить весь код. Другой подход это «статический» учёт ко:

1. Новым параметром становится количество внешних ко угроз. Скажем если этот параметр равен +3, то у чёрных на три ко угрозы больше, а если -2 — то у белых на две ко угрозы больше.
2. Если в процессе решения возникает повторение и для этого повторения есть ко угроза, она тратится, путь сбрасывается (фактически цель ко угрозы — сбросить путь и начать поиск как бы с нуля).
3. Решения в кеш записываются не в виде одного числа (+1 или -1), а бесконечного в обе стороны массива чисел где для каждого количества ко угроз записан результат: для -2 ко угроз белые выигрывают, если у белых только 1 ко угроза, то получается секи, а если ко угроз нет, то черные выигрывают. Очевидно, что если черные выигрывают при N ко угрозах, то и при N+1 они тоже выиграют. Аналогично для белых. Отсюда видно, что решение можно записать в виде двух чисел: количество ко угроз которое достаточно чёрным, чтобы выиграть (maxb), и количество ко угроз которое достаточно белым чтобы выиграть (minw). Тогда если мы ищем решение для позиции b имея k ко угроз и для b известны minw и maxb от предыдущих попыток решения, то можно сразу же вернуть ответ при k < minw (белые выигрывают) и при k > maxb (черные выигрывают), а при minw < k < maxb надо решение искать.

interface Results {     minw: number; // white wins if nkt <= minw     maxb: number; // black wins if nkt >= maxb }  const tt: { [key: string]: Results } = {};  function solve(path: Board[], color: Color, nkt: number): Result {     function solveFor(color: Color, nkt: number): Result {         const board = path[path.length - 1];         const key = color + board;         const cached = tt[key] || { minw: -Infinity, maxb: +Infinity };          if (color > 0 && nkt >= cached.maxb)             return +1; // black has enough ko treats to win          if (color < 0 && nkt <= cached.minw)             return -1; // white has enough ko treats to win          var result = -color; // that's a loss         var depth = Infinity; // where repetition occured          /* ... */          if (color > 0 && nkt < cached.maxb)             cached.maxb = nkt;          if (color < 0 && nkt > cached.minw)             cached.minw = nkt;          tt[key] = cached;         return [result, depth];     }      return solveFor(color, nkt); } 

Теперь, чтобы решить тсумего с учётом внешних ко угроз, надо сначала решить его в предположении, что ко угроз нет (nkt=0) и продолжать увеличивать или уменьшать этот параметр пока это может изменить результат. Это, теоретически, можно определять по графу решения: если найденное решение зависит от проигранного ко, то есть смысл добавить одну внешнюю ко угрозу и и решить заново. Практически же я этого не сделал, да и количество необходимых ко угроз крайне редко превышает 1, т.е. бывают задачи в которых надо выиграть два ко для решения, но это экзотика, поэтому если решить тсумего для |nk2|<2, то можно, вообщем то, говорить, что задача решена. Надо заметить, что этак 99% времени занимает поиск первого решения (обычно для nkt=0) которое заполняет кеш (tt) после чего решения для других nkt находятся почти мгновенно (даже на JS).

Вот собственно и всё. Такая вот простая решалка на JS без каких либо оптимизаций, которая на каждый чих создаёт временные объекты (чем грузит GC), а перед каждым ходом копирует всю доску целиком, способна шустро, за несколько секунд, решать тсумего с 10 свободными клетками (вроде того, что я показал в начале). На тсумего чуть большего размера она просто зависнет и будет большую часть времени грузить GC. Однако в оптимизациях такого рода я пока не вижу смысла, потому что есть куча способов сделать сам алгоритм быстрее:

• Применить продвинутый поиск в глубину: dfpn, dfpnr, ldfpnr. Мюллер пишет, что ldfpnr может осилить тсумего с 27 свободными клетками, что очень много.
• Написать алгоритмы статического анализа — я ведь даже алгоритм Бенсона ещё не реализовал. Это позволит прекращать поиск когда уже понятно кто выиграл. Это, наверно, основная причина того, что мы можем решать тсумего так быстро: обычно поиск решения в уме выглядит как перебор нескольких коротких последовательностей завершаемых оценкой «а, ну тут, очевидно, белые захвачены.»
• Придумать как искать тсумего на доске и где делать ходы. Для этого надо «лишь» внимательно понаблюдать за своим же собственным мышлением и понять как именно мы находим тсумего. Ключом к такому поиску, понятное дело, является оценка живучести группы (кучки близко расположенных камней) которая основана на определении того может ли группа сделать два глаза: тсумего всегда находится возле слабой и сравнительно большой группы (чтобы был смысл её захватывать или спасать).
• Сделать некую библиотеку трюков (tesuji): всякие там squeeze, wedge, snapback, ladder, net и т.п. Эти трюки играет огромную роль в поиске решения в уме: мы ведь не просчитываем каждый раз все возможные варианты, чтобы найти snapback — мы просто замечаем характерную комбинацию камней и проверяем можно ли из этого трюка что то «выжать.»

Кому интересно, посмотреть код можно на гитхабе. Там, честно говоря, всё надо нафиг переписать как только я пойму как организовать код решалки так, чтобы она была разбита на модули без ущерба для скорости и чтобы к ней потом можно было подключать модули ответственные за статический анализ, за распознавание секи, за разные трюки и т.д. Ну и чтобы можно было юнит тесты писать — иначе после каждого изменения я думаю «эта хрень ещё работает?» 🙂

ссылка на оригинал статьи http://habrahabr.ru/post/260935/