IPB
ЛогинПароль:

> Игра Калах, самообучающийся алгоритм ИИ
сообщение
Сообщение #1


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Гость @ 10.01.2010 13:02) *
Lapp, можешь, пожалуйста, обьяснить мне роль массива Rate:array[1..r]of integer?
и еще. зачем нам функция HexDig, мы ведь ее нигде не вызываем.
Rate (с англ.: оценка, вспомни рейтинг) - это как раз главная вещь в программе. Придется вкратце повторить суть метода..

В игре перед игроком есть доска (r его лунок, r лунок противника и два калаха). Разные ходы - разная ситуация на доске. В разных играх, конечно, ситуация может повторяться. В каждой ситуации у игрока на выбор несколько возможных ходов (1-й лункой, 2-й и т.д., если они не пустые). В процессе обучения происходит случайный выбор хода, один из возможных, и сделанный ход запоминается в лог игры (как сам ход, так и полная ситуация на доске: сколько шариков в каждой лунке и в калахах, запись Brd:tBoard). После того, как игра окончена и результат определен (выигрыш или проигрыш) мы с помощью записанного лога изменяем массив Rate в записи Block.
    Block:array[1..LBlock]of record
Brd:tBoard; {ситуация на доске}
Rate:array[1..r]of integer; {рейтинг ходов}
end;

Если выигрыш, то Rate[i] (i - это сделанный ход) увеличиваем на 1, если проигрыш - уменьшаем на 1. То есть повышаем или понижаем рейтинг сделанного хода в этой ситуации. Тем самым, Rate[хода], который привел к выигрышу увеличивается, а того, который к проигрышу - уменьшается.
Это был процесс обучения. Теперь рассмотрим, что происходит в игре.
Когда игроку AI (artificial intelligence, искусственный интеллект) нужно сделать выбор хода в конкретной ситуации, программа просматривает базу данных, упорядоченную по ситуациям на доске. Если текущая ситуация присутствует в базе, то берется соответстующий ей массив Rate (из структуры Block). Далее делается ход, исходя из содержимого Rate. Тут есть два варианта:
- можно просто тупо брать тот ход, для которого элемент массива Rate максимален (жесткий детерминизм);
- можно ход снова выбирать соучайно, но с весами, взятыми из Rate - ход с бОльшим значением более вероятен (нежесткий детерминизм, именно так и сделано в этой программе).
Я ответил на вопрос?

Цитата(cameron @ 10.01.2010 18:47) *
Каково назначение у процедуры Teach?
С ее помощью мы чему-то "учим" програму?
smile.gif ну, не мы, а она сама себя (см. название темы)). А если говорить, что мы это запрограммировали - то да, мы )).
Процедура Teach, если я правильно помню, как раз осуществляет уменьшение/увеличение элементов массива Rate после того, как результат игры определен (см. выше ответ Гостю). То есть она корректирует БД, а если записи с такой ситуацией на доске еще нет в БД, то создает новую запись.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

Сообщений в этой теме
lapp   Игра Калах   6.12.2006 19:27
Archon   Знаю эту игру! На нокиа 3310 она была среди ст…   11.12.2006 2:54
Творец   Хотелось бы посмотреть на комментарии кода проги …   13.05.2007 1:05
Lapp   посмотреть на комментарии кода проги Творец, обя…   13.05.2007 2:50
Творец   Творец, обязательно сделаю. На вскидку - в ближа…   13.05.2007 22:25
Творец   Lapp пока хотя бы примерно что к чему поясни пожал…   21.05.2007 0:37
Lapp   Lapp пока хотя бы примерно что к чему поясни пожа…   23.05.2007 14:59
Творец   Я посмотрел прогу :), и решил, что писать коммент…   28.05.2007 0:06
RathaR   Популярная это всётаки игрушка :) Описали и алгори…   11.10.2009 20:34
Lapp   Популярная это всётаки игрушка :) Описали и алгори…   12.10.2009 10:56
cameron   Lapp, огромное спасибо Вам за написание сей програ…   11.12.2009 2:02
Lapp   очень интересует общий принцип работы и назначение…   11.12.2009 15:07
Lapp   Выполняя обещание, я пересмотрел программу, и.. н…   14.12.2009 10:35
RathaR   Lapp, не так давно, я втечении примерно двух недел…   14.12.2009 23:52
cameron   Lapp, все верно, для курсовой работы! ну и сам…   15.12.2009 21:54
Lapp   Lapp, все верно, для курсовой работы! ну и сам…   21.12.2009 16:47
cameron   Lapp, спасибо, что ответил скоро! сейчас буду …   22.12.2009 1:13
Lapp   [b]Lapp, спасибо, что ответил скоро! сейчас бу…   22.12.2009 10:00
andriano   Большинство из этих проблем решаются, если использ…   23.12.2009 2:22
Lapp   плохо поняла назначение функций HexDig, AddRec, Fi…   23.12.2009 10:11
andriano   Вряд ли медленнее, чем чтение/запись мегабайтного …   23.12.2009 15:30
Lapp   - если объем файла один считать за 1.0, то объем б…   23.12.2009 17:01
andriano   Этим можно пренебречь. При размере БД около 500 Г…   23.12.2009 17:42
cameron   плохо поняла назначение функций HexDig, AddRec, Fi…   23.12.2009 0:30
Гость   Lapp, можешь, пожалуйста, обьяснить мне роль масси…   10.01.2010 17:02
cameron   Lapp Каково назначение у процедуры Teach? С ее пом…   10.01.2010 22:47
Lapp   Lapp, можешь, пожалуйста, обьяснить мне роль масси…   11.01.2010 4:49
cameron   Lapp благодарю, теперь понятно, учитывая и твой от…   11.01.2010 23:36
Гость   да, спасибо, очень доходчиво объяснил. У меня еще…   12.01.2010 1:56
Lapp   что за переменная р? а массивы tBoard (лунки и 2 …   12.01.2010 3:33
Lapp   Гм. Псмотрю.Посмотрел.. Что ж ни у кого язык не…   12.01.2010 4:51
Lapp   а массивы tBoard (лунки и 2 калаха?), tKalahНет. …   12.01.2010 13:37
Гость   пардон, tBoard ты объяснил.   12.01.2010 2:02
cameron   честно говоря, не знала что на форуме можно писат…   12.01.2010 23:19
cameron   переменная Num: boolean? ll: longint? о каких лин…   12.01.2010 23:56
Lapp   не знала что на форуме можно писать пост без входа…   13.01.2010 10:43
cameron   преподаватель еще не видел программы, вопросы мои…   13.01.2010 18:23
Lapp   преподаватель еще не видел программы, вопросы мои.…   13.01.2010 18:41
cameron   на счет записей в БД. Store[NStore]^.Len:=0 - тут…   13.01.2010 19:29
Lapp   Store^.Len:=0 - тут мы создаем пустой блокДа, имен…   14.01.2010 10:08
Lapp   Как хороши, как свежи были розы.. (С)   3.02.2010 5:50


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 21:28
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name