Крестики-нолики

[vlad_light]

Хочу написать ИИ для игры крестики-нолики, который бы сам обучался. Реализовывать буду на языке си.
Моя идея:
1. Каждый ход ИИ ставит знак в случайном месте и сохраняет текущую расстановку.
2. В конце игры ИИ получает ориентированный граф, вершинами которого являются расстановки.
3. Каждой вершине приписывается число, равное сумме таких чисел по всем "потомкам" этой вершины. Если у вершины нет потомков -- ей приписывается $1$ за победу и $-1$ за поражение.
4. При последующих играх, если в графе присутствует соответствующая расстановка с положительным числом, ИИ следует ей. В противном случае -- случайно.
Проблема этого алгоритма в том, что при размере поля больше 3х3 он требует огромное количество памяти.
Подскажите, пожалуйста, алгоритм по-интереснее. Спасибо!

[arseniiv]

Эвристический какой-нибудь. Как бы играли вы? Можно при каждом ходе обновлять список возможных цепочек и ходить так, чтобы закрыть цепочки подлиннее или сразу несколько. Можно пытаться составить противнику «вилку», после чего он обязательно проиграет, не имея возможности закрыть все ваши цепочки вовремя.

(Кстати, есть игра, где у первого игрока шансы на победу не настолько больше, чем у второго — Connect6, она и посложнее, и должна быть поинтереснее (жалко, не с кем было проверить).)

[vlad_light]

Дело в том, что я хотел составить алгоритм, который будет обучаться самостоятельно. Т.е. я хочу, чтоб до этого

Цитата:

Можно пытаться составить противнику «вилку», после чего он обязательно проиграет, не имея возможности закрыть все ваши цепочки вовремя.

алгоритм додумался сам

Цитата:

Как бы играли вы?

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

Цитата:

Connect6

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

[arseniiv]

vlad_light в сообщении #805118 писал(а):

Дело в том, что я хотел составить алгоритм, который будет обучаться самостоятельно.

Ясно. Тогда, конечно, надо выбрать удачный способ представления стратегии вместо дерева. Например, может быть такой: список правил с весами. Правила состоят, например, из шаблона, соответствующего каким-то конфигурациям на поле (например, там отмечается возможность каждой клетки некоторого прямоугольника быть пустой, содержать свой знак или знак противника), и координат относительно него, куда в данном случае надо поставить знак (или, например, делать эти прямоугольники сторонами в нечётное число клеток, а ставить всегда в центр — может быть, с такими будет проще работать). Из правил с совпавшими в какой-то части доски шаблонами выбирается правило с наибольшим весом; если ничего не совпало, крестик ставится как-то случайно.

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

-- Пн дек 23, 2013 18:52:48 --

Можно контролировать обучение не только результатами игры (это ж сколько тогда надо будет наиграть!), а каким-то «чувством цепочек» — считать, насколько меняется длина цепочек противника и своих. Например, если противник удлинил какую-то цепочку, ход можно посчитать неудачным, а если поставил где-то отдельный знак — удачным. И если удлинил длинную цепочку, это хуже, чем удлинил короткую. Расчитывать оценку хода можно по-всякому, и это тоже всё скажется на обучении.

[vlad_light]

К сожалению, не понял

Цитата:

Например, может быть такой: список правил с весами.

А правила придётся самому придумывать? Это не очень просто...

Цитата:

Можно контролировать обучение не только результатами игры (это ж сколько тогда надо будет наиграть!)...

Количество отыгранных игр не важно; главное, чтоб алгоритм стремился к идеальному (пусть даже медленно). А я не уверен, что это

Цитата:

каким-то «чувством цепочек» — считать, насколько меняется длина цепочек противника и своих.

приведёт к идеальному алгоритму. Т.е., зная такой подход, компьютер можно будет "обманывать", выдавая плохую позицию за хорошую.

[arseniiv]

vlad_light в сообщении #805213 писал(а):

А правила придётся самому придумывать? Это не очень просто...

Нет, всё труднее — или легче — надо сделать, чтобы самообучающаяся программа их умела создавать и оперировать ими. И вот от состояния базы правил будет зависеть, как она играет.

Доказать, что стратегия будет приближаться к оптимальной… В этом я не разбираюсь, но тут пока никакой определённой системы и нет. Я описал только то, как она могла бы быть устроена, а чтобы она ещё и работала… В результате может выйти система, которая стратегию приближает к оптимальной, или к какой-то другой, или стратегия вообще хаотически меняется. Да это и от сыгранных игр зависит. Можно специально ходить так, чтобы система не могла сформировать нормальную стратегию. Это всё где-нибудь рассматривается, должно быть — но не знаю где.

-- Пн дек 23, 2013 21:44:55 --

Разумеется, можно базу организовать по-другому, не в виде списка взвешенных правил описанного мной состава. И сами правила, и их организация, могут быть другими. Например, это последовательности команд какого-то языка.

[vlad_light]

Цитата:

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

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

Цитата:

Можно специально ходить так, чтобы система не могла сформировать нормальную стратегию.

Будем считать, что мы будем ходить "правильно"

[arseniiv]

vlad_light в сообщении #805229 писал(а):

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

Мне тоже так кажется, но я этим никогда не занимался, да ещё и, извините, сейчас не хочется.

[vlad_light]

(Оффтоп)

В любом случае, огромное спасибо за прявленный интерес к теме!

[arseniiv]

(Оффтоп)

Пожалуйста.

Кстати, если бы в игре имели значение сколь угодно длинные части доски, база предложенного вида бы не подошла вообще.

[Утундрий]

vlad_light в сообщении #805053 писал(а):

Подскажите, пожалуйста, алгоритм по-интереснее.

Потратить один вечер своего драгоценного времени и проанализировать все варианты вручную.

[arseniiv]

Вряд ли имеются в виду скучные крестики-нолики $3\times3$.

[bin]

Классический алгоритм - это альфа-бета отсечение, см. Википедию и книгу Е. Корнилов, Программирование шахмат и других логических игр, СПб: БХВ-Петербург, 2005. На с. 42 описание алгоритма, на с. 223 листинг программы "крестики-нолики". Я модифицировал в 3D $5\times5\times5$ - работает очень быстро!

[vlad_light]

Цитата:

Кстати, если бы в игре имели значение сколь угодно длинные части доски, база предложенного вида бы не подошла вообще.

Естественно.

Моя цель -- написать алгоритм, который будет обучаться самостоятельно. Первый алгоритм

Цитата:

Потратить один вечер своего драгоценного времени и проанализировать все варианты вручную.

требует огромного моего вмешательства, а второй

Цитата:

Классический алгоритм - это альфа-бета отсечение

не является обучаемым.

[bin]

vlad_light в сообщении #807361 писал(а):

Цитата:

Классический алгоритм - это альфа-бета отсечение

не является обучаемым.

Первоначально Вы поставили вопрос:

vlad_light в сообщении #805053 писал(а):

Подскажите, пожалуйста, алгоритм по-интереснее. Спасибо!

Я и подсказал интереснее в плане эффективности. Далее на основу этого алгоритма Вы можете навешивать всевозможные эвристики, как это делают, например, в шахматах. Можете и самообучение добавить. В этом случае можно быть уверенным, что будет отсекаться больше ветвей дерева решений, чем делает исходный классический алгоритм (другой вопрос: а насколько больше? будет ли усложнение оправданным?). А вот если пытаться сделать что-то с нуля, это в данном случае ИМХО выглядит изобретением велосипеда, но м.б. я и не прав: никто пока не доказал, что изобретенный с нуля велосипед будет хуже существующих