Игра Гранди расширилась до более чем двух куч - PullRequest
Новая
       60

Игра Гранди расширилась до более чем двух куч

1 голос
/ 21 марта 2012

Как может В разбить кучу на две кучи в игре Гранди?

Как насчет разбить кучу на любое количество куч (нет двух равных)?

Ответы [ 2 ]

1 голос
/ 21 марта 2012

Игры такого типа детально проанализированы в серии книг " Пути победы для ваших математических игр ". Большинство вещей, которые вы ищете, вероятно, в томе 1.

Вы также можете посмотреть по этим ссылкам: Nimbers (Википедия) , Теорема Спрейга-Гранди (Википедия) или выполнить поиск по "теории комбинаторных игр".

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

Редактировать: В общем, метод решения этих типов игр заключается в "наращивании" размеров стеков. Поэтому начните со стека 1 и решите, кто выиграет с оптимальной игрой. Затем сделайте то же самое для стека 2, который можно разделить на 1 и 1. Переходите к 3, который можно разделить на 1 и 2. То же самое для 4 (здесь становится сложнее): 3 & 1 или 2 & 2, используя теорему Спаге-Гранди и алгебраические правила для нимберов, вы можете рассчитать, кто победит. Продолжайте, пока не достигнете размера стека, для которого вам нужно знать ответ.

Редактировать 2: Сайт, о котором я говорил в комментариях, кажется, не работает. Вот ссылка на его резервную копию: Wayback Machine - Введение в комбинаторные игры .

0 голосов
/ 21 марта 2012

Игра Grundy's и многие другие подобные игры могут быть решены с помощью такого алгоритма: 

//returns a Move object representing the current player's optimal move, or null if the player has no chance of winning
function bestMove(GameState g){
    for each (move in g.possibleMoves()){
        nextState = g.applyMove(move)
        if (bestMove(nextState) == null){
            //the next player's best move is null, so if we take this move, 
            //he has no chance of winning. This is good for us!
            return move;
        }
    }

    //none of our possible moves led to a winning strategy.
    //We have no chance of winning. This is bad for us :-(
    return null;
}

Реализации GameState и Move зависят от игры.Для игры Гранди оба просты.

GameState хранит список целых чисел, представляющих размер каждой кучи в игре.

Move хранит целое число initialHeapSize, иresultingHeapSizes список целых чисел.

GameState::possibleMoves перебирает свой список размеров кучи и определяет юридические деления для каждого из них.

GameState::applyMove(Move) возвращает копию GameState, кромеданный ход применяется к доске.

GameState::possibleMoves может быть реализовано для "классической" игры Grundy's следующим образом: 

function possibleMoves(GameState g){
    moves = []
    for each (heapSize in g.heapSizes){
        for each (resultingHeaps in possibleDivisions(heapSize)){
            Move m = new Move(heapSize, resultingHeaps)
            moves.append(m)
        }
    }
    return moves
}

function possibleDivisions(int heapSize){
    divisions = []
    for(int leftPileSize = 1; leftPileSize < heapSize; leftPileSize++){
        int rightPileSize = heapSize - leftPileSize
        if (leftPileSize != rightPileSize){
            divisions.append([leftPileSize, rightPileSize])
        }
    }
    return divisions
}

Модифицируя это, чтобы использовать "разделить на любое количество неравных куч "Правило - это всего лишь вопрос изменения реализации possibleDivisions.

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

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

...