Игра Калах, самообучающийся алгоритм ИИ Опции

[Lapp]

Всем привет,
сыграем в Калах?
Эта игра меня давно занимает, причем с определенной точки зрения. Но сначала о том, что это за игра (не все, может, знакомы). Она очень древняя, пришла (как чуть ли не все игры) с Востока. Известна также под названием Ман-Кала, а также иногда пишут два "л": Каллах. Играют двое на специальной доске камнями. Доска имеет два ряда лунок (по шесть), а по бокам две большие лунки (именно они и называются "калах"). Доска ставится между двумя игроками. Ближайший ко мне ряд лунок - мой, другой - противника. Правый калах - мой, левый - противника.

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

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

Игра заканчивается либо когда в одном из калахов скопилось более половины всех камней (то есть больше 36), и тогда этот игрок выиграл, либо когда в лунках игрока кончились камни, и тогда он проиграл. Вот, кажется, и все правила. На рисунке изображено состояние после моего хода лункой №1. Сейчас снова мой ход.

Игра продавалась у нас, наверняка продается и сейчас. Играть интересно, ситуация на доске меняется иногда молниеносно, предсказать игру на пару ходов очень нелегко. Разумеется, есть и программные реализации (поройтесь в сети). В свое время все сотрудники нашего головного предприятия по производству ЭВМ были страстно увлечены ее электронной версией, проводились соревнования.. Понятно, что предсказание хода в данном случае трудно для человека, но не для машины - сбивает с толку необходимость постоянно вести подсчеты, но граф этой игры ветвится не так сильно, так как всякий раз есть не более шести возможных ходов.

Вот именно эта особенность (малое количество ходов) и привлекла меня. Теперь расскажу о другом..
Когда-то давно я прочитал в книжке моего кумира Мартина Гарднера, как сделать машину для игры крестики-нолики. Ничего удивительного, если не сказать, что это было написано где-то в 60-е годы.. Машину предлагалось делать из.. спичечных коробков! Меня заинтересовал принцип. А принцип состоял в следующем..

По сути, это был метод кнута и пряника. Нужно было записывать все комбинации, возникающие в игре, зарисовывать их каждую на отдельном коробке. При игре 3х3 это возможно . Но не только каждой комбинации соответствовал отдельный коробок, но и каждому возможному в ней ходу тоже. Перед процессом обучения "машины" в каждый коробок нужно было положить по три горошины. Потом нужно было несколько раз сыграть самому (с кем-нить) в эту игру, при каждом ходе фиксируя возникшие комбинации. В конце партии, когда результат (кто выиграл) уже ясен, нужно во все коробки, на которых обозначены ходы выигравшего игрока, должить по горошине. Из всех же тех, которые соответствуют ходам проигравшего игрока - наоборот, вынуть горошину. Я сейчас не ручаюсь за точность повторения алгоритма, но принцип тот.

После достаточного количества сыгранных партий "машина" готова к игре - разумеется, вашими руками, но своим "мозгом". Игрок, играющий за машину должен всякий раз открывать все коробки, соответствующие текущему положению на доске, и выбрать из них тот, в котором больше всего гороха. Затем сделать тот ход, который обозначен на этом коробке.

Не правда ли, все просто? Если мое объяснение вам таковым не показалось, найдите книжку Гарднера .

Итак, я решил применить тот же принцип к Калаху. Это было давно, жутко давно - когда я впервые дорвался до персоналки. Тогда я это сделал на Бейсике. И ведь работало! Конечно, полный вариант мне был тогда не по зубам - не хватало ни памяти, ни производительности - но я извернулся. Придумал калах-3. Как вы, может, уже догадались, это вариант игры с тремя лунками, в каждой из которых в начале лежит 3 камня.

Да, не очень интересно.. Именно поэтому я помнил это и ждал момента, когда машины подрастут. Тогда я делал все на машине с памятью 512 КБ (аналог DEC Pro 350, кажется). Нынешние машины имеют памяти примерно на три порядка больше (а моя и вообще в 4000 раз). Так что я решил, что момент настал. И сделал все заново. Теперь на Паскале (с прицелом, чтоб выложить сюда ).

Ну вот, теперь несколько слов о самой проге, да и хватит пока - устал долбить по клаве, однако..

Собсно, а что там говорить? Разберетесь.. Это Калах-4 (легко превращающийся в Калах-5,6 и т.д. заменой одной констаныт). Интерфейс крайне уродский, но не хочу доводить его до ума в текстовой версии. Во время игры можно только вводить номер лунки. Между играми можно кое-что еще (хелп по нажатии h). Советую переходить в режим картинки (буква p). Код непричесанный, невычищенный - короче, рабочий, не судите строго. Извиняюсь за отсутствие комментариев. Если будет интерес - снабжу.

Enjoy, как грится! И - жду ваших коментариев.. улучшений.. и т.п.

Да, забыл сказать.. Программа сама по себе страшно тупая - она ходит случайным образом. Чтоб ей поумнеть, нужен файл с накопленными данными. Файл у меня есть (для Калах-4), он весит почти 30 МБ - но вы можете сделать его и сами.

Самый интересный вопрос - оценка памяти, необходимой для обучения Калах-5 и 6. Я пока не соображу, как правильно оценить. Если верно, что каждый новый уровень требует примерно на 2.5-3 порядка большей памяти (как при переходе от 3 к 4), то для Калаха-5 потребуется больше 10 ГБ.. И такого количества операционки у меня пока нету.. Но мне кажется, что множитель не постоянен, он растет, но не спец по этим вопросам..
Итак - ваши соображения, господа?..

