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

[profrotter]

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

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

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

Дальше надо думать как обучать. Первый вариант - это условно оценить каждое решение. Приближает ли оно нас к победе? Мешает ли противнику выиграть? Одновременно решает обе эти задачи? Начинаем обучаемому объекту предъявлять ПС-сгенерированные состояния игрового поля, получаем решение, вычисляем показатель качества решения, изменяем веса нейронов. Второй вариант, который мне от чего-то кажется очень привлекательным, заключается в том, что обучаемый объект проводит большое количество игр (скажем не менее 100) с рандомным противником (который просто случайным образом делает незапрещённые ходы) при этом фиксируется количество побед и оценивается "вероятность победы". Она то и будет показателем качества обучения. Корректируются веса. Проводим следующие сотню игр и тд. На начальных этапах возможно вероятность победы будет нулевая, тогда новые веса можно генерировать случайно.

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

Первая пробема сразу видна и заключена в том, что неизвестно количество слоёв и количество нейронов в слоях сети. Но экспериментировать никто не мешает.

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

[arseniiv]

profrotter в сообщении #807498 писал(а):

Количество входов - количество клеток игрового поля.

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

[profrotter]

arseniiv в сообщении #807601 писал(а):

А если оно бесконечное?

Не бывает. На бесконечном поле я сам кого хошь обыграю: уйду на бесконечность, нарисую что надо и всё. Жаль только соперник об этом не узнает. Ну можно, скажем, большие поля анализировать по подполям заданного размера.

Человек захотел поиграться - я внёс свои пять копеек для начала. Вот вам и крестики-нолики, вот вам и обучение. А потом он сам нас научит.

[arseniiv]

profrotter в сообщении #807670 писал(а):

уйду на бесконечность, нарисую что надо и всё. Жаль только соперник об этом не узнает.

Надеюсь, вы не серьёзно.

В общем, я просто хотел чуточку уточнить, ничего более.

[profrotter]

arseniiv в сообщении #807675 писал(а):

Надеюсь, вы не серьёзно

Серьёзно. Алгоритм должен иметь возможность обзора всего поля. Этот обзор может быть "параллельным" или "последовательным". В первом случае алгоритм имеет столько входов, сколько клеток на поле. Во втором - осуществляет сканирование, в простейшем случае рассматривая последовательно сдвигаемые вдоль и поперёк квадраты. В каждом квадрате может быть принято решение сделать ход. Этот ход может быть помехой противнику для выигрыша, может приближать алгоритм к выигрышу, может быть ещё каким нибудь. Потом следует рассмотреть принятые в каждой позиции сканирования решения и выбрать самое ценное. В общем тут напрашивается второй алгоритм, который принимает окончательное решение. Как в передаче "Что? Где? Когда?" - там у каждого игрока своя версия, но капитан команды выбирает одну из них. Этого капитана, наверное, тоже можно обучать. Какой из способов обзора поля эффективнее (по вычислительному ресурсу или по экономии памяти) судить не берусь.

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

И ещё один момент. Чем больше поле, тем больше количество меток победителя должны быть выстроены в ряд. На бесконечном поле их должно быть сколько?

В общем надо начинать с простого.

[mustitz]

Обычно делают готовые перебор и alpha-beta. Оценочная функция зависит от некоторых параметров, которые и настраиваются в процессе игры (например, программа играет сама с собой)

[arseniiv]

profrotter в сообщении #807745 писал(а):

На бесконечном поле ходы одного соперника могут быть попросту не найдены другим.

Ходы же как-то объявляются. Например, один игрок передаёт второму координаты поля. Как-то же вычислили некоторые свойства крестиков-ноликов на бесконечной доске; например, что у начинающего больше шансов выиграть?

-- Пн дек 30, 2013 03:02:48 --

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

[B@R5uk]

У Матрина Гарднера в его книге "Математические досуги" есть классный пример самообучающейся машины для игры в крестики-нолики из... вы не поверите! из спичечных коробков! Очень советую скачать книжку и прочитать соответствующую главу.

[Aritaborian]

Глава 14? Но там не крестики-нолики, а другая игра (крестики-нолики лишь вскользь упоминаются в конце главы, на стр. 178).

[vlad_light]

Цитата:

У Матрина Гарднера в его книге "Математические досуги" есть классный пример самообучающейся машины для игры в крестики-нолики

Спасибо, почитал! Рассмотренный автором алгоритм очень похож на мой (описанный в 1-ом посте), правда допускает оптимизации за счет симметрии и т.п. (хотя сложность этих двух алгоритмов эквивалентна). Но, как я указал, для игры "5 в ряд" этот алгоритм будет требовать огромное кол-во памяти и никакие оптимизации не спасут

-- Чт янв 09, 2014 19:08:45 --

Мне понравилось предложение profrotter'а, сейчас пытаюсь реализовать что-то подобное.

[Утундрий]

profrotter в сообщении #807670 писал(а):

На бесконечном поле я сам кого хошь обыграю: уйду на бесконечность, нарисую что надо и всё. Жаль только соперник об этом не узнает.

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

[Yuri Gendelman]

arseniiv в сообщении #807601 писал(а):

profrotter в сообщении #807498 писал(а):

Количество входов - количество клеток игрового поля.

А если оно бесконечное?

Классическая доска для Гомоку (Gomoku) и Рендзю (Renju) - 15х15.

[mustitz]

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

Соответственно, обучение должно строиться на основе таких вещей, как (1) оценка позиции $E(p)$; (2) приоритет хода $P(m, p)$ при переборе вариантов. Эти две функции задают вместе с альфа-бета дают нам игровую программу. Возникает задача поиска таких функций $E$ и $P$, чтобы сила игры программы оказалась максимальной. Эту задачу можно решать как раз самыми разными методами, в частности генетические алгоритмы, нейросети, ...