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

3 страниц V  1 2 3 >  
 Ответить  Открыть новую тему 
> Игра Калах, самообучающийся алгоритм ИИ
сообщение
Сообщение #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


Профи
****

Группа: Пользователи
Сообщений: 618
Пол: Мужской

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


Знаю эту игру! На нокиа 3310 она была среди стандартных игр (правда под другим кажется именем) На высоких уровнях сложности телефон думал аж секунд ~30, но это его не спасало... переиграть всё равно было просто.
Мартина Гарднера читал... И крестики нолики такие делал... И тоже на Васике smile.gif. Вот только не думаю, что этот способ подходит для данной игры. Хранить базу данных на 10 гб... это имхо.. слишком. Проще обычный перебор с отсеиванием заведомо проигрышных ветвей на ранней стадии.


--------------------
Close the World...txeN eht nepO
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3





Группа: Пользователи
Сообщений: 4
Пол: Мужской
Реальное имя: Дима

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


Хотелось бы посмотреть на комментарии кода проги rolleyes.gif что бы получше её понять, ведь что-то может я не так понял, а что-то и во все не понимаю к чему это!? blink.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


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

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

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


Цитата(Творец @ 12.05.2007 22:05) *

посмотреть на комментарии кода проги

Творец, обязательно сделаю. На вскидку - в ближайшие несколько дней найду для этого время. Заглядывай еще.
Спасибо за интерес! Сам бы я еще долго не занялся бы этим.. smile.gif


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





Группа: Пользователи
Сообщений: 4
Пол: Мужской
Реальное имя: Дима

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


Цитата(Lapp @ 12.05.2007 23:50) *

Творец, обязательно сделаю. На вскидку - в ближайшие несколько дней найду для этого время. Заглядывай еще.
Спасибо за интерес! Сам бы я еще долго не занялся бы этим.. smile.gif

Хорошо smile.gif Буду заглядывать
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6





Группа: Пользователи
Сообщений: 4
Пол: Мужской
Реальное имя: Дима

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


Lapp пока хотя бы примерно что к чему поясни пожалуйста
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


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

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

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


Цитата(Творец @ 20.05.2007 21:37) *

Lapp пока хотя бы примерно что к чему поясни пожалуйста

Я посмотрел прогу smile.gif, и решил, что писать комменты займет слишком много времени.. Ты скажи - тебя интересует общий принцип работы? Это я могу рассказать, плюс назначение процедур. Устроит?


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





Группа: Пользователи
Сообщений: 4
Пол: Мужской
Реальное имя: Дима

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


Цитата(Lapp @ 23.05.2007 11:59) *

Я посмотрел прогу smile.gif, и решил, что писать комменты займет слишком много времени.. Ты скажи - тебя интересует общий принцип работы? Это я могу рассказать, плюс назначение процедур. Устроит?

да, хватит, надеюсь мои все вопросы это решит
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Знаток
****

Группа: Пользователи
Сообщений: 346
Пол: Мужской
Реальное имя: Иван

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


Популярная это всётаки игрушка smile.gif Описали и алгоритм для программы smile.gif
Разложили игру по полочкам
Прикрепленное изображениеПрикрепленное изображение
З.Ы. Просто предполагаю: rolleyes.gif Lapp а не после этой ли статьи появилась идея програмной реализации? smile.gif

Сообщение отредактировано: RathaR -


--------------------
Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик!
Я - системный аналитик!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


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

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

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


Цитата(RathaR @ 11.10.2009 17:34) *
Популярная это всётаки игрушка smile.gif Описали и алгоритм для программы smile.gif
Разложили игру по полочкам
З.Ы. Просто предполагаю: rolleyes.gif Lapp а не после этой ли статьи появилась идея програмной реализации? smile.gif
Да, хорошая заметка)). Нет, я ее не видел (да и подход же совсем другой). В некий момент у нас на работе появились персоналки, Электроника НЦ-80 (копия DEC Pro 350). 8-битный проц, 512К памяти, Бейсик. Встал вопрос, на каком примере ее осваивать, и выбор пал на Калах (по соображениям, о которых я уже говорил не раз). Забавно, что это все происходило как раз примерно в момент выхода статьи. Надо еще сказать, что тогда в эту игру резались все программеры, поскольку существовала ее неплохая реализация (типа для БЭСМ). А еще, она тогда продавалась (не программная, а настольная). И была, кстати, значительно удобнее классического варианта (который описан в этой статье и широко продается сейчас тут, например). Там лунки были каждая отдельно, и не круглые, а камни одинаковые. Первое способствует легкости доставания шариков, а второе с третьим - легкости подсчета. Все это немаловажно, как выясняется в игре.

