Системы из спичечных коробков

From: Тармо Пикаро ( tpikaro@turkuamk.fi ) Date: 1999-08-23 23:03

по поводу статьи: http://www.nestor.minsk.by/kg/9703/k1211.htm

Я хотел испытать как выглядит из себя адаптационная система созданная
из спичечных коробков и решил написать программку которая бы
емулировала все эти коробки с бусинками (лень как то было
использовать настоящие спичечные коробки). :)

скачать отсюда: http://www.tekniikka.turkuamk.fi/~tpikaro/ai/aiplayb.exe
10 Kb, незапакованно, beta.
(source довольно кошмарно выглядит - надо - спросите - вышлю)

вот мои коментарии по этому поводу...

я сделал адаптацию к игре "3 пешек".
насколько я понял правила там следующие:
---
* доска 3x3, пешки - 3 белые снизу, 3 черные сверху.
* берется n:ное количество коробков на которых изображены все
возможные позиции игры.
* также на каждом коробке помечаются разными цветами
все возможные ходы на данную позицию и в коробок ложатся по 3 бусинки
всех тех цветов которые есть на коробке. (то есть если возможен ход
вперед, помеченный красным цветом - в коробке вначале лежит 3 бусинки
красного цвета)
* пешки могут ходит как и в шахматах - пойти вперед или съесть
противника по диагонали. (вперед кушать не могут, и "наступать"
на пешки сверху тоже)
* во время игры берется коробок с изображенной позицией,
коробок встряхивается и оттуда достается случайная бусинка и делается
ход соответствующий цвету. (после этого ходит противник, затем
процедура повторяется)
* если AI выигрывает (то есть не противник) то в коробки добавляются
по 3 бусинки того же цвета что был вынут из коробка ;
если же AI проигрывает то у него отнимается по одной бусинке;если
будет ничья то ничего не делается. (правильно ли я понял ?-вынутая
бусинка в расчёт не берется =возвражается в коробок после окончания
партии)
* выигрывает тот кто достигнет первым противоположной линии (тама где
стоят пешки противника) или тото кто съест все пешки противника.
Ничья - когда кто-то из игроков не может сделать хода.
---

это что касается правил...
что же касается программы...
противником я поставил "Mr. Stupid" :) который просто ходит куда
попало без всякого расчета.
AI довольно неплохо адаптируется... но ! он не доходит до
совершенства ! - Stupid все равно умудряется его как-нибудь да и
обыграть. Сейчас объясню почему...

Итак... мысленно возьмем самую начальную позицию и поставим её на
самый верх - это у нас будет вершиной дерева.
(опять я со своим деревом...) :) поставим 3 комбинации продолжения
как ветви этого дерева. и каждой ветке сделаем то же самое до тех пор
пока у нас на всех концах будет конец партии. Теперь...
Мы естественно следуем только по одному пути... (если партия одна)
от самой вершины к какой-нибудь ветке... Если партия оказывается
проигранной - отнимаются бусинки со всех сделанных ходов - примерно
то же что и утоньшать ветки по пройденному пути - меньше возможностей
на то,что мы в следущий раз пойдем по меньшей ветке.
(наверное это слишком ассоциативно...). Но после какого-то момента
появляется ветка через которую прошло 3 проигрыша подряд и
не одного выигрыша. Аха ! Ветка "погибает", что означает то,что
больше бусинок у нас на тот ход нету и туда мы больше в жизни
не попадем. И хотя на той погившей ветке наверняка
были выигрышные и/или ничейные комбинации - но тем не менее мы
абсолютно конкретно разобрались с этой веткой раз и навсегда.
Это и дает шанс Stupidу обыгрывать AI - соседнии ветки (=другие
варианты ходов) могут оказаться 100% проигрышными или
проигрышными при каком-то именном ходе противника.

Как сделать идеальный вариант AI для игры в пешки (и не только)?
следующие идеи посетили меня:
вариант1. в случае проигрыша
- если это последняя бусинка - проверить отмерла ли вся ветка
да - удалить последнюю бусинку, нет - ничего не удалять
- если не последняя - отнять одну бусинку.
вариант2. наказывать удалением одной бусинки с подледнего хода.
- это значительно замедлит скорость адаптации.

Далее я пока не пытался делать улучшенной версии AIPLAY
- надеюсь скоро доделать.

Кстати... мировая вещь эти спичечные коробки - в практические
работы по C++ советую кому-нибудь запихать. :)

Ещё идеи...
Кстати... AI по идее мог бы адаптироваться как-нибудь к симметрии
доски за счет чего адаптация прошла бы раза в 2 быстрее.

Чего не хватает этой системе - full flow control. :)
Сама система должна "задевать саму себя" - то есть...
- система получает информацию.
- она адаптируется, генерируя при этом новую информацию.
Теперь же надо продолжить адаптацию адаптируясь к этой новой
информации.
Опять же... я говорю слишком туманно наверное. :)