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

[Lapp]

плохо поняла назначение функций HexDig, AddRec, FindRec (что-то добавить, найти... )

учи латынь (и/или хотя бы английский))
Hex, hexadecimal - шестнадцатиричный
Dig, digit - цифра
HexDig - шестнадцатиричная цифра (1,2,...,9,A,B,..,F)
Rec, record - запись
AddRec - добавить запись
FindRec - найти запись

Стандартная БД - это ОЧЕНЬ медленно. Впрочем, если для составления базы будут использованы переборные алгоритмы с большой глубиной, то это несущественно. А если живые игроки - тем более.

Вряд ли медленнее, чем чтение/запись мегабайтного файла (дальше мельчить стремно).

Кстати, нет ли возможности реализовать базу в виде дерева?

Так она и есть деревянная! По начальным ходам в блоках. Беда в том, что частые и полезные ходы существенно перемешаны с редкими и бесполезными..

[andriano]

Вряд ли медленнее, чем чтение/запись мегабайтного файла (дальше мельчить стремно).

Давай сравнивать сравнимое.
1 вариант: файл с двоичным представлением наших данных собственной оптимизированной под задачу структуры.
2 вариант: стандартная база (SQL), содержащая тот же набор данных и связей, что и файл 1.
Соображения:
- если объем файла один считать за 1.0, то объем базы SQL будет существенно больше 1.0, причем, возможно, в разы.
- если объем файла один будет "на пределе" помещаться в ОЗУ, то, очевидно, SQL-база уже неизбежно будет, хотя бы частично, размещаться на диске. Откуда и разница во времени доступаю.
- если ни то ни другое в ОЗУ не помещается, то для файла 1 бОльший процент его может содержаться в ОЗУ, а, следовательно, % попаданий без обмена с диском будет выше.
- если мы сумели представить структуру файла 1 в виде дерева, то поиск по нему будет в худшем случае как O(log(N)), а вот насчет SQL-базы это совершенно неочевидно.
- если длина записи строго фиксирована, можно свести поиск к О(1), а для базы - сомнительно.
- если нам НЕ требуется обеспечить устойчивость собственного формата 1 к одновременному проведению транзакций с одним и тем же элементом, сама логика работы базы существенно упроцается по сревнению с любой стандартной реализацией, что само по себе приведет к экономии времени.

Так она и есть деревянная! По начальным ходам в блоках. Беда в том, что частые и полезные ходы существенно перемешаны с редкими и бесполезными..

Сначала отмечу, что при хранении данных на жестком диске, действительно, оптимальной с точки зрения скорости доступа величиной является 1-2 Мбайта.

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

[Lapp]

- если объем файла один считать за 1.0, то объем базы SQL будет существенно больше 1.0, причем, возможно, в разы.

Думаю, это верно, даже если не считать за 1.0 )))

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

Этот случай неинтересен. Калах-5 можно поместить в ОЗУ, если оно не менее 16 ГБ и код скомпилирован под 64 бит. Но калах-5 не заслуживает таких жертв..

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

Этим можно пренебречь. При размере БД около 500 ГБ и памяти под задачу порядка 1 ГБ вероятность попадания - доли процента.

- если мы сумели представить структуру файла 1 в виде дерева, то поиск по нему будет в худшем случае как O(log(N)), а вот насчет SQL-базы это совершенно неочевидно.

Я где-то в глубине души надеюсь, что БД оптимизирована.. Конечно, универсальная оптимизация далека от специальной для задачи, но я повторяю: тут обычный двоичный поиск.

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

Да, фиксирована (если не ужимать). Это должно сыграть.

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

Вот тут не совсем ясно.. Хотя, если сделать "подбазу", которая будет обучаться, скажем, в течении дня/часа, и раз в день/час их синхронизировать - то можно оптимизировать и этот момент.

Сначала отмечу, что при хранении данных на жестком диске, действительно, оптимальной с точки зрения скорости доступа величиной является 1-2 Мбайта.

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

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

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

По моим оценкам продолжительность партии где-то порядка 50 коротких ходов (т.е. однократных раскладываний камней. Полуход состоит из одного или нескольких коротких ходов, делаемых подряд одним игроком), т.е. за всю партию нам потребуется вряд ли более 8 блоков (для каждого из игроков, если они играют друг с другом).

Перепроверь свои оценки. Ты не учитываешь сильнейшего ветвления (которое, совственно, и приводит к тому размеру ДБ, который рассматривался выше). Если бы все было так просто!.. ))

[andriano]

Этим можно пренебречь. При размере БД около 500 ГБ и памяти под задачу порядка 1 ГБ вероятность попадания - доли процента.

А вот это зависит от структуры данных.

Я где-то в глубине души надеюсь, что БД оптимизирована.. Конечно, универсальная оптимизация далека от специальной для задачи, но я повторяю: тут обычный двоичный поиск.

Чудес не бывает. База должна быть оптимизирована под ЛЮБОЙ поиск, а не под поиск по одному конкретному параметру. И попытка создания внутри базы структур, позволяющих оптимально производить поиск по любому из параметров - IMHO слишком дорогое удовольствие.

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

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

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

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

Перепроверь свои оценки. Ты не учитываешь сильнейшего ветвления (которое, совственно, и приводит к тому размеру ДБ, который рассматривался выше). Если бы все было так просто!.. ))

