10 февраля сего года состоялся февральский конкурс по функциональному программированию, который был посвящён Дню научного работника. Несмотря на то, что в конкурсе приняло участие всего лишь 4 человека (с причиной этого я ещё буду разбираться), результаты хороши — по крайней мере двое участников представили достаточно хорошее решение, которое подходит в большинстве случаев. А задача была проста — написать программу, которая для заданной шахматной задачи на мат в один ход ищет этот самый ход (а ходов может быть и несколько, конечно). Ну а на затравку конкурсантам была дана простейшая задача:
Каждый раз, когда я организовываю конкурсы, предварительно я сам решаю задачу, готовя решение, которое мне самому нравится. Само собой разумеется, что я использую для программирования прекрасный язык Haskell. Так было и на этот раз, а потому сегодня я представлю вам описание набора функций для решения шахматных задач на мат в один ход. Тем более, что в архивах Hackage, вроде бы, нет модулей для работы с шахматами.
Немного о методике решения задачи сверху-вниз
В первом номере научно-практического журнала «Практика Функионального Программирования» Дмитрий Астапов опубликовал статью «Давно не брал я в руки шашек», в которой он наглядно показал один из методов программирования в функциональном стиле, когда программа разабатывается сверху-вниз от самой общей функции к мелким частностям. Этот метод является следствием техники декомпозиции задачи на подзадачи и выражения нерешённых задач через уже решённые. В функциональной парадигме этот метод применяется сплошь и рядом, а в языке Haskell он нашёл своё продолжение ещё и в том, что повсеместно можно использовать такую функцию, как undefined, которая имеет тип a и может быть подставлена взамен любого, совершенно любого выражения. Конечно, если в процессе выполнения программы поток исполнения наткнётся на неё, то программа остановится с ошибкой времени исполнения, однако тут соль в ином.
Дело в том, что в строгих функциональных языках имеет место такой принцип, как «если программа откомпилировалась, то с большой вероятностью она сразу будет работать правильно». Строгая проверка типов не позволит откомпилировать программы, в которых нарушена типизация и могут возникнуть какие-либо проблемы с указателями, неявными преобразованиям и прочим подобным. Во многих функциональных языках программирования даже нет таких идиом и программных сущностей, как указатели и неявные преобразования. А потому определения функций через терм undefined является вполне обыденным делом — это позволяет проверить программу на компилируемость. Конечно, никто не застрахован от ошибок в логике исполнения, однако это ошибки совершенно иного плана, и тут ни один транслятор не поможет.
Итак, техника проста — мы определяем функцию для решения задачи самого верхнего уровня, сразу же в теле вызывая подфункции, которых ещё нет. А эти подфункции просто выписываем и определяем как undefined. Проверяем программу компилированием, но не запускаем, конечно. Если откомпилировалось, то идём дальше и постепенно определяем все подфункции, подподфункции и т. д. до самых низовых операций. Типы данных, используемые в такой программе, определяются на ходу по мере надобности и по потребности текущих задач. Зачастую в функциях используются временные типы данных, создаваемые налету, об уничтожении которых потом позаботится сборщик мусора.
Дмитрий Евгеньевич в своей статье показал, как при помощи данной методики можно быстро написать простенькую программу, играющую в шашки. В его реализации было много ограничений, однако суть метода была показана отлично. Так что сегодня мы вооружимся этим методом для разработки набора функций, решающих шахматные задачи на мат в один ход.
Вот на этой диаграмме показаны некоторые функции (далеко не все, которые будут определены и рассмотрены в этой статье), через которые постепенно определяется главная функция для решения поставленной задачи, функция solve. Так что далее так мы и будем примерно придерживаться такого порядка.
Парсер нотации FEN и вывод позиции на экран
Прежде чем кодировать и формализовывать шахматные правила, необходимо решить чисто утилитарную задачу — каким образом считывать и как выводить на экран шахматные позиции. Стандартным способом описания шахматных позиций является нотация Форсайта-Эдвардса (FEN), которая описывает всю позицию в виде одной строки. В этой строке выделяется 6 последовательных полей, разделённых пробелами. В первом поле описывается сама доска (положение фигур) со стороны белых: по горизонталям сверху вниз указываются фигуры строчными и заглавными буквами, и при этом строчные соответствуют чёрным фигурам, а заглавные — белым. Обозначения фигур в точности соответствуют кодам из алгебраической нотации на английском языке. Пустые клетки обозначаются цифрами — сколько пустых клеток идёт подряд, такая цифра и ставится, так что тут мы имеем что-то вроде сжатия по принципу RLE. Ну и горизонтали отделятся друг от друга косой чертой «/». После описания доски идут поля для всяких ограничений: какая сторона ходит следующей, какие виды рокировок возможны, возможно ли взятие на проходе (и если да, то на какое поле), сколько полуходов прошло с предыдущего взятия или хода пешки, какой текущий номер хода. Все эти параметры в меньшей степени требуются для решения поставленной задачи, хотя, конечно, знание о рокировках и взятии на проходе необходимо.
В итоге, описание позиции на представленной выше диаграмме описывается в нотации FEN следующей строкой: "4k3/8/4K3/8/8/8/R7/8 w ---- - 0 1".
Ну, собственно, кодировать тут особо нечего. Вот определение функции, которая разбирает строку в нотации FEN и возвращает формализованное описание шахматной позиции:
parseFEN :: String -> Position
parseFEN s = let [b, sd, [wk, wq, bk, bq], ep, sm, mn] = words s
in Position (setProperCoordinates $ concatMap parseFEN' $ filter (/= '/') b)
(readSide sd)
(wk /= '-')
(wq /= '-')
(bk /= '-')
(bq /= '-')
(readCoordinate ep)
(read sm)
(read mn)
where
parseFEN' 'k' = [Just (King, Black)]
parseFEN' 'q' = [Just (Queen, Black)]
parseFEN' 'r' = [Just (Rook, Black)]
parseFEN' 'b' = [Just (Bishop, Black)]
parseFEN' 'n' = [Just (Knight, Black)]
parseFEN' 'p' = [Just (Pawn, Black)]
parseFEN' 'K' = [Just (King, White)]
parseFEN' 'Q' = [Just (Queen, White)]
parseFEN' 'R' = [Just (Rook, White)]
parseFEN' 'B' = [Just (Bishop, White)]
parseFEN' 'N' = [Just (Knight, White)]
parseFEN' 'P' = [Just (Pawn, White)]
parseFEN' c | isDigit c = replicate (read [c]) Nothing
| otherwise = []
Необходимо сразу отметить, что эта функция небезопасна. Она ожидает на вход исключительно синтаксически корректное описание шахматной позиции, и может выдать непредсказуемые результаты (вплоть до вываливания из программы с ошибкой времени исполнения) при получении синтаксически некорректной строки. Функция определена так исключительно для удобства, поскольку написание безопасной функции потребовало бы оборачивания её в какую-нибудь монаду Error и постоянного развёртывания этой монады для получения требуемого значения. А, поскольку не предполагается передавать этой функции некорректные строки, то и особого смысла наворачивать механизмы отлова ошибок и нет.
Итак, здесь сразу же предполагается, что переданная на вход строка состоит из шести «слов», разделённых пробельными символами (вызов стандартной функции words с указанием в качестве возвращаемого значения образца в виде списка из шести элементов), причём третье слово должно строго состоять из четырёх символов. Если сопоставление произошло успешно, то все компоненты образца непосредственно используются в разборе. Рассмотрим их по порядку и подробнее. Компонент b описывает расположение фигур. Из него сразу же одним махом убираются эти странные разделители горизонталей (вообще не понятно, зачем их вставили в нотацию, если и так понятно, что в каждой горизонтали ровно 8 клеток; разве что только для универсализации нотации для описания шахмат на досках иных конфигураций). Далее к каждому символу описания доски применяется локальная функция parseFEN', задача которой очевидна. Если она находит символ фигуры, она возвращает эту фигуру в конструкторе Just типа Maybe. А в случае обнаружения числа она реплицирует конструктор Nothing именно столько раз, сколько указано. В итоге получается 64 значений типа Maybe (FigureName, Side). А типы, указанные в этой паре, определяются как простые перечисления (что должно было быть вполне очевидно из определения функции parseFEN'):
data FigureName = King
| Queen
| Rook
| Bishop
| Knight
| Pawn
deriving (Eq, Enum)
data Side = Black
| White
deriving Eq
А вот сам алгебраический тип данных Position, который используется для описания шахматной позции и возвращается рассматриваемой функцией, описывается в виде декартова типа:
data Position = Position
{
board :: Board,
side :: Side,
castlingWK :: Bool,
castlingWQ :: Bool,
castlingBK :: Bool,
castlingBQ :: Bool,
enpassant :: Maybe Coordinate,
semimoves :: Int,
moveNumber :: Int
}
Здесь есть два других ещё неизвестных нам типа, а именно Board и Coordinate. Это всего лишь синонимы типов для упрощения записей. Их определения таковы:
type Board = Map Coordinate Figure
type Figure = (FigureName, Side)
type Coordinate = (Int, Int)
Итак, описание доски — это словарь из координат и фигур. Фигура — это наименование фигуры и её цвет, а координата — это пара целых чисел (от 1 до 8, конечно, но здесь этого не проверяется). Таким образом, вышеприведённое описание позиции типа Position полностью соответствует полям нотации FEN. Сначала идёт описание доски в виде словаря, потом цвет ходящей фигуры, потом четыре булевых значения, указывающих на возможность той или иной рокировки, затем возможное поле для взятия на проходе и в конце два числовых счётчика (которые у нас в программе точно уж использоваться не будут, но обрабатывать их для пущей универсальности уж надо).
Впрочем, нам надо вернуться к определению функции parseFEN. Мы ещё не рассмотрели такие функции, которые она вызывает, — readSide, readCoordinate и setProperCoordinates. Первые две тривиальны и используются для преобразования строки в заданный тип, а в данном случае в значения типов Side (перечисление) и Coordinate (синоним пары). Их определения таковы:
readCoordinate :: String -> Maybe Coordinate
readCoordinate [c, n] = if inRange ('a', 'h') c && inRange ('1', '8') n
then Just (ord c - 96, digitToInt n)
else Nothing
readCoordinate _ = Nothing
readSide :: String -> Side
readSide s | s `elem` ["w", "W"] = White
| otherwise = Black
Функция readSide определена немного слабо, но опять же это сделано для облегчения кода, чтобы не заморачиваться с обработкой синтаксических ошибок в записи FEN. Так что любой символ во втором поле нотации FEN, кроме символов w и W, будут обозначать лишь то, что ходит чёрная сторона. А вот определение функции setProperCoordinates немногим более сложно:
setProperCoordinates :: [Maybe Figure] -> Board
setProperCoordinates b = M.fromList $ map fromJust $ filter isJust $
zipWith zipper b [(v, h) | h <- [8,7..1], v String
showBoard b = border ++ foldl showLine "" (splitListBy 8 [M.lookup (v, h) b | h <- [8,7..1],
v [a] -> [[a]]
splitListBy n xs | null xs = []
| otherwise = x : splitListBy n y
where
(x, y) = splitAt n xs
Эта функция уже намного интереснее. Для начала она получает список фигур из словаря, при этом данный список состоит из 64 элементов. Для этих целей опять используется уже знакомый нам генератор, а стандартная функция получения значения из словаря lookup из модуля Data.Map (здесь обозванного как M) как раз возвращает или значение Nothing, либо значение в конструкторе Just, в данном случае пару из наименования фигуры и её цвета. Функция splitListBy разбивает список из 64 элементов на 8 подсписков, каждый длиной в 8 элементов. Это получаются горизонтали, причём они следуют от восьмой к первой. И каждая из этих горизонталей выводится на экран при помощи локальной функции showLine. Она, как это ни странно, устроена по тому же самому принципу — она выводит на экран каждый символ в горизонтали при помощи локальной функции showCell. А эта в свою очередь выводит либо символ фигуры, либо пробел (стандартная функция maybe достаёт из конструктора Just значение, а если там Nothing, то она возвращает заданное значение по умолчанию, в данном случае пробел). Всё это дело обрамляется в рамочки, чтобы доска выглядела как доска. В итоге получается что-то вроде такого (опять позиция из представленной выше задачи):
+---+---+---+---+---+---+---+---+
| | | | | k | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | K | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
| R | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | |
+---+---+---+---+---+---+---+---+
При должной сноровке и привычке такое представление шахматной позиции становится вполне понятным и быстро распознаваемым. Например, мне после окончания разработки всего модуля вполне было комфортно работать с таким видом шахмат.
Осталось рассмотреть, как работает функция showFigure. Она преобразует в строку фигуру с ассоциированым цветом, а потому должна возвращать строные буквы для чёрных фигур и заглавные буквы для белых. Вот как она это делает:
showFigure :: Figure -> String
showFigure (figure, Black) = show figure
showFigure (figure, White) = map toUpper $ show figure
instance Show FigureName where
show King = "k"
show Queen = "q"
show Rook = "r"
show Bishop = "b"
show Knight = "n"
show Pawn = "p"
Ну вот, собственно, и всё. Для чёрных фигур просто вызывается функция show из экземпляра класса Show для типа FigureName, а для белых фигур результат раоты этой же функции преобразуется к верхнему регистру.
В этом разделе осталось отметить, что здесь нарочито определялись специальные функции типа showBoard или showFigure, а не определялись для соответствующих синонимов типов экземпляры класса Show. Дело в том, что стандарт языка Haskell 98 не позволяет определять экземпляры для синонимов типов, но это можно было бы сделать при помощи расширений TypeSynonymInstances и OverlappingInstances, но практика показала, что они в данном случае работают некорректно. Наворачивать же обёртки изоморфных типов newtype не хотелось ради такой простецкой задачи.
Мат в один ход
Поскольку все необходимые сервисные функции написаны, можно приступить к кодированию непосредственно решения поставленной задачи. Как было оговорено в самом начале статьи, начнём кодировать сверху вниз. Так что вот функция для решения задачи:
solve :: [String] -> Int -> IO ()
solve ts i = mapM_ (putStrLn . (number ++) . (++ "#") . init . show . fst) $ checkmate p
where
p = parseFEN $ ts !! (i - 1)
number = case side p of
White -> "1. "
Black -> "1... "
Тут ничего особенного нет, поскольку эта функция является всего лишь обёрткой для основной функции checkmate, которая и ищет ходы, ведущие к мату. В функции же solve берётся результат работы функции checkmate над позицией, полученной в результате синтаксического анализа заданной строки с описанием позиции в нотации FEN, и выводится на экран в алгебраической записи (в нотации PGN). Для этих целей и прибавляется в начале хода единичка с одной точкой для белых и тремя точками для чёрных, а в конце хода ставится знак мата взамен знака шаха (ведь мы знаем, что функция checkmate возвращает ходы, ведущие к мату). Странная сигнатура и способ доставания строки из списка по номеру был сделан для простой вещи — для того чтобы записывать вызов функции примерно так: solve task 1, где терм task представляет собой список строк с описаниями позиций для решения:
task :: [String]
task = ["4k3/8/4K3/8/8/8/R7/8 w ---- - 0 1",
"N1n5/1kPP4/8/8/4K3/8/Q7/8 w ---- - 0 1",
"2r4r/6pp/3R4/4kpB1/1Pb5/1n4P1/2P3BP/2R3K1 w ---- - 0 1",
"7k/5Ppp/4K3/8/8/8/8/8 w ---- - 0 1",
"r1bqkb1r/pp1npppp/2p2n2/8/3PN3/8/PPP1QPPP/R1B1KBNR w KQkq - 0 1",
"3B4/8/5K1p/8/7k/5P1p/7P/8 w ---- - 0 1",
"7k/5K1p/6P1/8/8/8/8/8 w ---- - 0 1",
"Q3nknR/ppppp1pp/8/8/8/8/PPPPP1PP/4K2R w K--- - 0 1",
"5k2/Q7/7N/8/8/n7/7q/2K5 w ---- - 0 1",
"5k2/Q7/7N/8/8/n7/7q/2K5 b ---- - 0 1",
"r1bq1r2/pp2n3/4N2k/3pPppP/1b1n2Q1/2N5/PP3PP1/R1B1K2R w KQ-- g6 0 1"]
Как должно было стать ясно после изучения предыдущей функции функция checkmate должна принимать на вход описание позиции типа Position и возвращать список некоторых пар, на первом месте которых стоит нечто, описывающее ход. Собственно, можно предположить, что на втором месте в этих парах стоит описание новой позиции, полученной после совершения хода. Так оно и есть:
checkmate :: Position -> [(Move, Position)]
checkmate p = [(m, p') | (m, p') fname figure ++ showV (fst $ moveTo m) ++ showH (snd $ moveTo m)
Capture -> fname figure ++ "x" ++ showV (fst $ moveTo m) ++ showH (snd $ moveTo m)
Transform fn -> showV (fst $ moveTo m) ++ showH (snd $ moveTo m) ++ "=" ++ fname fn
PawnCapture -> showV (fst $ moveFrom m) ++ showV (fst $ moveTo m)
EnPassant -> showV (fst $ moveFrom m) ++ showV (fst $ moveTo m) ++ " e. p."
ShortCastling -> "O-O"
LongCastling -> "O-O-O"
) ++ checkSign
where
figure = fst $ moveFigure m
fname Pawn = ""
fname f = map toUpper $ show f
showV v = [chr (v + 96)]
showH = show
checkSign = if isChecked m then "+" else ""
Пять полей типа Move соответствуют: типу хода (описывается ниже), ходящей фигуре, координате клетки-источника, координате клетки-назначения и флагу шахования вражеского короля. Тип MoveType представляет собой перечисление, определяющее одну из возможных альтернатив для хода в шахматной партии:
data MoveType = SimpleMove
| Capture
| Transform FigureName
| PawnCapture
| EnPassant
| ShortCastling
| LongCastling
deriving Eq
Как видно, это почти перечисление, но только конструктор Transform, соответствующий превращению пешки, оборачивает наименование фигуры, в которую пешка превращается. Остальные конструкторы соответствуют последовательно: простому ходу (в том числе и пешкой), взятию (но не пешкой), превращению, взятию пешкой, взятию на проходе, короткой рокировке и длинной рокировке. Здесь, как видно, есть один косячок, а именно заключающийся в том, что ход фигуры и ход пешки представляет один и тот же конструктор, хотя иногда бывает удобно разделять ти два типа ходов. Однако иногда бывает удобно и не разделять, так что тут палка-то о двух концах. Некоторые из конкурсантов дали код, в котором эти два хода разделены.
Рассматривать экземпляр класса Show для типа Move особо смысла нет, поскольку он вполне тривиален, но несколько громоздок в виду необходимости по-разному представлять в виде строки разные ходы. Там, конечно же, можно было бы сделать несколько оптимизаций (например, очевидная замена постоянно встречащихся повторений типа fst $ moveFrom), однако пусть остаётся в таком виде — тратить лишнее время на отладку и причёсывание сервисных функций нецелесообразно. Лучше посвятить его реализации основных функций для решения задачи. Единственное, что надо отметить, так это то, что функция show для типа Move может давать некорректное представление хода в PGN. Это происходит тогда, когда на одну клетку могут пойти несколько одинаковых фигур, и тут описание хода просто получается неоднозначным. Вводить и нагромождать дополнительные проверки и варианты разрешения неоднозначности (либо по вертикали, либо по горизонтали) для этих целей было бы совершенное нецелесообразно, хотя это и весьма просто.Далее в определении функции checkmate видны следующие ещё не определённые идентификаторы: JustMove, allLegalMoves и kingCantEscape. Первый — это конструктор специального типа MoveMode, который пришлось ввести из-за того, что король по-разному ведёт себя при хождении и при атаке. Дело в том, что король может ходить только на свободные от вражеской атаки клетки, а вот атаковать он может и несвободные от вражеской атаки клетки, хотя ходить от на них и не может. Это ясно видно на ситуации, когда два короля разделены одной клеткой. Каждый из них воспрещает ход своему визави на смежную клетку, хотя и сам ходить на неё не может. На диаграмме справа показано, как белый король не разрешает чёрному королю ходить на клетки, отмеченные красными стрелками, но и сам он на эти клетки пойти не может. А вот на клетки, помеченные зелёными стралками, белый король вполне может пойти. Абсолютно зеркальная позиция и для чёрного короля.
Собственно, этот тип данных был введён только ради короля, для остальных фигур это совершенно неважно — они всегда могут ходить туда, куда атакуют, и наоборот атаковать туда, куда могут ходить (кроме пешки, разумеется, но с пешкой особый разговор, она тоже может ходить и атаковать по своим собственным правилам без каких-либо ограничений). Так что вполне можно было обойтись вообще типом Bool, но в функциональном программировании не принято «смешивать семантику». Создать новый тип — проще простого, так почему бы этого не сделать. Вот:
data MoveMode = JustMove
| Attack
deriving Eq
Предикат kingCantEscape получает на вход описание шахматной позиции Position и возвращает значение True, если король в данной позиции получил мат, то есть он сам не может уйти, атакующую фигуру невозможно взять и от атаки невозможно защититься. Всё это кодируется на языке Haskell примерно так же, как и записано на естественном языке:
kingCantEscape :: Position -> Bool
kingCantEscape p = null (kingMoves p king) &&
(length atks == 2 ||
(length atks == 1 &&
not (canBlockField p (fst atkr) (side p)) &&
(fn == Pawn ||
fn == Knight ||
all (c -> not $ canBlockField p c (side p))
((lineFromTo `on` fst) king atkr))))
where
king = head $ getFigures (King, side p) (board p)
atks = attakersList p (fst king) (negateSide $ side p)
atkr@((v, h), (fn, s)) = head atks
Немного страшновато, конечно. Особенно условие, которое и есть значение предиката. Но если разобраться, то здесь всё достаточно просто. Локальные переменные введены для удобства, при этом переменная king представляет собой того самого короля, относительно которого решается его судьба. Для позиции p проверяется мат королю той стророны, которая должна ходить в этой позиции. Поэтому при поиске короля использована конструкция side p. Переменная atks представляет собой список атакующих короля, причём другого цвета (вызов функции negateSide, определение которой настолько тривиально, что даже не будет приводиться здесь). Ну а переменная atkr представляет собой голову списка атакующих фигур, и зачастую это будет та самая одна атакующая фигура, которая поставила шах. Дело в том, что если на короля напали, то атакующих фигур может быть либо две, либо одна, других вариантов нет. Переменная atkr сразу же разбирается на компоненты при помощи идиомы именованных образцов.
Итак, королю поставлен мат тогда и только тогда, когда: 1) король не может сделать ни одного хода (список ходов короля пуст), и 2) выполняется следующее довольно сложное условие: 2.1) атакующих фигур две (двойной шах, от которого невозможно закрыться или уйти взятием, можно только отойти королём), или 2.2) атакующая фигура одна (в принципе, лишнее условие, поскольку уже сказано, что их либо две, либо одна, иного не дано; но для единообразия пусть будет), и невозможно взять атакующую фигуру, и выполняется ещё одно сложное условие: 2.2.1) атакует пешка (от неё нельзя защититься), или 2.2.2) атакует конь (от него тоже невозможно защититься), или 2.2.3) ни на одно из полей, лежащих между атакующей фигурой и королём (а атакующая фигура в данном случае является линейной) невозможно поставить свою фигуру. Вот это и есть формальное описание матовой ситуации.
В функции kingCantEscape вызывается некоторое количество других функций, ещё не определённых здесь. Вместе с ними ниже будут описаны и некоторые подобные функции, которые используются в тех же самых целях, но в других функциях для расчётах ходов фигур. Начнём же с функции lineFromTo. Вот её определение:
lineFromTo :: Coordinate -> Coordinate -> [Coordinate]
lineFromTo (v1, h1) (v2, h2)
| v1 == v2 = zip (repeat v1) [min h1 h2 + 1 .. max h1 h2 - 1]
| h1 == h2 = zip [min v1 v2 + 1 .. max v1 v2 - 1] $ repeat h1
| otherwise = zip [min v1 v2 + 1 .. max v1 v2 - 1] [min h1 h2 + 1 .. max h1 h2 - 1]
Как видно, она возвращает список координат клеток, находящихся между заданными. Функция опять же слегка небезопасна, так как корректно работает только для входных клеток, лежищих на одной горизонтали, вертикали или диагонали. Если ей дать две клетки, не лежищие ни на одной из шахматных линий, то она всё равно вернёт какой-то список, и там будут координаты клеток, и они даже будут расположены по какой-то диагонали, но к шахматным ходам эта диагональ не будет иметь никакого отношения. Но здесь не предполагается, что функция будет использоваться некорректным образом, поэтому никаких проверок не делается.
Далее. Вот набор функций, которые предназначены для определения того, может ли поле быть заблокировано какой-либо фигурой, а также для получения списка блокирующих фигур:
canBlockField :: Position -> Coordinate -> Side -> Bool
canBlockField = (((not . null).).) . blockersList
blockersList :: Position -> Coordinate -> Side -> [FigureAtCell]
blockersList p c s = actorsList p filterBlockers JustMove blockers c s
where
filterBlockers :: (Move, Position) -> Bool
filterBlockers (m, _) = (moveType m `elem` [SimpleMove, Capture, PawnCapture]) &&
moveTo m == c
blockers :: [(FigureName, FigureMoves)]
blockers = [(Pawn, pawnMoves), (Knight, knightMoves), (Bishop, bishopMoves),
(Rook, rookMoves), (Queen, queenMoves)]
Что интересно, функция canBlockField используется в определении функции kingCantEscape и для того, чтобы понять, можно ли забрать атакующую короля фигуру. Это можно сделать, поскольку данная функция возвращает значение True тогда и только тогда, когда заданное поле атакует какая-нибудь фигура, но не король. Собственно, это достигается при помощи использования списка фигур blockers, в котором этот самй король отсутствует.
Кто-то воскликнет страшным голосом, увидев определение функции canBlockField, в котором два раза используется левое сечение композиции. Таким я опять рекомендую ознакомиться со статьёй Дениса Москвина «Сечения композиции как инструмент бесточечного стиля», опубликованной в пятом номере журнала «Практика Функционального Программирования». Здесь же надо просто пояснить, что это определение — то же самое, что и просто not . null . blockersList, но только для функции с тремя аргументами. Кому-то не нравится такая бесточечная нотация, а кому-то и нравится…
Функция blockersList используется для получения списка тех фигур, которые могут блокировать заданную координату на заданной позиции, причём она получает и цвет, поскольку такой анализ может проводиться для обеих сторон в одной и той же позиции. Она просто вызывает обобщённую функцию actorsList, определение которой будет дано ниже. А пока обратимся к такому же набору функций, но предназначенных не для блокировки, а для атаки. Вот они:
isFieldUnderAttack :: Position -> Coordinate -> Side -> Bool
isFieldUnderAttack = (((not . null).).) . attakersList
isKingUnderAttack :: Position -> Side -> Bool
isKingUnderAttack p s = isFieldUnderAttack p king s
where
king = fst $ head $ getFigures (King, negateSide s) (board p)
attakersList :: Position -> Coordinate -> Side -> [FigureAtCell]
attakersList p c s = actorsList p filterAttackers Attack attackers c s
where
filterAttackers :: (Move, Position) -> Bool
filterAttackers (m, _) = ((moveType m == SimpleMove && fst (moveFigure m) /= Pawn) ||
(moveType m `elem` [Capture, PawnCapture, EnPassant])) &&
moveTo m == c
attackers :: [(FigureName, FigureMoves)]
attackers = [(Pawn, pawnMoves), (Knight, knightMoves), (Bishop, bishopMoves),
(Rook, rookMoves), (Queen, queenMoves), (King, kingAttacks)]
Всё абсолютно то же самое, разве что добавлена специальная функция isKingUnderAttack, которая конкретизирует функцию isFieldUnderAttack для поиска ответа на вопрос, под шахом ли находится король. Поскольку для решения предложенной задачи именно на этот вопрос надо отвечать часто, то и надо выделить отдельную функцию. В остальном же всё точно так же, как и в функциях предыдущего блока с поправкой на правила атаки: в список атакующих фигур добавлен король со своей функцией атаки, а в перечень атакующих ходов добавлено взятие на проходе, но удалён обычный, не атакующий ход для пешки, ибо она обычным ходом не атакует никого.
А вот и обобщённая функция actorsList, которая была написана для того, чтобы абстрагировать общую функциональность двух функций blockersList и attakersList. Получилось несколько монструозно, но тем не менее:
actorsList :: Position -> ((Move, Position) -> Bool) -> MoveMode
-> [(FigureName, FigureMoves)] -> Coordinate -> Side -> [FigureAtCell]
actorsList p p' mm movers c s = map ((m, _) -> (moveFrom m, moveFigure m)) $
filter p' $
allLegalMoves p{side = s} mm movers
Само-то определение ещё ничего, а вот сигнатура немного ужасает, конечно. Функция получает на вход позицию, предикат для фильтрации пар (ход, позиция), режим хода (просто ход или атака), список фигур для осуществления ходов, координату для проверки действия и цвет стороны, фигуры которой проверяются. Возвращает она список фигур со своими координатами. Соответственно, для функции blockersList она возвращает список фигур, блокирующих заданное поле, а для функции attakersList — список фигур, атакующих заданное поле. И это, как было показано ранее, не одно и то же.
Ну а вот просто перечень фигур с их обычными ходами:
figures :: [(FigureName, FigureMoves)]
figures = (King, kingMoves) : blockers
Этот список включает в себя неатакующий ход короля и используется для получения всех возможных ходов заданной стороны на заданной шахматной позиции. Это будет видно чуть позже.
Теперь мы можем перейти к написанию функций, вычислящих ходы фигур. В процессе этого придётся ещё раз написать небольшой набор сервисных функций, но они будут простым. Сейчас же посмотрим на определение функции allLegalMoves, которая принимает на вход описание позиции, режим хода и список пар (название фигуры, функция её хода), а возвращает список пар (ход, позиция после него). Её определение таково:
allLegalMoves :: Position -> MoveMode -> [(FigureName, FigureMoves)] -> [(Move, Position)]
allLegalMoves = ((concatMap . uncurry).) . figureMoves
Опять немного пугающе, опять сечение композиции, а и ещё какая-то странная функция uncurry, которая превращает заданую ей на вход функцию в некаррированный вариант её же, то есть получающий вместо двух аргументов пару, составленную из них. Но это обычное дело, поскольку часто данные хранятся в парах, а их надо обрабатывать функциями, которые принимают аргументы в обычном каррированном стиле. Как видно, эта функция представляет собой всего лишь обёртку для функции figureMoves, которую и надо рассмотреть самым внимательным образом:
figureMoves :: Position -> MoveMode -> FigureName -> FigureMoves -> [(Move, Position)]
figureMoves p mm fn moves = [(m{isChecked = ic p'}, p') | f <- getFigures (fn, side p) $ board p,
m Board -> [FigureAtCell]
getFigures f b = filter ((_, f') -> f' == f) $ M.toList b
А вот функция applyMove не так проста, как хотелось бы. И всё дело опять в разнообразии шахматных правил для различных ситуаций. В её определении есть попытка кое-как оптимизировать вычисления при помощи локальных функций, выполняющих повторяющиеся действия, однако всё равно она получилась весьма громоздкой для функционального программирования. Вот её определение:
applyMove :: Position -> Move -> Position
applyMove p m
= case moveType m of
SimpleMove -> Position b1 s (c castlingWK White) (c castlingWQ White)
(c castlingBK Black) (c castlingBQ Black) ep sm mn
Capture -> Position b1 s (c castlingWK White) (c castlingWQ White)
(c castlingBK Black) (c castlingBQ Black) Nothing 0 mn
Transform fn -> Position (b2 fn) s (c castlingWK White) (c castlingWQ White)
(c castlingBK Black) (c castlingBQ Black) Nothing 0 mn
PawnCapture -> Position b1 s (c castlingWK White) (c castlingWQ White)
(c castlingBK Black) (c castlingBQ Black) Nothing 0 mn
EnPassant -> Position b3 s (c castlingWK White) (c castlingWQ White)
(c castlingBK Black) (c castlingBQ Black) Nothing 0 mn
ShortCastling -> Position b4 s (c castlingWK White) (c castlingWQ White)
(c castlingBK Black) (c castlingBQ Black) Nothing sm mn
LongCastling -> Position b5 s (c castlingWK White) (c castlingWQ White)
(c castlingBK Black) (c castlingBQ Black) Nothing sm mn
where
s = negateSide $ side p
h = initialH $ side p
b1 = replaceFigure (board p) (moveFrom m) (moveTo m) (moveFigure m)
b2 fn = replaceFigure (board p) (moveFrom m) (moveTo m) $ ((_, s') -> (fn, s')) (moveFigure m)
b3 = M.delete (second (pawnStep s) (moveTo m)) b1
b4 = replaceFigure b1 (8, h) (6, h) (Rook, side p)
b5 = replaceFigure b1 (1, h) (4, h) (Rook, side p)
c p' s' = p' p && not (fst (moveFigure m) == King || (fst (moveFigure m) == Rook &&
(moveFrom m `elem` [(1, initialH s'), (8, initialH s')])))
ep = if fst (moveFigure m) == Pawn &&
((snd (moveTo m) == 4 && side p == White) ||
(snd (moveTo m) == 5 && side p == Black))
then Just (fst $ moveTo m, pawnStep s $ snd $ moveTo m)
else Nothing
sm = case fst (moveFigure m) of
Pawn -> 0
_ -> semimoves p + 1
mn = case side p of
White -> moveNumber p
Black -> moveNumber p + 1
Вот как-то так. Само определение функции крайне просто — в зависимости от типа хода она возвращает новую позицию. А все вычисления производятся в локальных функциях. В этих функциях вычисляются все компоненты описания новой позиции. Вот краткое описание локальных функций, из которого станет ясно, зачем и почему они написаны именно так:
s — противоположный цвет для текущего цвета позиции.
h — начальная горизонталь для заданного цвета.
b1 — доска, получающаяся при простом ходе любой фигуры, взятии и взятии пешкой. Получается из доски заданной позиции простым перемещением фигуры и для взятие с заменой ею вражеской фигуры. Замена производится автоматически внутренними методами словаря Data.Map.
b2 — доска, получающаяся при превращении пешки. Отличается от b1 тем, что перемещение фигуры с одной позиции на другую сопровождается и заменой наименования фигуры, а оное наименование передаётся в виде аргумента.
b3 — доска, получающаяся при взятии на проходе. Отличается от доски b1 тем, что удаляемая с доски фигура стоит на другой клетке, и её удаление приходится делать вручную.
b4 — доска, получающаяся после короткой рокировки. Необходимо вручную перемещать ладью.
b5 — доска, получающаяся после длинной рокировки. Также необходимо вручную перемещать ладью.
c — флаг возможности рокировки. Проверяется как текущее значение флага со связкой И с условиями неперемещения короля и ладей.
ep — поле для взятия на проходе. Вычисляется только для хода пешки с начальной своей позиции на два шага вперёд. Для остальных случаев равно значению Nothing.
sm — счётчик полуходов, который обнуляется каждый раз, когда ходит пешка, либо происодит взятие. В остальных случаях всегда увеличивается на единицу.
mn — счётчик ходов, который увеличивается на единицу при каждом ходе чёрных.
Хорошо определение функции replaceFigure, которая заменяет одну фигуру другой на заданной доске. Хотя оно читается несколько необычно, но плавно делает то, что требуется:
replaceFigure :: Board -> Coordinate -> Coordinate -> Figure -> Board
replaceFigure b from to f = M.insert to f $ M.delete from b
Здесь образцы from и to представляют собой координаты клеток, откуда и куда перемещается фигура f соответственно. Так что вызов M.delete удаляет из словаря фигуру по координате (помните, координаты использутся в качестве ключей словаря). А вызов M.insert вставляет заданную фигуру на новое поле. При этом если там уже стоит какая-либо фигура (то есть происходит взятие), то функция M.insert просто перезаписывает фигуру, и старая как бы автоматически пропадает с доски.
Теперь несколько определений сервисных функций, о которых было упомянуто ранее. Они все простешие и используются исключительно для упрощения записей. Вынесены они в отдельные верхнеуровневые функции только лишь потому, что используются в нескольких разных функциях. Соответственно, эти сервисные функции предназначены для: получения начальной горизонтали для заданной стороны, получения следующей горизонтальной координаты для хода пешки для заданной стороны, получения горизонтальной координаты для первого хода пешки на две клетки для заданной стороны, определения возможности пешке всё ещё двигаться без надобности превращения, определения того, стоит ли пешка всё ещё на своей начальной позиции. Вот их определения, каждое занимает по две строки кода:
initialH :: Side -> Int
initialH White = 1
initialH Black = 8
pawnStep :: Side -> Int -> Int
pawnStep White h = h + 1
pawnStep Black h = h - 1
pawnStep' :: Side -> Int -> Int
pawnStep' White h = h + 2
pawnStep' Black h = h - 2
pawnCanMove :: Side -> Int -> Bool
pawnCanMove White h = h 2
pawnAtInitial :: Side -> Int -> Bool
pawnAtInitial White h = h == 2
pawnAtInitial Black h = h == 7
Тут, собственно, и обсуждать нечего, поэтому надо плавно перейти к функциям для рассчёта ходов фигур. Пойдём с начала, то есть от пешки к королю. Вот непростая функция для расчёта ходов пешки:
pawnMoves :: FigureMoves
pawnMoves p (c@(v, h), f@(_, s)) = step1 ++ step2 ++ ep ++ pc (-) ++ pc (+) ++ t
where
step1 = [Move SimpleMove f c (v, pawnStep s h) False |
isNothing (M.lookup (v, pawnStep s h) (board p)),
pawnCanMove s h]
step2 = [Move SimpleMove f c (v, pawnStep' s h) False |
isNothing (M.lookup (v, pawnStep s h) (board p)),
isNothing (M.lookup (v, pawnStep' s h) (board p)),
pawnAtInitial s h]
ep = case enpassant p of
Nothing -> []
Just (v', h') -> [Move EnPassant f c (v', h') False |
v `elem` [v' - 1, v' + 1],
h == pawnStep s (pawnStep' s $ pawnStep s $ initialH s)]
pc o = case M.lookup (v `o` 1, pawnStep s h) (board p) of
Nothing -> []
Just (fn', s') -> [Move PawnCapture f c (v `o` 1, pawnStep s h) False | s /= s']
t = case (M.lookup (v, pawnStep s h) (board p), pawnAtInitial (negateSide s) h) of
(Nothing, True) -> map (fn' -> Move (Transform fn') f c (v, pawnStep s h) False) $ enumFromTo Queen Knight
_ -> []
Как видно, здесь использована та же самая техника, как и при определении функции applyMove, только в ещё более вычурном варианте. Абсолютно все расчёты делаются в локальных функциях, а в основном определении результаты локальных функций просто конкатенируются. Так что имеет смысл опять просто рассмотреть все локальные функции по порядку:
step1 — обычный ход пешки вперёд на одно поле. Совершается только тогда, когда непосредственно перед пешкой не стоит никакой другой фигуры.
step2 — обычных ход пешки вперёд на два поля. Совершается только тогда, когда пешка стоит на своей первоначальной позиции и на два поля вперёд перед ней нет никаких других фигур.
ep — взятие на проходе. Осуществляется только тогда, когда взятие на проходе разрешено в исследуемой шахматной позиции, а также пешка стоит как раз на таком поле, откуда она может осуществить взятие на проходе вражеской пешки.
pc — обычное взятие пешкой, причём в качестве параметра передаётся операция (+) или (-), что соответствует взятию вправо или влево. Такой ход пешки может быть осуществлён только тогда, когда на следующей горизонтали справа или слева стоит вражеская фигура.
t — превращение пешки. Осуществляется тогда, когда пешка ходит на один шаг вперёд с предпоследней для себя горизонтали. Пешка может превратиться в любую фигуру от коня до ферзя.
Само собой разумеется, что использование определённых ранее сервисных функций для различных вариантов ходов пешки позволяют написать все эти локальные функции для обеих сторон, передавая в качестве параметра цвет стороны, и при этом горизонтали и направление движения пешек будут рассчитываться абсолютно правильно.
Следующая фигура — конь, который ходит буквой «Г». Функция для рассчёта его ходов менее сложна, чем предыдущая:
knightMoves :: FigureMoves
knightMoves p (c@(v, h), f@(fn, s)) = concatMap (tryField p JustMove f c) knightMoves'
where
knightMoves' = filter ((v', h') -> v' >= 1 && v' = 1 && h' <= 8)
[(v `f` d, h `g` (3 - d)) | f <- [(+), (-)],
g <- [(+), (-)],
d Coordinate -> FigureAtCell -> Int -> Int -> [Move]
linearAttack p c ((v', h'), f@(_, s)) dv dh
= if v'' >= 1 && v'' = 1 && h'' Move SimpleMove f c (v'', h'')
False : linearAttack p c ((v'', h''), f) dv dh
Just (fn', s') -> [Move Capture f c (v'', h'') False | s /= s']
else []
where
v'' = v' + dv
h'' = h' + dh
Здесь есть одна тонкость. Образец c, обозначающий второй аргумент используется для запоминания начальной позиции фигуры, для которой рассчитываются ходы. Это требуется для того, чтобы правильно указать, с какого поля пошла фигура. А сам алгоритм простой — функция просто рекурсивно перебирает поля по заданной приращениями линии и останавливается либо тогда, когда натыкается на свою фигуру (возвращает пустой список), либо на вражескую (возвращает взятие). В остальных случаях она возвращает простой ход и снова запускает ту же самую функцию с новой координатой для приращения. Хотя можно было бы обойтись и одной начальной координатой, передаваемой в качестве аргумента, а распространять линию можно было при помощи увеличения абсолютного значения приращений на 1 при каждом шаге (и на 0, если приращение нулевое, конечно же).
Что ж, остался король. Как уже было неоднократно упомянуто, король является особенной фигурой, поэтому для него будет реализовано две функции. Первая функция обычная, как для всех остальных фигур. Единственное, чем она отличается, так это тем, что в ней производится проверка того, может ли король ходить на клетку, не будет ли ему там шах. А вот вторая функция предназначена для получения атакующих ходов короля, даже таких, которые он и не сможет совершить (ну об это уже сказано немало). Вот определения этих функций. Как и предполагалось, первая вышла громоздкой, а вторая очень даже и нет:
kingMoves :: FigureMoves
kingMoves p (c@(v, h), f@(fn, s))
= lc ++
sc ++
concatMap (tryField p JustMove f c)
(filter (c' -> let p' = p `applyMove` Move SimpleMove f c c' False
in not $ isFieldUnderAttack p' c' s') kingMoves')
where
s' = negateSide s
kingMoves' = delete c $ (liftM2 (,) `on` adjacent) v h
adjacent i = [max 1 (i - 1) .. min 8 (i + 1)]
lc = let castling = case s of
White -> castlingWQ
Black -> castlingBQ
in [Move LongCastling f c (v - 2, h) False |
castling p,
c == (5, initialH s),
not $ isKingUnderAttack p s',
not $ isFieldUnderAttack p (4, initialH s) s',
all (v' -> isNothing $ M.lookup (v', initialH s) (board p)) [2..4],
M.lookup (1, initialH s) (board p) == Just (Rook, s)]
sc = let castling = case s of
White -> castlingWK
Black -> castlingBK
in [Move ShortCastling f c (v + 2, h) False |
castling p,
c == (5, initialH s),
not $ isKingUnderAttack p s',
not $ isFieldUnderAttack p (6, initialH s) s',
all (v' -> isNothing $ M.lookup (v', initialH s) (board p)) [6, 7],
M.lookup (8, initialH s) (board p) == Just (Rook, s)]
kingAttacks :: FigureMoves
kingAttacks p (c@(v, h), f) = concatMap (tryField p Attack f c) kingAttacks'
where
kingAttacks' = delete c $ (liftM2 (,) `on` adjacent) v h
adjacent i = [max 1 (i - 1) .. min 8 (i + 1)]
Замыкания lc и cs дают ходы для длинной и короткой рокировки соответственно. Здесь особо разъяснять нечего, поскольку эти локальные функции просто формализуют правила рокировки и осуществляют проверку того, можно ли осуществить рокировку в принципе (соответствующий флаг из описания позиции p), либо в данном конкретном случае (не поставлен ли шах, не идёт ли король через атакованное поле, не загорживает ли королю или ладье кто-нибудь проход). Там ещё есть проверка на наличие ладьи, но в этом, конечно же, необходимости нет (кто скажет, почему?).
В функции kingMoves есть одна сложность, которую надо прочувствовать. В ней при помощи конструкции let ... in рассчитывается следующая позиция после хода короля. И для этой следующей позиции установлено условие, что король не может ходить под вражескую атаку. Только в этой функции делается предпросмотр на один ход вперёд. А вот в функции kingAttacks нет ничего сложного. Просто проверяются все клетки вокруг короля, к которым применяется уже упоминаемая ранее функция tryField. А в функции kingMoves используется вызов той же функции. Поэтому рассмотрим её подробно:
tryField :: Position -> MoveMode -> Figure -> Coordinate -> Coordinate -> [Move]
tryField p mm f@(fn, s) c c'
= case M.lookup c' (board p) of
Nothing -> [Move SimpleMove f c c' False]
Just (_, s') -> if s' == s
then case mm of
JustMove -> []
Attack -> [Move SimpleMove f c c' False]
else [Move Capture f c c' False]
Собственно, относительно этой функции уже всё объяснено. Она проверяет наличие на целевой клетки фигуры. Если там никого нет, то она возвращает просто ход на ту клетку. Если же там стоит какая-либо фигура, то проверяется её цвет. В случае вражеского цвета безусловно возвращается ход-взятие. В случае если на целевой клетке стоит своя фигура, то в зависимости от режима хода возвращается либо пустой список (то есть отсутствие хода в принципе), либо атакующий ход, и это, конечно же, обозначает, что фигура защищает свою фигуру.
На этом, собственно, всё. Все необходимые определения сделаны, можно решить задачи. Хоть по одной, хоть всем скопом. Например:
Checkmate> mapM_ (solve task) [1..11]
1. Ra8#
1. d8=N#
1. Bf4#
1. f8=Q#
1. f8=R#
1. Nd6#
1. Kg6#
1. g7#
1. O-O#
1. Rf1#
1. Qf7#
1... Qc2#
1. hg e. p.#
Заключение и бонусы
Статья закончена. Фреймворк для шахматной игры написан. Всякий желающий может скачать весь модуль по данной ссылке. Весь модуль полностью откомментирован, так что с пониманием не должно быть никаких проблем. Ну и как всегда я готов ответить на любые конструктивные вопросы, заданные в комментариях или по личной почте.
А напоследок бонус. Если кто подумал, что мы решили узкоспециализированную задачу, то это не так. Вот определение функции, которая решает задачи на мат в два хода:
solve2 :: [String] -> Int -> IO ()
solve2 ts i = mapM_ (putStrLn . (++ "#") . init . numberize . map show . fst) $ checkmate2 p
where
p = parseFEN $ ts !! (i - 1)
number = case side p of
White -> "1. "
Black -> "1... "
numberize [m1, m2, m3] = number ++ m1 ++ case side p of
White -> " " ++ m2 ++ " 2. " ++ m3
Black -> " 2. " ++ m2 ++ " " ++ m3
checkmate2 :: Position -> [([Move], Position)]
checkmate2 p = [([m1, m2, m3], p''') | (m1, p') <- allLegalMoves p JustMove figures,
(m2, p'') <- allLegalMoves p' JustMove figures,
(m3, p''') <- allLegalMoves p'' JustMove figures,
isChecked m3,
kingCantEscape p''']
Здесь общий паттерн кода чем-то напоминает монадические вычисления, и, действительно, можно разработать свой монадический тип, который будет предназначен для вычисления разнообразия шахматных ходов. Но это дело далеко выходит за рамки настоящей статьи. Тем не менее, функция solve2 выдаёт список абсолютно всех ходов, даже если они совершенно нелогичные с точки зрения человека-шахматиста. Главное, чтобы все ходы соответствовали формальным правилам шахмат. Тем, кто хочет поэкспериментировать с этой функцией, вот несколько позиций:
task2 :: [String]
task2 = ["r1bk1b1r/ppp2ppp/2p5/8/4n1q1/8/PPPB2PP/2KR1B1R w ---- - 0 1",
"kb6/1p1B4/1K6/8/p1Q5/8/8/3q4 w ---- - 0 1",
"3r4/p1p4p/1pb31k/4R3/2P3B1/2Q3PP/P2q1P2/6K1 w ---- - 0 1",
"2Q2qk1/1p4pp/p7/5P1B/2pP1r2/3b2K1/PP5P/8 w ---- - 0 1",
"2r1kbr1/2p2ppp/p1p5/3NpqB1/5P2/8/PPP3PP/2KR3R w ---- - 0 1",
"8/5Rpk/P1p5/2Pp3q/4p2p/4P1P1/1Q3PKP/8 b ---- - 0 1",
"r1b3k1/ppp2p2/1q6/4B1rb/8/8/PPP2P1P/2KR2NR w ---- - 0 1",
"5r1k/8/2r1B1RK/6N1/8/8/8/8 w ---- - 0 1",
"r7/pN6/k1b5/3p1n2/P2p1B2/2P5/2P2PrP/1R1K4 w ---- - 0 1",
"8/r1q4p/7k/3p1Q2/2pP4/1p3PP1/1P3K2/8 w ---- - 0 1"]
Если вы хотите дополнительно отблагодарить автора, но не знаете как, то вам сюда.Мои предыдущие статьи о конкурсах по ФП на Хаброхабре:
Решение задачи о перегорающих лампочках на языке Haskell
Фреймворк для решения задач о переправах на языке Haskell
Конструирование и вычисление арифметических выражений на языке Haskell
Расшифровка кода на языке Haskell (конкурс по ФП в январе 2012)
P. S.: Самый первый черновой вариант этой статьи был написан, когда мой сын участвовал в полуфинале Первенства Москвы по шахматам среди детей до 8 лет :).
