Ним игровой вопрос

Question

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

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

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

РЕДАКТИРОВАТЬ:

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

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

РЕДАКТИРОВАТЬ 2: хорошо, так что без правила, которое вы можетеНе так же, как и у предыдущего игрока, я думаю, что это довольно просто.

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

РЕДАКТИРОВАТЬ3:

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

Концепция, к которой я стремлюсь, объясняется в концепции модульной арифметики , на случай, если это поможет.

<ч />

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

<ч />

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

Просто продолжайте задавать вопросы и отвечать себе:

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

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

<ч />

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

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

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

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

Answer 2

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

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

Редактировать : Вот код, показывающий, как легко сделать идеального агента.Для кодирования потребовалось около 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 на себя, либо на случайногоагент, так что вы изучаете ходы, которые совершает совершенный игрок.

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

Редактировать 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 

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

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