Помощь - Поиск - Пользователи - Календарь
Полная версия: Игра Калах
Форум «Всё о Паскале» > Pascal, Object Pascal > Написание игр
Lapp
Всем привет,
сыграем в Калах? 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
Archon
Знаю эту игру! На нокиа 3310 она была среди стандартных игр (правда под другим кажется именем) На высоких уровнях сложности телефон думал аж секунд ~30, но это его не спасало... переиграть всё равно было просто.
Мартина Гарднера читал... И крестики нолики такие делал... И тоже на Васике smile.gif. Вот только не думаю, что этот способ подходит для данной игры. Хранить базу данных на 10 гб... это имхо.. слишком. Проще обычный перебор с отсеиванием заведомо проигрышных ветвей на ранней стадии.
Творец
Хотелось бы посмотреть на комментарии кода проги rolleyes.gif что бы получше её понять, ведь что-то может я не так понял, а что-то и во все не понимаю к чему это!? blink.gif
Lapp
Цитата(Творец @ 12.05.2007 22:05) *

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

Творец, обязательно сделаю. На вскидку - в ближайшие несколько дней найду для этого время. Заглядывай еще.
Спасибо за интерес! Сам бы я еще долго не занялся бы этим.. smile.gif
Творец
Цитата(Lapp @ 12.05.2007 23:50) *

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

Хорошо smile.gif Буду заглядывать
Творец
Lapp пока хотя бы примерно что к чему поясни пожалуйста
Lapp
Цитата(Творец @ 20.05.2007 21:37) *

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

Я посмотрел прогу smile.gif, и решил, что писать комменты займет слишком много времени.. Ты скажи - тебя интересует общий принцип работы? Это я могу рассказать, плюс назначение процедур. Устроит?
Творец
Цитата(Lapp @ 23.05.2007 11:59) *

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

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

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

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

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


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

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

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

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


в графическом режиме при Калах-6 одна лунка выезжает на другую..
Lapp
Цитата(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 мордовать меня. Только я вряд ли смогу ответить на большинство вопросов )).
cameron
Lapp, спасибо, что ответил скоро!
сейчас буду разбираться в программе! пока, понятно, воопросов нет. Одни только благодарности smile.gif
Lapp
Цитата(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
cameron
плохо поняла назначение функций HexDig, AddRec, FindRec (что-то добавить, найти... )
andriano
Цитата(Lapp @ 22.12.2009 6:00) *
Большинство из этих проблем решаются, если использовать реальную БД (типа MySQL), но мне не хотелось бы - можно обойтись и без нее.
...
Пока не могу выбрать. Приглашаю всех к дискуссии на эту тему. Также, если кто поможет (Cameron?)).. smile.gif
Стандартная БД - это ОЧЕНЬ медленно. Впрочем, если для составления базы будут использованы переборные алгоритмы с большой глубиной, то это несущественно. А если живые игроки - тем более.
Кстати, нет ли возможности реализовать базу в виде дерева?
Lapp
Цитата(cameron @ 22.12.2009 20:30) *
плохо поняла назначение функций HexDig, AddRec, FindRec (что-то добавить, найти... )
smile.gif учи латынь (и/или хотя бы английский))
Hex, hexadecimal - шестнадцатиричный
Dig, digit - цифра
HexDig - шестнадцатиричная цифра (1,2,...,9,A,B,..,F)
Rec, record - запись
AddRec - добавить запись
FindRec - найти запись

Цитата(andriano @ 22.12.2009 22:22) *
Стандартная БД - это ОЧЕНЬ медленно. Впрочем, если для составления базы будут использованы переборные алгоритмы с большой глубиной, то это несущественно. А если живые игроки - тем более.
Вряд ли медленнее, чем чтение/запись мегабайтного файла (дальше мельчить стремно).

