Как я могу проверить, работает ли мой Tic Tac Toe A.I. идеально?

Я сделал крестики-нолики А.И. Учитывая каждое состояние доски, мой А.И. вернет 1 точное место для перемещения. (Даже если ходы одинаково правильные, он каждый раз выбирает один и тот же, а не случайный)

Я также сделал функцию, которая повторяет все возможные действия, сделанные с помощью ИИ.

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

Я делаю это, когда ИИ ходит первым, а когда другой ходит первым... и складываю их вместе. Я получаю 418 возможных побед и 115 возможных ничьих и 0 возможных поражений.

Но теперь моя проблема в том, как мне максимизировать количество выигрышей? Мне нужно с чем-то сравнить эту статистику, но я не могу понять, с чем ее сравнивать.


python artificial-intelligence recursion greedy
person Thomas    schedule 01.12.2012    source источник
comment
@JakobBowyer: youtube.com/watch?v=NHWjlCaIrQo   -  person hammar    schedule 02.12.2012
comment
@hammar youtube.com/watch?v=6uVunn6Vux4   -  person Jakob Bowyer    schedule 02.12.2012
comment
Если он совершенен, он никогда не может проиграть, если запустится.   -  person GolezTrol    schedule 02.12.2012
comment
@GolezTrol Нет, ты ошибаешься. Это не доказывает, что она идеальна, а только то, что она хороша. Для того, чтобы быть совершенным, он должен выиграть при всех возможностях. Возможно, мой ИИ сравняет счет в некоторых из них, а не победит.   -  person Thomas    schedule 02.12.2012
comment
Я не говорил, что он идеален, если он никогда не теряется. Я сказал, если он идеален, он никогда не проиграет. Таким образом, все, что вы можете сделать из этого, это то, что если он проигрывает игру, которую начал, то он не идеален, но не наоборот. Не очень полезно, я согласен, поэтому я рад, что не опубликовал это как ответ. ;)   -  person GolezTrol    schedule 02.12.2012

Ответы (3)


arrow_upward
5
arrow_downward

Вы читали статью в википедии? ссылка

Количество клеммных позиций

При рассмотрении только состояния платы и после учета симметрии платы (т. е. поворотов и отражений) имеется только 138 позиций клеммной колодки. Предполагая, что X делает первый ход каждый раз:

  • 91 уникальная позиция выиграна (X)
  • 44 уникальные позиции выиграл (O)
  • Разыгрываются 3 уникальные позиции

Количество возможных игр

Без учета симметрии количество возможных игр можно определить вручную по точной формуле, которая дает 255 168 возможных игр. Предполагая, что X делает первый ход каждый раз:

  • 131 184 завершенных игры выиграл (X)
  • 77 904 завершенных игры выиграл (O)
  • 46 080 завершенных игр разыграны

Вы можете сгенерировать 138 позиций клеммной колодки из первого абзаца.

or

Вы можете запустить достаточно тестов на случайных полях и сравнить свои результаты со статистикой отсюда ссылка

Win in 5 moves    1440     0.6%
Win in 6 moves    5328     2.1%
Win in 7 moves    47952   18.8%
Win in 8 moves    72576   28.4%
Win in 9 moves    81792   32.1%
Draw              46080   18.1%    
Total             255168 100.0%
person akaRem    schedule 01.12.2012
comment
как сравнить 131 184 победы с 418 победами? Как вы сравниваете эту статистику с моими результатами, вот мой вопрос. - person Thomas; 02.12.2012
comment
сделать 91+44+3=138 установок доски из первого абзаца. Запустите ИИ. Сравните количество побед/проигрышей/ничьи. - person akaRem; 02.12.2012
comment
@BlazArt вы можете их сгенерировать: прямой поиск + некоторые ограничения на симметрию и вращение поля. Или все-таки сделать брутфорс и сравнить с этим se16.info/hgb/tictactoe.htm (ссылка из википедии) - person akaRem; 02.12.2012

arrow_upward
0
arrow_downward

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

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

person user711413    schedule 01.12.2012
comment
255168 игр. Ok. У вас есть некоторые результаты, например. 51% побед, 40% поражений, 9% ничьих. Это хорошо или плохо? - person akaRem; 02.12.2012

arrow_upward
0
arrow_downward

Одна проблема с ответом akaRem заключается в том, что оптимальный игрок не должен выглядеть как общее распределение. Например, игрок, о котором я только что написал, выигрывает примерно в 90% случаев у кого-то, играющего случайным образом, и в 10% случаев ничья. Вы должны ожидать, что статистика akaRem совпадет только в том случае, если у вас есть два игрока друг против друга, играющие случайным образом. Два оптимальных игрока всегда приводят к ничьей.

person wwfarch    schedule 26.08.2013