Я задал этот вопрос на Boardgame StackExchange , касающийся того, какой персонаж имеет лучшие шансы на победу в матче Button Men. Это заставило меня задуматься о конкретных подходах к ответу на вопрос в разумные сроки. Правила для игры довольно простые.
В начале игры каждый игрок бросает свои многогранные кости.
Игрок с самым низким кубиком идет первым (связи используют следующий младший кубик).
Игрок может захватить кубик противника двумя возможными способами.
1) Силовая атака: с одним кубиком с большим или равным значением (и затем перебросьте этот кубик).
2) Атака умением: с несколькими кубиками, которые в точности равны умирающим противникам (перебрасывая все кости, использованные при захвате).
3) Если игрок не может поймать смерть противника, он должен пройти.
Игра заканчивается, когда у игрока не осталось игральных костей. Каждый игрок получает по X очков за каждый dX, полученный от противника, и 0.5dX за каждый оставшийся кубик. (т. е. если вы захватили противников d4, d4, d10, d12, d20 и все еще имеете свой собственный d20, вы наберете (4 + 4 + 10 + 12 + 20 + 0,5 * 20) = 60 баллов.)
Грубая сила
Персонаж Avis выбрасывает d4, d4, d10, d12 и dX (где dX - это d4, d6, d8, d10, d12 или d20). Это означает, что они имеют максимум (4 * 4 * 10 * 12 * 20) 38 400 состояний после их первого броска. Персонаж Яго имеет максимум 4d20 (если они используют d20 для своего смертельного куба dX), что дает ему 160 000 возможных начальных состояний. Вместе это приводит к 6,144 миллиардам возможных начальных состояний, и все становится только хуже. Без какого-либо интеллекта, пытающегося разобраться с лучшими ходами, нужно попробовать все возможные ходы. В худшем случае игрок может перебросить все свои кости в атаке навыка. Поскольку до окончания игры необходимо сделать до 8 снимков, даже повторное использование одного d20 в силовой атаке для каждой стороны складывается (20 ^ 8 = 25,6 миллиарда). Метод грубой силы может привести к оценке 157+ квинтиллионов или более возможных состояний. Это невозможно, но есть лучший способ. Метод грубой силы несколько раз переоценивал одни и те же игровые состояния.
Цепь Маркова
Если мы посмотрим на серию возможных состояний, которые в конечном итоге переходят в конечную игру, мы можем оценить шансы перехода из одного состояния в игру в другое и, наконец, определить шансы каждого персонажа на победу в начале. игры Игра заканчивается только в нескольких возможных состояниях (условно говоря). У одного игрока нет игральных костей, а у другого игрока есть некоторая комбинация оставленных им собственных костей (в приведенном ниже примере игральная кость dX была выбрана как d20. Это просто доказательство концепции, так что не беспокойтесь, что эта игра в кости меняется от игры к игре).
Avis: d4 | д10 | д12 | d20
Avis: d4, d4 | d4, d10 | d4, d12 | d4, d20
Avis: d4, d4, d10 | d4, d4, d12 | d4, d4, d20 | d4, d10, d12 | d4, d10, d20 | d4, d12, d20 | d10, d12, d20
Avis: d4, d4, d10, d12 | d4, d4, d10, d20 | d4, d10, d12, d20
Avis: d4, d4, d10, d12, d20
Яго: d20
Яго: d20, d20
Яго: д20, д20, д20
Яго: д20, д20, д20, д20
Как только эти конечные игровые состояния подсчитываются для каждого игрока, и определяется, является ли это состояние выигрышем или проигрышем для каждого персонажа, могут быть рассмотрены «следующие за последним» игровые состояния.Аналогичным образом могут быть определены шансы на то, насколько вероятно, что каждое "следующее за последним" игровое состояние приведет к одному из наших конечных игровых состояний.Некоторые простые вычисления в электронной таблице приводят к результату около 9,9 миллиардов игровых состояний (поскольку мне нужно только сохранить выигрышную / проигрышную природу игрового состояния, я должен быть в состоянии упаковать эту информацию в один бит, верно?).Это не похоже на непреодолимое количество игровых состояний для хранения / оценки.
Можно ли ответить, какой персонаж лучше использовать с помощью цепей Маркова, в разумные сроки и с довольно недорогим оборудованием??
Есть ли лучший способ решить эту проблему?