Цитата
Кстати, нет ли возможности реализовать базу в виде дерева?
Так она и есть деревянная! smile.gif По начальным ходам в блоках. Беда в том, что частые и полезные ходы существенно перемешаны с редкими и бесполезными..
andriano
Цитата(Lapp @ 23.12.2009 6:11) *
Вряд ли медленнее, чем чтение/запись мегабайтного файла (дальше мельчить стремно).
Давай сравнивать сравнимое.
1 вариант: файл с двоичным представлением наших данных собственной оптимизированной под задачу структуры.
2 вариант: стандартная база (SQL), содержащая тот же набор данных и связей, что и файл 1.
Соображения:
- если объем файла один считать за 1.0, то объем базы SQL будет существенно больше 1.0, причем, возможно, в разы.
- если объем файла один будет "на пределе" помещаться в ОЗУ, то, очевидно, SQL-база уже неизбежно будет, хотя бы частично, размещаться на диске. Откуда и разница во времени доступаю.
- если ни то ни другое в ОЗУ не помещается, то для файла 1 бОльший процент его может содержаться в ОЗУ, а, следовательно, % попаданий без обмена с диском будет выше.
- если мы сумели представить структуру файла 1 в виде дерева, то поиск по нему будет в худшем случае как O(log(N)), а вот насчет SQL-базы это совершенно неочевидно.
- если длина записи строго фиксирована, можно свести поиск к О(1), а для базы - сомнительно.
- если нам НЕ требуется обеспечить устойчивость собственного формата 1 к одновременному проведению транзакций с одним и тем же элементом, сама логика работы базы существенно упроцается по сревнению с любой стандартной реализацией, что само по себе приведет к экономии времени.
Цитата
Так она и есть деревянная! smile.gif По начальным ходам в блоках. Беда в том, что частые и полезные ходы существенно перемешаны с редкими и бесполезными..
Сначала отмечу, что при хранении данных на жестком диске, действительно, оптимальной с точки зрения скорости доступа величиной является 1-2 Мбайта.

Коль скоро у нас все равно древовидная структура, не целесообразно было бы предусмотреть точно такую же организацию блоков. Например, первый блок хранит полную информацию обо всех партиях, скажем, на глубину 5-6 полуходов и ссылается на блоки следующего уровня (скажем, полуходы с 7 по 13), а те, в свою очередь, на блоки полуходов следующего уровня.
По моим оценкам продолжительность партии где-то порядка 50 коротких ходов (т.е. однократных раскладываний камней. Полуход состоит из одного или нескольких коротких ходов, делаемых подряд одним игроком), т.е. за всю партию нам потребуется вряд ли более 8 блоков (для каждого из игроков, если они играют друг с другом).
Lapp
Цитата(andriano @ 23.12.2009 11:30) *
- если объем файла один считать за 1.0, то объем базы SQL будет существенно больше 1.0, причем, возможно, в разы.
Думаю, это верно, даже если не считать за 1.0 smile.gif)))

Цитата
- если объем файла один будет "на пределе" помещаться в ОЗУ, то, очевидно, SQL-база уже неизбежно будет, хотя бы частично, размещаться на диске. Откуда и разница во времени доступаю.
Этот случай неинтересен. Калах-5 можно поместить в ОЗУ, если оно не менее 16 ГБ и код скомпилирован под 64 бит. Но калах-5 не заслуживает таких жертв..

Цитата
- если ни то ни другое в ОЗУ не помещается, то для файла 1 бОльший процент его может содержаться в ОЗУ, а, следовательно, % попаданий без обмена с диском будет выше.
Этим можно пренебречь. При размере БД около 500 ГБ и памяти под задачу порядка 1 ГБ вероятность попадания - доли процента.

Цитата
- если мы сумели представить структуру файла 1 в виде дерева, то поиск по нему будет в худшем случае как O(log(N)), а вот насчет SQL-базы это совершенно неочевидно.
Я где-то в глубине души надеюсь, что БД оптимизирована.. Конечно, универсальная оптимизация далека от специальной для задачи, но я повторяю: тут обычный двоичный поиск.

Цитата
- если длина записи строго фиксирована, можно свести поиск к О(1), а для базы - сомнительно.
Да, фиксирована (если не ужимать). Это должно сыграть.

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

Цитата
Сначала отмечу, что при хранении данных на жестком диске, действительно, оптимальной с точки зрения скорости доступа величиной является 1-2 Мбайта.
Я не вполне согласен.. К сожалению, дисковый кэш тут бесполезен, скорее даже вреден. Думаю, что дробление вплоть до размера блока на диске должно ускорять процесс (хотя и несильно в конце).

