Ветвление фактор и глубина

Question

Вопрос

Простая игра для двух игроков включает в себя кучу N спичек и два игроков, которые имеют чередующиеся повороты. В каждом повороте игрок удаляет 1, 2 или 3 спички из кучи. Игрок, удаляющий последний матч , теряет игру.

A) Что такое коэффициент ветвления и глубина игрового дерева (дать общее решение, выраженное в терминах N)? Насколько велика область поиска space?

B) Сколько уникальных состояний в игре? Для больших N, что можно сделать, чтобы сделать поиск более эффективным?

Ответ

A) Я сказал, что коэффициент ветвления будет 3, но я оправдывал это, потому что игрок может только когда-либо удалить до 3-х матчей, а это означает наше дерево, как правило, у них трое детей. Вторая часть относительно глубины, я не уверен.

B) N x 2 где N - количество оставшихся совпадений. Я не уверен, как мы могли бы сделать поиск более эффективным? Может быть, может быть обрезка альфа-бета?

Answer 1

A: Для глубины, представьте себе, как будет выглядеть самая длинная игра. Это игра, состоящая из обоих игроков, удаляющих только 1 матч за каждый ход. Поскольку существует n совпадений, такая игра будет принимать n оборотов: дерево имеет глубину n.

B: Имеются только 2 * N состояния, каждый из которых доступен из 3 состояний с более высоким количеством совпадений. Поскольку число матчей обязательно уменьшается, так как игра продолжается, график возможных состояний - это DAG (Direct Acitlic Graph). Таким образом, метод динамического программирования позволяет анализировать эту игру. В итоге вы увидите, что оптимальный ход зависит только от N mod 4, а N - оставшихся совпадений.

EDIT: Идея доказательства для N mod 4: Каждая позиция является либо проигрывающей, либо выигрышной. Потерять позицию - это ситуация, когда независимо от того, что вы играете, если ваш противник играет оптимально, вы проиграете. Точно так же выигрышная позиция - это ситуация, когда, если вы играете в правильные ходы, противник не может победить. N = 1 - проигрывающая позиция (по определению игры). Таким образом, N = 2,3,4 являются выигрышными позициями, потому что, удаляя правильное количество матчей, вы помещаете противника в проигрышную позицию. N = 5 - проигрывающая позиция, потому что независимо от того, какое допустимое количество совпадений вы удаляете, вы ставите противника в выигрышную позицию. N = 6,7,8 - выигрышные позиции ... у вас есть идея.

Теперь речь идет только о том, чтобы сделать это доказательство формальным: считать гипотезой, что позиция N является проигрышной позицией тогда и только тогда, когда N mod 4 = 1. Если это верно до некоторого целого числа k, вы можете доказать, что это верно для k+1. Это верно до k = 4, как мы показали ранее. По повторяемости, это верно для любого N.

Answer 2

Состояние игры в любое время можно описать по очереди и количеству матчей, проводимых каждым игроком. После n перемещений существует 3^n возможных историй, но для больших n, намного меньше, чем 3^n возможных состояний, поэтому вы можете сэкономить время, например, признав, что вы собираетесь столкнуться с состоянием, с которым вы уже столкнулись, и выработали значение для ранее.

См. Также https://en.wikipedia.org/wiki/Nim - если это Nim или множество Nim, для него разработаны эффективные стратегии.