Такие были времена.. Машина в миллионы (не преувеличиваю) раз слабее, и доступ к ним был сложнее. Но, вот, делали же и такие штуки)).


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


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Женский
Реальное имя: Ольга

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


Lapp, огромное спасибо Вам за написание сей программы!

Цитата(Lapp @ 23.05.2007 7:59) *

Я посмотрел прогу smile.gif, и решил, что писать комменты займет слишком много времени.. Ты скажи - тебя интересует общий принцип работы? Это я могу рассказать, плюс назначение процедур. Устроит?


да, очень интересует общий принцип работы и назначение процедур!
но, если Вас не затруднит написать подробнее, очень прошу! smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


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

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

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


Цитата(cameron @ 10.12.2009 22:02) *
очень интересует общий принцип работы и назначение процедур!
но, если Вас не затруднит написать подробнее, очень прошу!

Хорошо, я попробую. Загляни типа завтра-послезавтра.


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


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

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

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


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

cameron, а можно узнать - тебе это для какой цели? Это курсовая или еще что-то? Просто интересно узнать smile.gif.


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


Знаток
****

Группа: Пользователи
Сообщений: 346
Пол: Мужской
Реальное имя: Иван

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


Lapp, не так давно, я втечении примерно двух недель пытался, исключительно самостоятельно розобраться с этой поистине "адской" rolleyes.gif БД. Но так и не добился успеха, перешел к другому... однако интерес не угас smile.gif Так что я тоже буду безумно рад увидеть хоть какое либо пояснение/коментарии, или доработаную версию игры rolleyes.gif

andriano, я почти ничего не понял, но это действительно хороший пример игры для конкурса, хотя реализация программы для рядового учасника может быть сложноватой... это ж не Крестики-Нолики smile.gif хотя я и не говорю что игра должна быть очень простой


--------------------
Считающий себя единственым здравомыслящим человеком сумасшедший? Если да, возможно я псих...
Пусть умолкнет всякий критик!
Я - системный аналитик!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Женский
Реальное имя: Ольга

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


Lapp, все верно, для курсовой работы! ну и самой хочется ее понять, эту программу. smile.gif
Цитата
Это Калах-4 (легко превращающийся в Калах-5,6 и т.д. заменой одной констант)


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


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

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

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


Цитата(cameron @ 15.12.2009 17:54) *
Lapp, все верно, для курсовой работы! ну и самой хочется ее понять, эту программу. smile.gif
Вторая часть фразы мне нравится больше, но и первая нормально, если серьезный подход smile.gif.

Цитата
в графическом режиме при Калах-6 одна лунка выезжает на другую..
Что ты имеешь в виду под графическим режимом? Этот режим называется у меня в программе "картинка", а графики тут и в помине нет..

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

При запуске выдается "меню". Можно нажимать буковки..

p - play - играть. Если есть база и ход найден в ней - то программа играет "разумно"; нет - случайно.
t - train - тренироваться. Программа играет со случайным процессом, при этом накапливается БД.
r - read - читать БД (если она есть на диске).
w - write - записать накопленную БД. Осторожно: БД затирается без предупреждения.
q - quit - выйти из игры.

В процессе игры теперь не нужно жать энтер - ход делается по сразу по нажатии клавиши. Можно выйти по нажатии Q.

Теперь про обучение.. Для него достаточно в главном меню нажать T. Если хочется посмотреть, как продвигается процесс, нажми N - она будет выводить количество сыгранных партий. Чтобы убрать это - снова N (эта опция не отмесена в меню).

Советую сначала поиграть в рангом 3. Этот случай обучается очень быстро. Запиши накопленную базу и потом считывай.

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

