Теория самообучающейся программы, на примере монополии Опции

[RathaR]

Вот, меня весьма заинтересовала идея Lappa , о написании кокой нибуть вариации монополии, с самообучающимся ИИ. Погуглил я на эту тему, но единственное что нашёл, это описание принципа роботы с крестиками-ноликами и много бредней про то что машины зохавают мир
Поэтому и решил создать тему здесь, об самообучении ИИ в общем, и об монополии в частности.
Так вот, как я это представляю:
допустим в игре участтвуэт самообучающийся ИИ, и человек/жёстко заданый ИИ.
Весь процес самообучения происходит следующим образом (поправте или скоординируйте меня если неправ):
Человек/жёстко заданый ИИ делает ход, попадая на определённый участок(правила монополии я думаю всем известны ему нужно определить что делать дальше - либо купить его либо пустить на аукцион. Этот выбор он делает исходя их жёстких формул, определяя степень "необходимости" для него этого участка, он учитывает его стоимость, наличие у него участков такогоже цвета, арендную плату, суму денег в наличии а также степень нужности этого участка для противника, а если противнику он некчему, то может сдать этот участок на аукцион(!) чтобы попробывать купить его подешевле. В это время самообучающийся ИИ следит за действиями человека/жёстко заданого ИИ, и у себя в памяти записывает ситуацию и решение опонента(допустим у него в памяти есть ячейка для каждого участка, и в соответствующую ячейку он записывает: суму денег которая была у опонента, кол-во участков, как других так и такогоже цвета, рентабельность участка, и т.д, ну и наконец решение которое принял его опонент) дальше если в игре самообучающийся ИИ попадёт на етот участок, он сравнит ту ситуацию что сейчас у него (суму денег друг участки, рентабельность), и те ситуации что были у его противника, что у него записаны, и выберет то решение которое противник принял в наиболее похожей ситуации (тоесть под ситуацией я подразумеваю економ состояние игрока).
Вот так и будет продолжаться игра, кроме того, самообучающийся ИИ будет записывать каждый раз когда его опонент заложит какой либо участок, или возьмёт зсуду в банке, и в случае возникновения похожей ситуации, будет поступать также, брать похожую зсуду, закладывать примерно равноценный участок.
Ставить дома и отели на своих участках он тоже будет только после того как "научиться " этого у опонента.

Хух, теперь о следуюющем
После всего этого у меня возник ряд вопросов:
1) Всётаки монополия - это не крестики нолики, и каждая игра займёт время, такчто обучаться он будет медленно, в связи с этим появляеться необходимость сделать "автоматический режим " в игре, когда она будет играть сама з собой опр кол-во партий, чтобы достигнуть того или иного уровня знаний?
2) А вообще реально ли это зделать?, я имею в виду, не будет ли это всё занимать огромные обьёмы памяти, и не будет ли ИИ думать по 10 мин? ( прошу дать хоть приблизительную оценку, по даному алгоритму, потомучто мне самому очень тяжело об этом судить)
3) Правильно я уразумел алгоритм хотябы в общих чертах?

Очень прошу поправить меня там где неправ
И с удовольствием выслушаю другие идеи по поводу этой же темы, или алгоритма.
И вообще мне кажеться что всё это не очень сложно в реализации, сложности могут возникнуть лишь с интерфейсом, графикой, а в общих чертах алгоритм сравнительно прост, или я не прав?

З.Ы. Lappу +1 за идею (уж очень она мне понравилась )

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

[RathaR]

Опуская подробности, скажу, что одним из основных условий реализуемрсти такого автомата является несильное ветвление графа игры. Иначе говоря, если на каждои ходу у игрока выбор из нескольких ходов - годится.

эм...я,не сильно розбираюсь в теории графов, скажу даже больше, вообще в ней не розбираюсь , но сравнивая монополию и крестики нолики я исходил из следующих соображений:
у ИИ при совершении хода - выбор из следующих вариантов действий:
1) Купить недвижимость (если нет, здать на аукцион);
2) Поучаствовать в аукционе(неважно хто его обявил, либо участвует, либо нет, если да то активно, или неочень);
3) Заложить недвижимость;
4) Выкупить ранее заложеную недвижимость;
5) Взять ссуду в банке;
6) Погасить ссуду в банке;
Вроде всё перечислил...сделки между игроками отменяються, ну и по поводу тюрьмы правила тоже упрощаються...
Таким образом у ИИ на каждом ходе выбор из 2(что чаще всего - купить/аукцион)-4(что реже - заложить/взять ссуду/купить/аукцион) вариантов.
Правда нужно обдумать одновременное выполнение нескольких условий (заложить+купить, взять ссуду+выкупить заложеное+купить, взять одну ссуду+погасить другую).
Ну а в крестиках ноликах там ведь выбор у ИИ сначала из 9 вариантов, затем из 7, из 5 из 3...
Тоесть это не намного сложней чем крестики нолики, как мне кажеться.

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

[Lapp]

эм...я,не сильно розбираюсь в теории графов, <...> Тоесть это не намного сложней чем крестики нолики, как мне кажеться.

Собственно, теории для понимания ветвления не нужно..)). RathaR, я не ожидал, что простым упоминанием популярной игры вызову у тебя такие бурные чувства)). Мне жутко не хочется тебя разочаровывать, но все-таки как грится, считаю долгом предупредить: игра Монополия ну оооочень слабо годится для реализации той методикой, которую я употребил в Калахе.