Цитата
Коль скоро у нас все равно древовидная структура, не целесообразно было бы предусмотреть точно такую же организацию блоков. Например, первый блок хранит полную информацию обо всех партиях, скажем, на глубину 5-6 полуходов и ссылается на блоки следующего уровня (скажем, полуходы с 7 по 13), а те, в свою очередь, на блоки полуходов следующего уровня.
Сергей, ты что-то путаешь. В рассматриваемом методе нет понятия ни ходов, ни полуходов, ни глубины. Есть ситуация на доске, и она может возникнуть когда угодно. Все остальное (если оно возможно) следует рассматривать как усовершенствование метода и подробно анализировать не впопыхах.

Цитата
По моим оценкам продолжительность партии где-то порядка 50 коротких ходов (т.е. однократных раскладываний камней. Полуход состоит из одного или нескольких коротких ходов, делаемых подряд одним игроком), т.е. за всю партию нам потребуется вряд ли более 8 блоков (для каждого из игроков, если они играют друг с другом).
Перепроверь свои оценки. Ты не учитываешь сильнейшего ветвления (которое, совственно, и приводит к тому размеру ДБ, который рассматривался выше). Если бы все было так просто!.. smile.gif))
andriano
Цитата(Lapp @ 23.12.2009 13:01) *
Этим можно пренебречь. При размере БД около 500 ГБ и памяти под задачу порядка 1 ГБ вероятность попадания - доли процента.
А вот это зависит от структуры данных.
Цитата
Я где-то в глубине души надеюсь, что БД оптимизирована.. Конечно, универсальная оптимизация далека от специальной для задачи, но я повторяю: тут обычный двоичный поиск.
Чудес не бывает. База должна быть оптимизирована под ЛЮБОЙ поиск, а не под поиск по одному конкретному параметру. И попытка создания внутри базы структур, позволяющих оптимально производить поиск по любому из параметров - IMHO слишком дорогое удовольствие.
Цитата

Я не вполне согласен.. К сожалению, дисковый кэш тут бесполезен, скорее даже вреден. Думаю, что дробление вплоть до размера блока на диске должно ускорять процесс (хотя и несильно в конце).
Я исхожу из соображений равнопрочности: данные должны быть такого объема, чтобы время их пересылки примерно равнялось времени позиционирования головки. При уменьшении объема данных мы практически не получаем выигрыша во времени, при увеличении - получаемый проигрыш во времени не компенсируется пропорциональным увеличением вероятности, что данные будут нужны.
Итого: желательно, чтобы время передачи данных составляло 15-20 мс, что при темпе передачи 60-100 Мбайт/с и составляет эти самые 1-2 Мбайта.
Цитата

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

Перепроверь свои оценки. Ты не учитываешь сильнейшего ветвления (которое, совственно, и приводит к тому размеру ДБ, который рассматривался выше). Если бы все было так просто!.. smile.gif))
Пока не вижу причин, по которым что-то может быть "не так просто".
1. Камни из калахов не вынимаются НИКОГДА, следовательно, игра, как минимум, слабо монотонна.
2. Минимальное перемещение за один ход - один камень на одну ячейку, что соответствует минимальной сходимости 1 камень в калах за 6 ходов. Т.е. игра в самом худшем случае никак не может превысить 216 ходов (на самом деле, и этих 216 составить не может).
3. Обратно камни ходить не могут.
4. Т.е. все позиции в игре строго упорядочены, из ПОСЛЕДУЮЩЕЙ позиции никогда не сможет получиться ПРЕДЫДУЩАЯ.
Другими словами, твой тезис "Есть ситуация на доске, и она может возникнуть когда угодно." неверен.
Вот именно это четвертое свойство и целесообразно испольховать для построения дерева позиций. Т.е. исходную позицию, в которой в каждой из лунок по 6 камней, считаем корнем дерева, а остальные - ПОСЛЕДУЮЩИЕ по отношению к ней. В этом случае мы можем описать дерево в виде отдельных блоков, каждый из которых описывает определенный диапазон ходов, является потомком вполне определенного "выхода" предыдущего по диапазону ходов блока и имееет кучку "выходов" на последующие блоки.
В этом случае мы имеем, минимум, одно преимущество: в процессе игры нам потребуется перебирать минимальное количество блоков: ссылок на блоки, отстоящие далеко от основной "сюжетной линии" не будут использоваться.
Гость
Lapp, можешь, пожалуйста, обьяснить мне роль массива Rate:array[1..r]of integer?
и еще. зачем нам функция HexDig, мы ведь ее нигде не вызываем.
cameron
Lapp
Каково назначение у процедуры Teach?
С ее помощью мы чему-то "учим" програму?
Lapp
Цитата(Гость @ 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 после того, как результат игры определен (см. выше ответ Гостю). То есть она корректирует БД, а если записи с такой ситуацией на доске еще нет в БД, то создает новую запись.
cameron
Lapp
благодарю, теперь понятно, учитывая и твой ответ Гостю. smile.gif
а можешь объяснить функцию SplitBlock? Finish?
вопрос: в функции Compare мы сравниваем состояние игровых полей противников?

пожалуйста, объясни значение переменной Protocol:array[1..2]of array[1..LProtocol]of tRecord; спасибо, надеюсь, я не затруднила бесконечными вопросами.
Гость
Цитата
Я ответил на вопрос?

да, спасибо, очень доходчиво объяснил. У меня еще вопросы.
что за переменная р?
а массивы tBoard (лунки и 2 калаха?), tKalah, Score, Store (массив записей в БД?)?
я так понял, что ход игрока (и перемещение камушков) осуществляется с помощью функции Move, да?
Гость
пардон, tBoard ты объяснил.
Lapp
Цитата(Гость @ 11.01.2010 21:56) *
что за переменная р?
а массивы tBoard (лунки и 2 калаха?), tKalah, Score, Store (массив записей в БД?)?
я так понял, что ход игрока (и перемещение камушков) осуществляется с помощью функции Move, да?
p - насколько помню, номер текущего игрока (типа 1 или 2).
Move - да, наверное ход. Даже наверняка )).
Score - это англ. счет.. Надо посмотреть, что это тут.
Store, наверное свма БД.


