Nim игра вопрос

Question

ОК, я должен сделать Nim игру и попытаться найти стратегию, чтобы всегда выиграть следующую игру Nim:

21 матчей, игрока 1 и 2 каждый дубль 1, 2, 3, 4 , или 5 совпадений в каждом повороте, и нельзя брать столько же совпадений, сколько и предыдущий игрок. Победитель выигрывает, если/когда они берут последний матч.

Мне нужно что-то программировать, но я даже не понимаю, что нужно начинать. Как я могу найти выигрышную стратегию с этим типом игры?

EDIT:

Так я понял, что вы всегда будете выигрывать, когда вы дойдете до 7 матчей еще в середине. Другой может принимать 2-5, и вы можете добавить до 7, взяв последний. когда другой принимает 1, вы принимаете 3 (другой не может принимать 3, а затем) и должен выбрать 1 или 2, и в этом случае вы получите второй и выиграете.

Однако, идя от 21 до 7 загадка для меня, я не могу понять, как вы можете всегда быть человеком добраться до 7.

EDIT 2: ИТАК без правила, что вы не можете взять так же, как и предыдущий игрок, это довольно просто, я думаю.

Вы должны сделать k = 5 + 1 = 6. тогда вы должны сделать первый ход таким образом, чтобы совпадения оставались тогда% 6 = 0. Итак, в этом случае сначала возьмите 3, а затем залейте ход другому игроку до 6. Однако в этом случае это не сработает, потому что другой игрок может забрать 3, после чего вы не сможете взять 3, чтобы заполнить до 6. Таким образом, есть моя проблема. Есть идеи?

EDIT3:

нормально, так что вы сказать, что я могу заставить 7 матчей. Однако предположим, что я принимаю то же самое мышление до этапа 14-7 матчей. (тогда это другой поворот)

Есть два сценария: 1: он занимает 2-5, и я заполняю его до семи, которые позволяют 7 там и я побеждаю. 2: он занимает 1, поэтому осталось 13. Когда я беру 3, как я делаю в (7-0), он становится 10. Затем он берет 5, и я больше не могу взять 5, чтобы закончить, и я потеряю.

В этом заключается проблема, когда сценарий 2 не является проблемой в (7-0) -ступенчатом сейчас. Как я могу это решить?

ДА, РЕШЕНИЕ:

Кстати, на 1 означает плеер: после того, как игрок 1 очереди и т.д. (я голландская).

ИТАК я попробовал некоторые вещи, и я думаю, что у меня есть решение. Сначала вы должны принять 1 матч в качестве первого игрока. Тогда другие ребята могут взять 2-5 матчей. Вы сравниваете (каламбур) свою сумму до 7, так что вы всегда будете иметь (21-1-7 =) 13 матчей слева в середине. Затем снова поворачивается игрок 2, и есть два сценария: игрок 2 принимает 1,2,4, или 5 совпадений, и в этом случае вы принимаете столько совпадений, что в левой части будет 7. (как было сказано ранее, когда вы принимаете совпадения, так что осталось 7, вы всегда будете выигрывать). Второй сценарий состоит в том, что игрок 2 занимает 3 матча, в этом случае их 10 в середине, когда настала ваша очередь. Вы не можете взять 3, чтобы сделать 7, потому что вы не можете взять 2 раза ту же сумму. Итак, вы берете 5, так что осталось 5. Игрок 2 затем не может взять 5, чтобы выиграть и должен выбрать 1-4, после чего вы можете взять оставшиеся и выиграть.

Это решение, я думаю.Я как-то пришел на него, потому что я заметил это:

Нормальная Nim игра с по модулю и т.д.:

P2 1 2 3 4 5 
P1 5 4 3 2 1 
------------------ 
    6 6 6 6 6 

Но вы не можете сделать 3,3 вот так Лик это:

p2 1 2 3 4 5 
p1 5 4 3 2 1 
--------------------- 
     7 7 7 7 

Так вы можете делать 7 каждый раз, а 1 - особый случай. Я не знаю, почему, но я интуитивно принимал 1 в качестве отправной точки, поскольку кажется, что вам нужно проявлять инициативу, чтобы иметь возможность контролировать действия другого. (нельзя делать два раза 1, чтобы другой должен был взять 2-5, что заставляет вас контролировать)

В любом случае, СПАСИБО много за всю помощь. Также для всей написанной программы. Я не мог использовать его, потому что он не будет компилироваться как недостаток хороших навыков java :), и я также хотел решить его сам.

В любом случае, я видел, что это вики, удача для людей в будущем, пытаясь решить это!

Answer 1

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

Вот три подсказки для вас:

1. Ваш moveset и moveset противника, одно и то же: взять 1, 2, 3, 4 или 5 матчей.
2. Эта игра, когда вы добираетесь до нее, является добавочной игрой.Да, вы вычитаете совпадения, но по-прежнему помогает думать с точки зрения добавления, когда вы формулируете свою стратегию.
3. Начните с этого: для любого противника, перемещающего X (где X равно 1, 2, 3, 4 или 5), что вы можете сделать, чтобы «отменить», что выйдет?

Концепция, которую я пытаюсь найти, объясняется в концепции modular arithmetic, в случае, если это помогает.

---

Edit: Ограничение не принимает одинаковое количество матчей делает интересные вещи, хотя. Мы должны будем рассмотреть это как краеугольный случай позже, но давайте сначала посмотрим, как вы согласны с тем, что я сказал до сих пор. Пожалуйста, не стесняйтесь прокомментировать это.

---

