Grundy의 게임이 두 개 이상의 힙으로 확장되었습니다.

Question

Grundy의 게임에서 두 힙을 어떻게 깰 수 있습니까?

힙을 임의의 수의 힙으로 분할하면 (그 중 두 개가 동일하지 않음) 어떻습니까?

Answer 1

이 게임 유형은 "Winning Ways for your Mathematical Plays"시리즈에서 매우 자세하게 분석됩니다. 당신이 찾고있는 대부분의 것들은 아마도 1 권입니다.

Nimbers (Wikipedia), Sprague-Grundy theorem (Wikipedia) 또는 "combinatorial game theory"에 대한 검색을 할 수도 있습니다.

내 지식이 상당히 녹슬어서이 특정 문제로 나 자신을 도울 수는없는 것 같습니다. 당신이 이미 내가 연결된 모든 것을 알고 있다면 내 변명.

편집 : 일반적으로 이러한 유형의 게임을 해결하는 방법은 스택 크기를 "빌드"하는 것입니다. 따라서 1의 스택으로 시작하여 누가 최적의 플레이로 승자를 결정하십시오. 그런 다음 2의 스택에 대해 동일한 방법으로 1 &으로 분할 할 수 있습니다. 1로 이동하여 1로 변할 수 있습니다. & 2. 4와 같음 (여기에서 더 까다로워 짐) : 3 & 1 또는 2 & 2, Spague-Grundy theorem &을 사용하여 nimbers에 대한 대수 규칙을 사용하면 누가 이길지 계산할 수 있습니다. 대답을 알 필요가있는 스택 크기에 도달 할 때까지 계속하십시오.

편집 2 : 내가 코멘트에서 말하고있는 웹 사이트가 다운 된 것 같습니다. 다음은 백업의 링크입니다 : Wayback Machine - Introduction to Combinatorial Games.

Answer 2

그런 디의 게임, 그리고 같은 많은 게임이 같은 알고리즘으로 해결할 수 있습니다 GameState의

//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; 
} 

구현을 게임에 따라 이동합니다. Grundy의 게임에서는 둘 다 간단합니다.

GameState은 게임의 각 힙 크기를 나타내는 정수 목록을 저장합니다.

Move은 initialHeapSize 정수 및 resultingHeapSizes 정수 목록을 저장합니다.

GameState::possibleMoves은 힙 크기 목록을 반복하며 각각에 대한 법적 구분을 결정합니다.

GameState::applyMove(Move)은 GameState의 사본이 보드에 적용된 것을 제외하고는 GameState의 복사본을 반환합니다.

---

GameState::possibleMoves은 "고전적인"그런 디의 게임과 같이 구현 될 수

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 돌의 시작 상태를 시작하면 긴 대기 시간을 갖게됩니다.따라서 성능을 향상 시키려면 memoization을 구현해야합니다.

최상의 결과를

, 분류, 각 GameState의 힙 크기 목록을 유지하고, 크기 2 또는 1