Играем в Ним при помощи ленивых вычислений и бесконечных списков

Добрый вечер.

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

Зачем это нужно? Допустим, решение какой-то задачи требует обработки нескольких массивов/списков/наборов данных. Если мы описываем решение в терминах операций над конкретными элементами («a[i]=b[j]+c[j-i+1,j]»), у нас всегда есть риск упустить какой-то частный случай или совершить простейшую (и от этого вдвойне досадную) ошибку. Все наверняка хоть раз да и встречались с классическими ошибками типа «на единичку больше/меньше» и «выход за границы массива».

Если же мы сумеем сформулировать решение в терминах операций над «целыми» списками/массивами, мы не только уменьшаем описанный риск, но и, как правило, получаем более короткий и читаемый код. Впрочем, довольно вступлений, перейдем к сути.
Для иллюстрации будет использоваться язык Haskell, для полного понимания происходящего полезно экспериментировать с приводимым кодом в какой-нибудь интерактивной среде (GHC, Helium или Hugs).

Задача: реализовать оптимальную стратегию игры в Wythoff’s game. Описание игры «на пальцах» выглядит так: представим себе шахматную доску, бесконечную в направлении вправо-вниз. На какой-то ее клетке стоит ферзь. Играют двое. На своем ходу игрок может передвинуть ферзя (по обычным правилам) на любую клетку, но только в направлении влево или вверх (или влево-вверх). Выигрывает тот, кто поставит ферзя в левый верхний угол доски.

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

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

Если мы каким-то образом вычислили список координат оптимальных позиций (назовем его «winning_positions», предполагая, что он выглядит вот так: [(1,2),(3,5),(4,7),...]), то поиск оптимального хода реализуется «в лоб» (да простят меня за английские комментарии):

module Main where

import Data.List (delete)

-- | Find optimal move (da,db) for game position (a,b).
-- Here, `da' and `db' are numbers that should be
-- substracted from `a' and `b', respectively.
move a b = move' a b winning_positions

-- | Find position in the list of winning positions that
-- could be reached from (a,b) by either:
-- 1)substracting solely from `a' or `b'
-- 2)substracting simultaneously from `a' and `b'
move' a b ((x,y):rest) 
  | a == b = (a,b)
  | a == x = (0,b-y)
  | a == y = (0,b-x)
  | b == y = (a-x,0)
  | b == x = (a-y,0)
  | a-x == b-y = (a-x,a-x)
  | a-y == b-x = (a-y,a-y)
  | otherwise = move' a b rest

main = loop
loop = 
  do putStrLn "Enter two number that describe game position and press Enter"
     l <- getLine 
     let [a,b] = map read $ words l
     putStr "My move: "
     putStrLn $ show $ move a b
     loop

Дело за малым — получить список оптимальных позиций. Можно увидеть (или сходить по приведенной мною ссылке и почитать :) ), что «строка» является суммой «порядкового номера» позиции и «столбца», а столбец, в свою очередь, является минимальным числом из ряда [1..], которое еще не было использовано в качестве «строки» или «столбца».

Так и запишем (я постарался снабдить листинги гиперссылками на примеры использования задействованных функций, чтобы не перегружать текст примерами и объяснениям, так что если вы не знаете, что делают ($), map, zipWith и т.п. — кликайте на ссылки и читайте):

column = <a href="http://www.zvon.org/other/haskell/Outputprelude/zipWith_f.html">zipWith</a> (+) [1..] row
row    = not_yet_used

winning_positions = <a href="http://www.zvon.org/other/haskell/Outputprelude/zip_f.html">zip</a> row column

Осталось определить «not_yet_used» — список, в котором на позиции N стоит минимальное число, не использованное в N-1 предыдущих оптимальных позициях. Очевидно, что можно взять список [1..] и, двигаясь последовательно по списку выигрышных позиций, вычеркивать из [1..] использованные строки и столбцы. После каждого вычеркивания «выписывать отдельно» минимальное неиспользованное число (оно будет первым в оставшемся списке) и двигаться дальше. Код практически дословно повторяет сказанное:

not_yet_used = <a href="http://www.zvon.org/other/haskell/Outputprelude/map_f.html">map</a> <a href="http://www.zvon.org/other/haskell/Outputprelude/head_f.html">head</a> <a href="http://www.zvon.org/other/haskell/Outputprelude/D_o.html">$</a> <a href="http://www.zvon.org/other/haskell/Outputprelude/scanl_f.html">scanl</a> remove [1..] winning_positions
  where remove lst (a,b) = <a href="http://haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#v%3Adelete">delete</a> b $ delete a lst 

Вот и все, алгоритм реализован, и вы можете проверить, что, например, «move 12 6» выдает правильный ход «(2,0)», переводящий игрока в оптимальную позицию (10,6).

Теперь приглядимся повнимательнее к тому, как функции используют друг друга. Для вычисления «column» используется «[1..]» и «row». Для вычисления «row» используется «not_yet_used». Для нее, в свою очередь, нужны «winning_positions». Для вычисления которой нужны ... все те же «row» и «column». Всё, круг замкнулся (см. рисунок).

Получилась эдакая змея, кусающая себя за хвост. Простите, спросите вы, но как все это может работать?

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

А запускается вся эта карусель тогда, когда «scanl» из функции «not_yet_used» выдает на-гора начало своего результата — список [1..]. Первый элемент этого списка тут же попадает в значение «row», после чего можно вычислить первый элемент результата «column», после чего можно вычислить первую пару из «winning_positions», которую можно использовать для вычисления следующего значения «not_yet_used» и т.д. и т.п (см. схему после этого абзаца). При этом вам вовсе не обязательно самому рисовать подобные картинки и прослеживать зависимости — за вас это сделает компилятор :)

Получившийся в результате список оптимальных позиций является бесконечным во всех практических смыслах этого слова. Например, если попытаться его напечатать («print winning_positions»), то среда исполнения будет выводить оптимальные позиции до тех пор, пока вы ее не прервете.

Причем, для операций с бесконечными списками вовсе не требуется бесконечно много памяти :) Если скомпилировать программу, печатающую список всех оптимальных позиций и запустить ее, то можно заметить, что она занимает в памяти около 10 мб, и это значение со временем увеличивается очень плавно. А все дело в том, что значения «winnig_positions», выведенные на экран, уже не требуются для дальнейших вычислений и тут же собираются сборщиком мусора, равно как и значения списоков «row» и «column». Таким образом, в любой момент времени в памяти хранится по одному значению из списков «row», «column» и «winning_position» + в памяти находится диапазон натуральных чисел от следующего минимально-неиспользованного до максимально-использованного (его использует в своих вычислениях функция «not_yet_used»). «Удлинение» этого диапазона и вызывает увеличение объема потребляемой памяти.

А неиспользованные элементы (или непрерывные диапазоны элементов) бесконечных списков представляются в Haskell в виде так называемых thunk-ов — «ссылок» на код, который их вычислит. Когда элемент «потребляется» для какого-то вычисления, thunk заменяется на вычисленное значение. Таким образом (упрощая), для хранения списка всех натуральных чисел [1..] достаточно хранить число «1» + thunk с описанием, как вычислить последующие числа.

Надеюсь, что это краткий экскурс в ленивые вычисления с использованием бесконечных списков оказался для вас не только забавным, но и полезным. Удачи, до новых встреч!

PS
Disclaimer: данный код не является самым умным, самым быстрым или самым оптимальным способом решения поставленной задачи.

Все про українське ІТ в телеграмі — підписуйтеся на канал DOU