Пока не вижу причин, по которым что-то может быть "не так просто".
1. Камни из калахов не вынимаются НИКОГДА, следовательно, игра, как минимум, слабо монотонна.
2. Минимальное перемещение за один ход - один камень на одну ячейку, что соответствует минимальной сходимости 1 камень в калах за 6 ходов. Т.е. игра в самом худшем случае никак не может превысить 216 ходов (на самом деле, и этих 216 составить не может).
3. Обратно камни ходить не могут.
4. Т.е. все позиции в игре строго упорядочены, из ПОСЛЕДУЮЩЕЙ позиции никогда не сможет получиться ПРЕДЫДУЩАЯ.
Другими словами, твой тезис "Есть ситуация на доске, и она может возникнуть когда угодно." неверен.
Вот именно это четвертое свойство и целесообразно испольховать для построения дерева позиций. Т.е. исходную позицию, в которой в каждой из лунок по 6 камней, считаем корнем дерева, а остальные - ПОСЛЕДУЮЩИЕ по отношению к ней. В этом случае мы можем описать дерево в виде отдельных блоков, каждый из которых описывает определенный диапазон ходов, является потомком вполне определенного "выхода" предыдущего по диапазону ходов блока и имееет кучку "выходов" на последующие блоки.
В этом случае мы имеем, минимум, одно преимущество: в процессе игры нам потребуется перебирать минимальное количество блоков: ссылок на блоки, отстоящие далеко от основной "сюжетной линии" не будут использоваться.

[Гость]

Lapp, можешь, пожалуйста, обьяснить мне роль массива Rate:array[1..r]of integer?
и еще. зачем нам функция HexDig, мы ведь ее нигде не вызываем.

[cameron]

Lapp
Каково назначение у процедуры Teach?
С ее помощью мы чему-то "учим" програму?

[Lapp]

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 - ход с бОльшим значением более вероятен (нежесткий детерминизм, именно так и сделано в этой программе).
Я ответил на вопрос?

Каково назначение у процедуры Teach?
С ее помощью мы чему-то "учим" програму?

ну, не мы, а она сама себя (см. название темы)). А если говорить, что мы это запрограммировали - то да, мы )).
Процедура Teach, если я правильно помню, как раз осуществляет уменьшение/увеличение элементов массива Rate после того, как результат игры определен (см. выше ответ Гостю). То есть она корректирует БД, а если записи с такой ситуацией на доске еще нет в БД, то создает новую запись.

[cameron]

Lapp
благодарю, теперь понятно, учитывая и твой ответ Гостю.
а можешь объяснить функцию SplitBlock? Finish?
вопрос: в функции Compare мы сравниваем состояние игровых полей противников?

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

Сообщение отредактировано: cameron - 11.01.2010 20:28

[Гость]

Я ответил на вопрос?

да, спасибо, очень доходчиво объяснил. У меня еще вопросы.
что за переменная р?
а массивы tBoard (лунки и 2 калаха?), tKalah, Score, Store (массив записей в БД?)?
я так понял, что ход игрока (и перемещение камушков) осуществляется с помощью функции Move, да?

[Гость]

пардон, tBoard ты объяснил.

[Lapp]

что за переменная р?
а массивы tBoard (лунки и 2 калаха?), tKalah, Score, Store (массив записей в БД?)?
я так понял, что ход игрока (и перемещение камушков) осуществляется с помощью функции Move, да?

p - насколько помню, номер текущего игрока (типа 1 или 2).
Move - да, наверное ход. Даже наверняка )).
Score - это англ. счет.. Надо посмотреть, что это тут.
Store, наверное свма БД.


Добавлено через 15 мин.

а можешь объяснить функцию SplitBlock?

БД состоит из блоков (см. пост №27). Блоки создаются пустыми и заполняются в процессе обучения. И сами блоки между собой, и внутри - все упорядочено. Новая запись вставляется в нужный блок на нужное место. Если блок переполняеся, он разделяется (англ. to split) на два.

Finish?

Гм. Псмотрю.

вопрос: в функции Compare мы сравниваем состояние игровых полей противников?

Да. Это как раз нужно для той самой упорядоченности записей внутри блоков и при поиске.

пожалуйста, объясни значение переменной Protocol:array[1..2]of array[1..LProtocol]of tRecord;

Протокол игры (лог, log). В нем записывается, кто как пошел на каком ходу и при каком состоянии доски в текущей игре. Нужно для обучения (см. пост №27).

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

Надеюсь, это помогает твоему образованию.

[Lapp]

Finish?

Гм. Псмотрю.

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

Функция Finish отлавливает окончание игры. После каждого хода состояние на доске проверяется - не закончена ли игра? Это происходит, если:
- либо у кого-то в калахе больше половины;
- либо у кого-то не осталось камней в лунках;
- все камни поровну в двух калахах (ничья).
В этих случаях Finish возвращает TRUE, а в массив Score (англ. счет в игре) по номеру игрока записывается 1 (выигрыш) или -1 (поражение). Так что назначение массива Score тоже объясняется..

[Lapp]

а массивы tBoard (лунки и 2 калаха?), tKalah

Нет.
tBoard - это только лунки (оба игрока). А tKalah - это оба калаха. Это несколько противоречит тому, что я сказал выше (извиняюсь, у меня память тоже не железная). Объясняю, почему.

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

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

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

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

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

[cameron]

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

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

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

[cameron]

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

[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