Добавлено через 15 мин.
Цитата(cameron @ 11.01.2010 19:36) *
а можешь объяснить функцию SplitBlock?
БД состоит из блоков (см. пост №27). Блоки создаются пустыми и заполняются в процессе обучения. И сами блоки между собой, и внутри - все упорядочено. Новая запись вставляется в нужный блок на нужное место. Если блок переполняеся, он разделяется (англ. to split) на два.

Цитата
Finish?
Гм. Псмотрю.

Цитата
вопрос: в функции Compare мы сравниваем состояние игровых полей противников?
Да. Это как раз нужно для той самой упорядоченности записей внутри блоков и при поиске.

Цитата
пожалуйста, объясни значение переменной Protocol:array[1..2]of array[1..LProtocol]of tRecord;
Протокол игры (лог, log). В нем записывается, кто как пошел на каком ходу и при каком состоянии доски в текущей игре. Нужно для обучения (см. пост №27).

Цитата
надеюсь, я не затруднила бесконечными вопросами.
Надеюсь, это помогает твоему образованию.
Lapp
Цитата(Lapp @ 11.01.2010 23:33) *
Цитата
Finish?

Гм. Псмотрю.
Посмотрел.. Что ж ни у кого язык не повернулся сказать, что русские комменты в программе нечитабельны? Я только сейчас заметил.. Исправлено.

Функция Finish отлавливает окончание игры. После каждого хода состояние на доске проверяется - не закончена ли игра? Это происходит, если:
- либо у кого-то в калахе больше половины;
- либо у кого-то не осталось камней в лунках;
- все камни поровну в двух калахах (ничья).
В этих случаях Finish возвращает TRUE, а в массив Score (англ. счет в игре) по номеру игрока записывается 1 (выигрыш) или -1 (поражение). Так что назначение массива Score тоже объясняется..
Lapp
Цитата(Гость @ 11.01.2010 21:56) *
а массивы tBoard (лунки и 2 калаха?), tKalah
Нет.
tBoard - это только лунки (оба игрока). А tKalah - это оба калаха. Это несколько противоречит тому, что я сказал выше (извиняюсь, у меня память тоже не железная). Объясняю, почему.

Если быть точным, то полная ситуация характеризуется количеством камней во всех лунках плюс в калахах. Что-то одно можно вычесть (одну лунку или один калах), поскольку если мы имеем количество камней в остальных, эту одну мы можем вычислить (r2- сумма по остальным). Это могло бы сэкономить место в БД. Но я этим не воспользовался. Я пошел несколько дальше. Хотя, если быть точным, мои эти самые дальнейшие действия можно оспорить. Объясняю, почему.

