Tic tac toe, принятие решения

Совсем недавно начал изучение ИНН, и на примере игры в X0, встал вопрос.
Как нейронная сеть должна принимать решение о ходе?
Должна ли она анализировать каждый возможный ход (каждую свободную ячейку) и выдавать вероятность победы для каждой ячейки?
Либо на выходе нейросети должен быть индекс ячейки?

Если не сложно, объясните, как должна работать нейросеть с игрой X0 (поле 10 на 10).

0

Абстрагируясь от конкретного метода (ИНС), чисто по теории принятия решения: в чем заключается решение на каждом ходе? Выбор из какого множества вариантов решения?

0

Сообщение от Mikhaylo в чем заключается решение на каждом ходе?

полагаю, оценить каждый ход и выбрать наиболее благоприятный... или как?

0

10х10 - это значит 100 вариантов решения, с каждым шагом уменьшается вплоть до одного решения. Всего шагов 50, максимум. Допустим мы сделали уже каким-то образом 25 ходов, спрашивается: надо ли решения прорабатывать на всю игру сразу или "жить одним днем"? Ответ: если ты умеешь находить оптимальные стратегии на всю игру, то сделаешь оптимальный 26-й ход, затем после хода противника у тебя будет иметься больше информации о ходе игры, чем на предыдущем ходе, следовательно, на 27-м ходе стратегия может обновиться и стать оптимальнее по отношению к новой игровой ситуации. Значит надо "жить одним днем", строить игру по стратегии вредно.

Добавлено через 8 минут
Теперь о благоприятности ходов. Я могу точно сказать, что ход, который выигрывает игру, является благоприятным. Даже трудно сообразить, какой ход неблагоприятный.. наверное тот, после которого у соперника нет других ходов, кроме выигрышных. Все остальные ходы имеют неоцениваемую благоприятность, так как все зависит от соперника. Можно ввести искусственные критерии благоприятности, но хотелось бы это делать как-то объективно, а не наобум. Трудно...

Добавлено через 7 минут
Ну да. Допустим ИНС обучается на чужих партиях. Благоприятными являются ходы у игрока, который выиграл; неблагоприятные - у проигравшего. Можно учиться на базе собственных игр, но выводы делать после окончания партии.

Добавлено через 9 минут
На вход нейронной сети подаются игровые ситуации - массив из нулей, крестиков и пустых ячеек. 100 входов. Каждую игровую ситуацию можно поворачивать на углы 90, 180, 270 градусов, чтобы увеличить объем обучающей выборки в 4 раза. На выходе - один из 100 вариантов решения. Я только не знаю, как быть с занятыми ячейками.. ведь из 100 вариантов часть решений запрещены. Может быть на выходе должен быть просто порядковый номер пустой ячейки?

1

я походу понял. для поля 10х10 будет всего 100 входных нейронов, у каждого 100 входов. Каждый нейрон соответствует позиции на доске (от 1 до 100), а входной вектор содержит значения {-1; 0; 1} (какое значение за что отвечает пока не разбирался, все зависит от функции нейрона и корректировки весов). На выходе у нейрона будет вероятность корректного хода, от 0 до 1.
В итоге, проходим все нейроны, и ставим крестик в позиции, нейрон которой выдал максимальный результат.

Так я это представляю. Буду рад любым комментариям, поправкам итд.

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

0

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

0

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

0

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

Очевидно же, что соперник скорее всего не идиот и даже из огромного множества выберет тот вариант, который приведёт к его скорейшему выигрышу. А любой наш ход может ускорить или замедлить выигрыш противника - соответственно, и благоприятность каждого хода оценить возможно. Например, выигрыш при xxxxx, имеем oxxx, следовательно ход oxxxo будет более благоприятным, чем ooxxx, потому что, хотя он и не ведёт к выигрышу, он отдаляет от выигрыша нашего противника. Потому что если мы пойдём ooxxx, следующий ход противник, не будучи идиотом, пойдёт ooxxxx и приблизится к выигрышу.

Сообщение от Mikhaylo Я только не знаю, как быть с занятыми ячейками.. ведь из 100 вариантов часть решений запрещены. Может быть на выходе должен быть просто порядковый номер пустой ячейки?

Мы подаём в нейросеть не только ситуации, но и решения ситуаций. А так как все решения находятся в пустых ячейках, то и нейросеть будет всегда ходить только в пустые ячейки... Впрочем, я слабо представляю себе работу ИНС...

Сообщение от Bio man {-1; 0; 1} (какое значение за что отвечает пока не разбирался, все зависит от функции нейрона и корректировки весов)

А что тут разбираться? -1 = x, 0 = пусто, 1 = o.

Вот только лучше сначала сделать сеть, которая выработает правильную стратегию в игре на стандартном поле 3x3 (как я помню, беспроигрышная стратегия только одна), это будет говорить о том, что модель сети правильная. Потом можно расширить поле до 4x4, и так далее. Беря поле сразу 10x10 есть высокий шанс запутаться, правильно ли работает модель.

1

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

Здесь ошибка в рассуждениях. Многие игры позволяют блефануть, то есть сделать вид, что ты почти выиграл, ан-нет!
Все критерии благоприятности будут искусственные: не понятно, являются ли десять последовательностей xxx лучше, чем одна xxxx. Или кому-то может показаться, что пять xxxx лучше, чем сорок xxx, хотя на самом деле все зависит от конфигурации (игровой расклад 10х10).

0

Сообщение от Mikhaylo Многие игры позволяют блефануть

Крестики-нолики настолько просты, что исключают такой вариант развития игры.

Сообщение от Mikhaylo Все критерии благоприятности будут искусственные: не понятно, являются ли десять последовательностей xxx лучше, чем одна xxxx. Или кому-то может показаться, что пять xxxx лучше, чем сорок xxx, хотя на самом деле все зависит от конфигурации (игровой расклад 10х10).

Одна xxxx на ходе крестиков - это уже выигрыш (xxxxx), одна oxxxx на ходе ноликов - это однозначно oxxxxo, чтобы предотвратить выигрыш крестиков, вне зависимости от количества xxx.

Так что в крестиках-ноликах 10x10 возможна только одна стратегия: закрывать чужие последовательности, пока они не стали четвёрками (oxxxx или xoooo) иначе сразу проигрыш, ну и по пути пытаться собрать свою четвёрку... Блефовать тупо некогда.

0

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

0

Вообще, не знаю, какая стратегия лучшая в 10 на 10 и возможно ли вообще выиграть, или будет постоянно ничья, или будет всегда побеждать тот, кто ходит первым... А ведь ещё бывают крестики-нолики в кубе (3x3x3, 10x10x10)...

Вот что нашёл про стратегии:
http://www.iqfun.ru/articles/t... rman.shtml
http://www.dokwork.ru/2012/11/tictactoe.html
Думаю, пригодится.

Добавлено через 32 секунды

Сообщение от Mikhaylo Что делать в начале игры, чтобы противник не сделал "вилку"?

Лучший ход в крестиках-ноликах - в центр поля, это вроде бы вообще без вариантов...

0

имхо в крестиках-ноликах 10 на 10, кто первым начинает, тот выигрывает
по крайней мере, я играл в рендзю, и там есть специальные ограничения на второй ход, чтобы выравнять шансы

1

Сообщение от TimKruz Лучший ход в крестиках-ноликах - в центр поля, это вроде бы вообще без вариантов...

Вы не поняли. Под началом игры я понимаю не только самый первый ход, а время, когда еще не появились тройки xxx и четверки xxxx.

0