Edit 2: Вы правильно со вторым редактирования в целом (если правило о каких-либо повторных движений не было, я имею в виду). Но ваше первое редактирование было на правильном пути: вы можете заставить все работать в 7-е.

Просто продолжайте спрашивать и отвечать на себя:

Q: Как надежно заставить выигрыш для ИИ, сделав ИИ взять последний матч?
A: Заставьте ИИ оставить 7 совпадений, затем используйте свою стратегию, чтобы заставить ИИ занять 7-е место слева. Это потому, что вы можете вычесть ровно 7 совпадений.
В: Итак, как я могу выиграть для ИИ, убедившись, что ИИ занимает последний матч (но семь)?

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

---

Edit 3: Это просто мелочь, я подумал о том, что может помочь вам справиться с этой проблемой вы упоминаете в своем третьем редактирования.

Если для всех X в ходовых частях (1, 2, 3, 4, 5) осталось совпадение 2X, когда это ход ИИ, то вы можете принудительно выиграть, взяв X совпадений. (Вы подробно рассказали, как, кроме как с другим игроком, в вашем третьем редактировании)

К сожалению, это не то, что вы можете заставить, потому что я говорю о том, что есть 2X совпадения до поворота ИИ, тогда как другой условия выигрыша стратегии зависят от позиции после поворота ИИ, так что движение ИИ может заставить его.

Кроме того, вы хотите, чтобы избежать необходимости перемещать результат ИИ в 2X соответствует любому из этих X.

Answer 2

Используйте Minimax algorithm, возможно с обрезкой альфа-бета, если вам нужно сократить время работы.

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

Редактировать: Вот какой код, чтобы показать вам, как легко сделать идеальный агент. Для кодирования потребовалось около 5 минут.

public class MinimaxNim { 

    public static int getBestMove(int matchesLeft, int lastVal) { 
     int max = Integer.MIN_VALUE; 
     int bestMove = matchesLeft > 0 ? 1 : 0; 
     for (int move = 1; move <= 5 && move <= matchesLeft; move++) { 
      if (move == lastVal) 
       continue; 
      int val = minValue(matchesLeft - move, move); 
      if (val > max) { 
       bestMove = move; 
       max = val; 
      } 
     } 
     return bestMove; 
    } 

    private static int maxValue(int matchesLeft, int lastVal) { 
     if (matchesLeft == 0) 
      return -1; //min has won 

     int max = Integer.MIN_VALUE; 
     for (int toTake = 1; toTake <= 5 && toTake <= matchesLeft; toTake++) { 
      if (toTake == lastVal) 
       continue; 
      int val = minValue(matchesLeft - toTake, toTake); 
      if (val > max) { 
       max = val; 
      } 
     } 
     return max; 
    } 

    private static int minValue(int matchesLeft, int lastVal) { 
     if (matchesLeft == 0) 
      return 1; //max has won 

     int min = Integer.MAX_VALUE; 
     for (int toTake = 1; toTake <= 5 && toTake <= matchesLeft; toTake++) { 
      if (toTake == lastVal) 
       continue; 
      int val = maxValue(matchesLeft - toTake, toTake); 
      if (val < min) { 
       min = val; 
      } 
     } 
     return min; 
    } 
} 

Вы можете проверить с этим:

public static void main(String[] args) { 
    int count = 21; 
    int move = -1; 
    for (;;) { 
     move = getBestMove(count, move); 
     System.out.println("Player 1 takes " + move); 
     count -= move; 
     if (count == 0) { 
      System.out.println("Player 1 has won"); 
      break; 
     } 
     move = getBestMove(count, move); 
     System.out.println("Player 2 takes " + move); 
     count -= move; 
     if (count == 0) { 
      System.out.println("Player 2 has won"); 
      break; 
     } 
    } 
} 

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

Опять же, это не показывает вам лучшую стратегию , но она будет демонстрировать оптимальную игру против любого противника (хотя и не проверена).

Edit 2

В случае, если вы любопытны, из начального состояния есть только 26705 терминальные состояния (где игрок выиграл), которые должны быть рассмотрены. Это становится все меньше и меньше, когда вы делаете больше ходов. То, что делает это идеальным для минимаксного, заключается в том, что прогресс всегда выполняется ... как только вы в 15 матчах остаетесь в куче, вы не сможете вернуться к 17, например. В игре, подобной шахматам, вы можете получать циклы в дереве поиска, так как игроки могут просто танцевать вокруг доски, возвращаться к предыдущим состояниям и т. Д.

Answer 3

Подобно тому, как еще некоторые данные, чтобы рассмотреть, я побежал мой агент против всех возможных сценариев вы могли бы иметь в игре (1-21 палочки влево раз 5 возможных последних ходов). Некоторые из этих состояний невозможны (например, 20, причем последний ход равен 2). Я удалил большинство из них из таблицы, но, скорее всего, остался.

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

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

0 1 2 3 4 5 
21 1   
20 x   
19  3  
18 5 5 5  
17 4 4 5 
16 3 3 x 3 3 
15 2 1 1 1 1 
14 x 1 1 1 1 
13 x x x x x 
12 5 5 5 5 x 
11 4 4 4 x 4 
10 3 3 5 3 3 
9 2 3 2 2 2 
8 4 1 1 1 1 
7 x x x x x 
6 3 3 x 3 3 
5 5 5 5 5 x 
4 4 4 4 x 4 
3 3 3 x 3 3 
2 2 1 1 1 1 
1 x 1 1 1 1 

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

Одна вещь, чтобы отметить дживы в совершенстве с вашим анализом: если это ваш ход, и осталось 7 палочек, вы ввернуты! Но примечание 13 также.