Я обещал "покумекать и написать" - вот, выполняю вторую часть обещания. Первую, увы, можно считать невыполненной((. Мои попытки придумать определение для "похожести" ситауций не пошли дальше обычного сравнения финансовых возможностей, а этого мало. Игра наполовину дискретная, наполовину непрерывная. Собственно, как наша жизнь - у почти всех качеств есть непрерывный спектр изменения, но выбор чаще всего дискретный: институт, жена, и даже курицу в магазине ты берешь ЭТУ, а не ТУ, и именно она может оказаться тухлой.. Ни дать ни взять - наглядное воплощение принципа спонтанного нарушения симметрии (это из теории квантовых полей)). Монополия была задумана как максимальное приближение к жизни, и, мне кажется, авторам удалось этого добиться в довольно неплохой степени. Рынок всегда был очень сложным объектом для математического описания. В докомпьютерную эру, возможно, могло бы показаться, что в нем можно все рассчитать - были бы вычислительные мощности. И вот они есть - и что? Все точно так же сложно (последний кризиз тому примером). Более того, компьютеры сами вносят усложнения в рынок (по разным версиям, они сыграли свою роль в подготовке условий для него).

Буду рад продолжить беседу в этой теме, если ты выскажешь какие-то продуктивные соображения - у меня их нет((. А по поводу изначальной темы (проекта) я выскажусь в в изначальном топике)).

[RathaR]

Я обещал "покумекать и написать" - вот, выполняю вторую часть обещания.

Я приятно удивлён, и ОЧЕНЬ признателен что эта тема не канула в небытие

Буду рад продолжить беседу в этой теме, если ты выскажешь какие-то продуктивные соображения - у меня их нет((. А по поводу изначальной темы (проекта) я выскажусь в в изначальном топике)).

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

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

З.Ы.
Наверно не в тему, но интерес вызвала фраза

Более того, компьютеры сами вносят усложнения в рынок (по разным версиям, они сыграли свою роль в подготовке условий для него).

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

[Гость]

> признателен что эта тема не канула в небытие
Ничто не зря, и ничто не вечно

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

> И буду держаться за эту идею до конца
Флаг тебе в руки)).

> допустим у ИИ есть три состояния, ну или характера игры:
> 1 - Он скупает всё что попадаеться и пытаеться выкупить ...
> 2 - Он действует нейтрально, на "выжыдание" ...
> 3 - Он судорожно продаёт и закладывает все ...

В этих состояниях я вижу только то, что ты играть умеешь и понимаешь ситуацию. Границы этих "состояний" невозможно четко определить. Извини, но в программировании все должно быть именно ЧЕТКО. Потому что в конечном итоге решение принимает железка по четко заданным правилам (твой код). Конечно, можно ввести и случайный элемент, но его следует использовать только при выборе из РАВНЫХ (в принятой системе сравнений) возможностей. А сама система сравнения возможностей все-таки должна быть ЧЕТКО ОПРЕДЕЛЕННОЙ. Представь себе, что ты комбинируешь некий параметр P (наподобие того же Доу Джонса), по которому принимаешь это решение:

if P₁ <= P then реализуется режим 1
if P₂ <= P < P₁ then реализуется режим 2
if P <= P₃ then реализуется режим 3

Тебе не кажется странным, что если Р=P₁, то мы все скупаем, а если P изменился всего на один пункт - все, стратегия резко меняется на выжидание? Напрашивается вывод: увеличить количество состояний, сгладив по возможности переходы между ними. Но тогда возникает вопрос: до какой степени сглаживать? Вопрос совершенно не праздеый, когда речь идет о программировании, повторяю: все должно быть четко определено. И тогда мы приходим к идее непрерывной зависимости, то есть к тому, от чего ты пытался уйти . В этом нет ничего плохого, просто природа этой задачи такова, что та самая технология неприменима - вот и все. Хочешь решать ее - придумай нечто другое, более подходящее.


> по ходу игры будут в определённый файл делаться записи,
> по ходам, на первый ход у человека было столькото недвижимости
> (по кол-ву) и столькото денег, на второй столькото и столькото ,
> и постоянно вычисляеться среднее арифметическое,
Что ж, это можно условно принять за исходную идею. Но заметь, что ты тут производишь НЕСКОЛЬКО сравнений. И тебе нужно ввести некоторое соотношение порядка в МНОГОМЕРНОМ пространстве. Иначе говоря, если сравнить две точки (x,y) на плоскости, то что больше: точка (3,7) или точка (2,9)? Если сравнивать только по расстоянию до точки (0,0), то будет ли это соответствовать цели?

> Жажду выслушать критику по поводу этих мыслей
Типа вот..

Отвечаю на P.S.
Почему это не по теме? Как раз ОЧЕНЬ даже ПО теме, ибо напрямую касается реализации алгоритма принятия решений.
Соображение такое. В последнее время основная часть сделок на ьирже производится не людьми, а программами. Я не знаю точной статистики, но кажется их число больше половины (по количеству, по финансам может и нет). Эти программы в основном рассчитаны на анализ сиюминтной (идаже сиюсекндной скорее) ситуации и ориентированы на сиюминтную прибыль. Программы как правило не пытаются учесть долгосрочного изменения ситуации на рынке, это им просто не под силу. И вот ТАКУЮ с позволения сказать "стратегию" ты называешь "рациональной"? Я полагаю, что ситуация в настоящее время доходит до того, что влияют задержки сетевой передачи пакетов. Иначе говоря, если случатся неполадки у крупного Интернет-провайдера, это может повлиять на исход торгов. Я согласен, людской злобе тут места не остается, но вступают в игру другие параметры. И неясно, что лучше..