Я принял допущение, что ход не зависит от количества камней в калахе. Это не совсем верно, и это особенно легко видеть на завершающей стадии. Допустим, у вас в калахе всего одного камня не хватает до выигрыша. Тогда выигрышным будет ход, который приносит хотя бы один камень в калах. Но наша БД ничего об этом не знает, поэтому она все равно будет "стараться" положить в калах как можно больше камней (грубо говоря). Это довольно тонкий момент, и я не стану с пеной у рта доказывать, что я прав. Но, что выросло - то выросло, и сейчас в БД хранится ситуация только в виде количества камней в лунках. И именно по этой причине полная ситуация разделена на два массива: калахи и лунки, типа tKalah и tBoard. Переменные типа tKalah (а именно, Kalah) участвует в игре (ессно), но не участвует в обучении и не записывается в БД.

Если вам покажется, что экономия-то копеечная - подумаешь, два байта (или даже один).. На самом деле не совсем так. Дополнительное поле повлечет за собой дополнительные записи в БД (записи с одинаковыми Board и разными Kalah будут разными в БД). Если вам все же захочется сказать, что все же лучше было точно следовать принципу алгоритма, я отвечу вот, что. Когда я сам играл в Калах (руками и головой) я практически очень мало обращал внимания на то, сколько у меня камней в калахе (разве, чтоб порадоваться или огорчиться). И чем тогда программа лучше меня? rolleyes.gif

Добавлено через 8 мин.
cameron, посредством привлечения Гостей ты пытаешься создать видимость массового интереса к вопросу? Типа толпы народа хотят самообучать программы игре в калах? smile.gif

Я тебя прошу, если ты не входишь, то по крайней мере напиши свой ник в поле "имя". Но лучше входи..
cameron
Цитата
Добавлено через 8 мин.
cameron, посредством привлечения Гостей ты пытаешься создать видимость массового интереса к вопросу? Типа толпы народа хотят самообучать программы игре в калах?

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

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

cameron
переменная Num: boolean?
ll: longint? о каких линиях идет речь: 'Lines: ', ll?
Lapp
Цитата(cameron @ 12.01.2010 19:19) *
не знала что на форуме можно писать пост без входа в систему. ...
я подумала, что достану тебя, если буду задавать слишком много вопросов, а их у меня много.
Можно отвечать, нельзя начинать тему. У пользователей все же есть довольно много преимуществ. Например, можно повышать репутацию другим (после 25 постов) smile.gif.
Вполне возможно, что достанешь smile.gif. Совет: если ты покажешь, что хоть немного вникла в суть, а не просто транслируешь мне вопросы преподавателя - в этом случае вероятность "доставания" будет меньше )). Поменьше условностей, побольше реальной заинтересованности )).

Цитата(cameron @ 12.01.2010 19:56) *
переменная Num: boolean?
ll: longint? о каких линиях идет речь: 'Lines: ', ll?

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

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

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

преподаватель еще не видел программы, вопросы мои.
по-моему, очень много усилий пошло на Picture, хотя режим без "картинки" тоже хорош. Но ты не пошел по пути наименьшего сопротивления smile.gif)
Lapp
Цитата(cameron @ 13.01.2010 14:23) *
преподаватель еще не видел программы, вопросы мои.
по-моему, очень много усилий пошло на Picture, хотя режим без "картинки" тоже хорош. Но ты не пошел по пути наименьшего сопротивления smile.gif)
Ужжасно приятно smile.gif.
Картинка - ерунда, там много мозгов не требуется, делается за пару часов )). Надо бы переделать, сделать не в тексте.
Ты хорошо разобралась с БД? Вот там мозги нужны в полной мере.
cameron
на счет записей в БД.
Store[NStore]^.Len:=0 - тут мы создаем пустой блок и используем селектор записи, Len - имя поля. записи внутри блоков упорядочены по имени поля. Так?
Lapp
Цитата(cameron @ 13.01.2010 15:29) *
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, вот тут кто-то из нас что-то совсем не понял, и я сильно подозреваю, что это был не я sad.gif. Как можно вообще записи упорядочивать по имени поля? Какой в этом смысл? Имя поля дается при написании кода и смысл его только в том, чтоб оно напоминало о том, что внутри.

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

Допустим, что у нас калах ранга 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
Как хороши, как свежи были розы.. (С)
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.