Игра в «кошки — мышки», поиск минимальной стратегии

в 3:20, , рубрики: haskell, игра, я пиарюсь, метки: ,

Игра в «кошки — мышки», поиск минимальной стратегииНаступил 2013 год, и мы успешно провели первый в этом году конкурс по функциональному программированию под эгидой ФП(ФП). В 2013 году конкурсы стартуют всё так же традиционно на первой длинной неделе месяца, но уже не каждого, а один раз в два месяца. Так что в 2013 году запланировано проведение шести конкурсов по ФП: в феврале (который мы сегодня и опишем), в апреле, в июне, в августе, в октябре и в декабре.

Задачу на февральский конкурс подготовил наш добрый коллега Александр Лебедев, за что ему низкий поклон, всяческие благодарности и занесение имени в Скрижали Славы ФП(ФП). Задача была из серии игр один-на-один, которую мы назвали «кошки — мышки»:

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

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

Задача: написать программу, которая рассчитывает для кошки победную стратегию, и желательно содержащую наименьшее число ходов.

Если кому-то интересна реализация решения этой задачи на языке Haskell, то добро пожаловать под кат.

Решение

Для начала определим модуль:

> module MouseAndCat where

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

> import Control.Monad
> import Control.Monad.State.Lazy

Самой важной функцией в этой задаче является функция для проверки решения, поскольку само решение ищется вообще тривиально (и это будет видно позже). Проверка решения в данном случае — это доказательство минимальности стратегии кошки.

Пусть поведение кошки описывается некоторой функцией behaviour :: Int -> [Int], которая возвращает список клеток, которые кошка должна накрывать лапой, чтобы поймать мышь. Как проверить, что это поведение правильное?

Поскольку кошке ничего неизвестно о местоположении мыши, то примем на вооружение вероятностный подход и будем брать в учёт все альтернативные положения мыши и её возможные ходы. Так для N = 4 имеем:

1) 1 1 1 1
2) 1 2 2 1
3) 2 3 3 2
4) 3 5 5 3

Здесь видно, что на втором ходе мышь могла прийти во вторую ячейку двумя способами (из первой и из третьей ячеек), а на четвёртом ходе в первую ячейку она могла придти тремя способами:

1. Выйти из второй клетки, пойти в первую, затем во вторую и обратно в первую:
[2,1,2,1].
2. [2,3,2,1].
3. [4,3,2,1].

Число способов попасть в ячейку с номером p на шаге (k + 1) определяется следующей функцией:

> ability :: Num a => a -> a -> a
> ability p k = ability (p - 1) (k - 1) +
>               ability (p + 1) (k - 1)

Когда в процесс вмешивается кошка, то у мышки становится меньше альтернатив для ходов. Каждый раз, когда кошка кладёт лапу на ячейку p, мы должны записать в неё 0, что означает, что эта ячейка не даёт вклада в будущие альтернативы мыши.

Например если игра идёт на четырёх ячейках, и кошка ходит так: [2,2,3,3,2], то после пятго хода у мыши нет альтернатив:

Было:                                1 1 1 1
Кошка положила лапу на 2: 1 0 1 1
Мышь сделала ход:             0 2 1 1
Кошка положила лапу на 2: 0 0 1 1
Мышь сделала ход:             0 1 1 1
Кошка положила лапу на 3: 0 1 0 1
Мышь сделала ход:             1 0 2 0
Кошка положила лапу на 3: 1 0 0 0
Мышь сделала ход:             0 1 0 0
Кошка положила лапу на 2: 0 0 0 0

На последнем ходе альтернативы у мыши иссякли, и кошка определённо поймала мышь.

Теперь немного о моделировании поведения мыши.

> next :: Num a => [a] -> [a]
> next ps = zipWith(+) (0:ps) (tail ps ++ [0])

Функция next считает альтернативы для ходов мыши без учёта поведения кошки.

> catImpact :: Num a => Int -> [a] -> [a]
> catImpact i ps = let (as, (_:bs)) = splitAt (i - 1) ps
>                  in  as ++ (0:bs)

Функция catImpact ставит ноль на i-ую позицию в списке альтернатив ходов мыши.

Игра моделируется функцией play, которая принимает на вход количество клеток N и список ходов кошки.

> play :: Num a => Int -> [Int] -> [a]
> play n ps = execState m $ replicate n 1
>   where  
>     m = forM_ ps $ i -> modify $ catImpact i . next 

Ну и, наконец, функция testGame проверяет поведение кошки:

> testGame :: (Int -> [Int]) -> Int -> Bool
> testGame beh n = play n (beh n) == replicate n 0

Теперь можно привести функцию, которая вычисляет один из возможных минимальных
ответов к задаче:

> answer :: (Enum a, Num a) => a -> [a]
> answer n = [2..(n - 1)] ++ reverse [2..(n - 1)]


Все заинтересованные смогут взять описанный модуль для моделирования здесь. Впрочем, если скопировать текст статьи в файл с расширением .lhs, сохранить его в кодировке UTF-8 (без BOM) и скормить компилятору языка Haskell, то всё будет хорошо, поскольку эта статья представляет собой модуль на языке Haskell в литературном стиле.

Дополнительная информация о конкурсах и ФП(ФП)

В 2013 году в работе Фонда Поддержки Функционального Программирования ФП(ФП) произошли определённые изменения, о которых необходимо сказать:

  1. Официальным блогом ФП(ФП) становится блог haskell98.blogspot.ru, с чем я всех и поздравляю.
  2. Как уже было сказано, конкурсы проводятся один раз в два месяца (по чётным месяцам года), объявление о старте конкурса производится в первую «длинную» неделю месяца, то есть такую неделю, которая содержит не менее 4-ёх дней нового месяца (1-ое число должно быть в четверг или ранее). Сам конкурс проводится в выходные в соответствии с установленным ранее регламентом.
  3. В течение 2013 года все конкурсанты будут получать баллы за своё участие. Подробно баллах и правилах их начисления написано здесь. Апелляции на тему «я буду участвовать, но баллы мне не начисляйте» не принимаются — правила едины для всех.
  4. Чуть позже придумаю ещё что-нибудь более интересное: звания, всякие ордена, ещё что-нибудь.
  5. В конце года по итогам зарабатывания баллов будет составлен список победителей, которые будут награждены чем-нибудь хорошим.

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

Да, и ещё. Альманах-2012 находится в процессе компиляции. Скоро выйдет в свет, о чём будет сообщено дополнительно. Неравнодушных прошу ждать.

Мои предыдущие статьи о конкурсах по ФП на Хаброхабре:

Автор: Darkus

Источник

Поделиться

* - обязательные к заполнению поля