При ранге 5 обучение занимает порядка суток и не заканчивается, поскольку вылетает по памяти (примерно после 3 миллионов сыгранных игр). Размер БД на диске - под 1 ГБ. Полагаю, полный размер потребует нескольких ГБ (может, 4-6), а обучение будет продолжаться не меньше недели.

Ранг 6 я толком не пробовал. Думаю, что размер БД будет где-то сотни ГБ, что вполне разумно. Если вычистить код и ввести многопроцессность, то время накопления такой БД тоже будет, хотя и большим, но еще не безумным (месяцы).

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

Уфф... Разберешься? (Показать/Скрыть)

Любители попридираться могут feel free мордовать меня. Только я вряд ли смогу ответить на большинство вопросов )).


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


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Женский
Реальное имя: Ольга

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


Lapp, спасибо, что ответил скоро!
сейчас буду разбираться в программе! пока, понятно, воопросов нет. Одни только благодарности smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #18


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

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

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


Цитата(cameron @ 21.12.2009 21:13) *
Lapp, спасибо, что ответил скоро!
сейчас буду разбираться в программе! пока, понятно, воопросов нет. Одни только благодарности smile.gif
Да какие там благодарности, я же так и не сделал пояснений к процедурам.. В принципе, там названия говорящие, но в основном я надеюсь, что ты будешь спрашивать поконкретнее - я отвечу.

Еще про ранг 6 (и частично 5).. То, что я написал выше, требует дополнения.
БД уже достигает таких размеров, что она не может поместиться в оперативную память и, ссответственно, не должна записываться одним файлом. Раз так, нужно для каждого хода считывать соответствующий кусок с диска. И значит, эти куски должны быть достаточно маленькими, чтоб чтение происходило быстро (не больше 1 МБ). Далее, при обучении надо устроить так, чтобы добавление записи в один файл не влекло за собой переписывания остатка БД (то есть формат должен быть достаточно свободным). И все равно обучение замедлится dramatically, в сотни раз, думаю [вставлено позже: и тогда месяцы превратятся в десятки лет. Наверное, это однозначно указывает на необходимость использования БД, а не просто файлов]. Проблема в том, что существено невозможно придумать организацию БД, где более употребительные ходы хранились бы "ближе", а менее - "подальше". Большинство из этих проблем решаются, если использовать реальную БД (типа MySQL), но мне не хотелось бы - можно обойтись и без нее. Короче гря, ЭТА реализация совершенно не годится для ранга 6 (да и для ранга 5 тоже уже не совсем).

Я лелею надежду все переписать совсем, полностью переделав БД. Я еще не вполне определился со средствами.. Сама по себе игра будет иметь web-интерфейс (скорее всего без излишеств на JS). Идея простая: выкладывается необученная прога, обучение проходит а)при игре пользователей; б)случайным фоновым процессом. И вот там выбор будет такой:

1. писать проги для доступа к файлам на Паскале или Си, вызываемые из PHP (либо прямо cgi);
2. писать доступ к файлам непосредственно на PHP;
3. использовать стандартную БД.

Пока не могу выбрать. Приглашаю всех к дискуссии на эту тему. Также, если кто поможет (Cameron?)).. smile.gif


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


Новичок
*

Группа: Пользователи
Сообщений: 11
Пол: Женский
Реальное имя: Ольга

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


плохо поняла назначение функций HexDig, AddRec, FindRec (что-то добавить, найти... )
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #20


Гуру
*****

Группа: Пользователи
Сообщений: 1 168
Пол: Мужской
Реальное имя: Сергей Андрианов

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


Цитата(Lapp @ 22.12.2009 6:00) *
Большинство из этих проблем решаются, если использовать реальную БД (типа MySQL), но мне не хотелось бы - можно обойтись и без нее.
...
Пока не могу выбрать. Приглашаю всех к дискуссии на эту тему. Также, если кто поможет (Cameron?)).. smile.gif
Стандартная БД - это ОЧЕНЬ медленно. Впрочем, если для составления базы будут использованы переборные алгоритмы с большой глубиной, то это несущественно. А если живые игроки - тем более.
Кстати, нет ли возможности реализовать базу в виде дерева?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

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

 





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