Старый вариант программы удален! Новый в посте №16

[Lapp]

не знала что на форуме можно писать пост без входа в систему. ...
я подумала, что достану тебя, если буду задавать слишком много вопросов, а их у меня много.

Можно отвечать, нельзя начинать тему. У пользователей все же есть довольно много преимуществ. Например, можно повышать репутацию другим (после 25 постов) .
Вполне возможно, что достанешь . Совет: если ты покажешь, что хоть немного вникла в суть, а не просто транслируешь мне вопросы преподавателя - в этом случае вероятность "доставания" будет меньше )). Поменьше условностей, побольше реальной заинтересованности )).

переменная Num: boolean?
ll: longint? о каких линиях идет речь: 'Lines: ', ll?

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

ll - количество записей в БД. По терминологии баз данных это lines, то есть линии.

[cameron]

Вполне возможно, что достанешь . Совет: если ты покажешь, что хоть немного вникла в суть, а не просто транслируешь мне вопросы преподавателя - в этом случае вероятность "доставания" будет меньше )). Поменьше условностей, побольше реальной заинтересованности )).

преподаватель еще не видел программы, вопросы мои.
по-моему, очень много усилий пошло на Picture, хотя режим без "картинки" тоже хорош. Но ты не пошел по пути наименьшего сопротивления )

[Lapp]

преподаватель еще не видел программы, вопросы мои.
по-моему, очень много усилий пошло на Picture, хотя режим без "картинки" тоже хорош. Но ты не пошел по пути наименьшего сопротивления )

Ужжасно приятно .
Картинка - ерунда, там много мозгов не требуется, делается за пару часов )). Надо бы переделать, сделать не в тексте.
Ты хорошо разобралась с БД? Вот там мозги нужны в полной мере.

[cameron]

на счет записей в БД.
Store[NStore]^.Len:=0 - тут мы создаем пустой блок и используем селектор записи, Len - имя поля. записи внутри блоков упорядочены по имени поля. Так?

[Lapp]

Store[NStore]^.Len:=0 - тут мы создаем пустой блок

Да, именно. Собственно, вся функция NewBlock служит этой цели.

function NewBlock:boolean;
begin
  if NStore<LStore then begin {если пустых блоков (то есть ссылок на блоки) пока хватает}
    Inc(NStore);                {увеличиваем кол-во блоков}
    New(Store[NStore]);         {размещаем новый блок в памяти}
    Store[NStore]^.Len:=0;      {инициализируем его нулевой длиной}
    NewBlock:=true              {возвращаем true, как признак того, что новый блок сделан}
  end
  else NewBlock:=false        {блок не сделан (закончились), возвращаем false}
end;

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

и используем селектор записи, Len - имя поля

Оно, конечно, верно, но никакой смысловой нагрузки не несет, извини.. Нужно сказать, для чего это поле.
Len - поле, обозначающее реальную длину (то есть заполненность) данного блока. Все блоки одинаковы по длине, если говорить о занимаемой памяти. Но реально в блоке может быть разное количество записей - от 0 до LBlock. Блок действительно создается пустым, то есть с Len=0, а потом при добавлении каждой записи мы увеличиваем Len на 1. Когда Len для данного блока достигает LBlock, мы его сплитим.

записи внутри блоков упорядочены по имени поля. Так?

cameron, вот тут кто-то из нас что-то совсем не понял, и я сильно подозреваю, что это был не я . Как можно вообще записи упорядочивать по имени поля? Какой в этом смысл? Имя поля дается при написании кода и смысл его только в том, чтоб оно напоминало о том, что внутри.

Записи рассортированы по содержимому поля с именем Brd (это сокращение от англ board - доска). Помнишь, ты спрашивала про функцию Compare? Она служит именнно этой цели. Про две различные ситуации на доске можно сказать, какая из них больше, если условиться о мере. Мера в данном случае представляет собой 2r-значное число, записанное как бы в r²-ичной системе счисления. Если тебе стало нехорошо по прочтении этого - не волнуйся, откинься на спинку кресла и сделай глубокий вдох )) - сейчас объясню.

Допустим, что у нас калах ранга 4. Вот текущая ситуация:

    3  12   0   1 
 6                 8
    1   0   5   0 

Как я уже говорил раньше, калахи не учитываем - отбрасываем их. Остаются две строчки: нижняя (считаем первой) и верхняя (вторая). Записываем эти строчки в одну подряд:

 1   0   5   0   3  12   0   1

Я специально использовал хотя бы одно число, большее 9 (это 12), чтобы у тебя не сложилось впечатления, что тут можно обойтись цифрами (от 0 до 9). Итак, каждая ситуация на доске - это вот такая запись. Мы их упорядочиваем как обычные числа - поразрядно слева направо. Разберись, как работает Compare (англ. сравнивать).
И рассмотрим еще одну ситуацию, вот такую:

    1   0   1   0 
14                13
    3   0   0   0 

- из которой мы тоже сделаем такую же строчку:

 3   0   0   0   1   0   1   0

Теперь вопрос: какая из этих двух ситуаций будет считаться большей, а какая меньшей?

Удачи тебе )).

[offtop]а ты Cameron в честь кого? Diaz или James? или еще как?
Из старого аватара я так и не смог понять. А новый, скорее привносит еще одну версию: страна? ))[/offtop]

Сообщение отредактировано: Lapp - 15.01.2010 5:01