とにかくブルートフォースではないこのパズルをやってみませんか？

Question

あなたは最適な選択を前提にゲームに勝つ者を決定しようとしています。アイデアには、x個のスペース、_ _ _ _ _ _ _があります。プレイヤー1人は2つの連続したスポットに行き、マークします。その後、2人のプレイヤーが同じことをします。 WINSに行くことができない最初のプレイヤー。

P1：XX _ _ _ _ _

P2：XX _ XX _ _

P1：XX _ xxxxの

だから、プレイヤー2だから、前板与えられ、これは1つのpossiblityです勝つ。あなたは0が空きスペースを表し、1がマークされたスポットを表す配列が与えられます。配列には既にマークが付いているスポットがあるかもしれません。

私がこれを行うと考えることができる唯一の方法は、すべての移動をチェックし、すべての移動チェックで可能なすべての移動が成功するかどうかチェックすることです。私はこれをどのようにして行うのか完全に理解できませんが、もっと良い方法があることを期待していました。何か案は？

Answer 1

あなたはこのような問題を後方に働かせる必要があります。

すべての可能なゲーム状態を考えて、どれがプレイヤー1（W）の勝利であり、プレーヤー2（L）の勝利であるかを決定します。最初は、誰も遊ぶことができない州の答えしか知りません。どの2つの連続したスポットや撮影したスポットの総数は今4k+2

されていない場合はどの2つの連続したスポットや撮影したスポットの総数は4k

Lされていない場合この場合、答えは

• Wです後方に働く。プレーヤー1がWに移動できるボードポジションがある場合はWとマークし、プレーヤー2がLに移動できるボードポジションがある場合はLとマークします。繰り返しますが、これは直ちにマークされたすべてのポジションを取得することはありませんが、この意志を反復します。反復部分は4kスポットと満たされた2つの連続したスポットがある場合は、位置を与えるW
• Lをマークし4k+2スポットと満たされた2つの連続したスポットがある場合は、位置を与えるこの
  • Wです

    ---

    例L

  マーク：ボード0123を考えてみましょう。

  X X X X X X (L - terminal) 
  

  プレーヤーの一つを移動する：

  X X _ X X _ (W - terminal) 
  _ X X _ X X (W - terminal) 
  _ X X X X _ (W - terminal) 
  X X X X _ _ (L - must move to X X X X X X) 
  _ _ X X X X (L - must move to X X X X X X) 
  

  プレーヤー二つを移動するには：

  X X _ _ _ _ (L - can move to X X X X _ _) 
  _ X X _ _ _ (W - must move to _ X X _ X X or _ X X X X _) 
  _ _ X X _ _ (L - can move to X X X X _ _) 
  _ _ _ X X _ (W - must move to X X _ X X _ or _ X X X X _) 
  _ _ _ _ X X (L - can move to X X _ _ X X) 
  

  プレーヤーワンに移動するために、後方

  プレーヤー二つの作業最終状態から評価移動：

  _ _ _ _ _ _ (W - can move to _ X X _ _ _) 
  

  ---

  各位置はWまたはLとして評価されるように、あなたは再帰的にこれをプログラムすることができます。 Pの各ボード位置を長さnのバイナリベクトルで表します。ここで、1は撮影スポット、0はオープ​​ンスポットを示します。ここでdoesPlayerOneWinのための擬似コードです：

  // STORE NUMBER OF ONES 
  int m = 0; 
  for (int i=0; i<n; ++i) 
      m += P[i]; 
  // LOOK FOR LEGAL MOVES 
  bool canMove = false; 
  for (int i=0; i<n-1; ++i) 
      int[] newP = P; 
      if (P[i]+P[i+1] == 0) { 
       canMove = true; 
       newP[i] = 1; 
       newP[i+1] = 1; 
       // PLAYER ONE CAN MOVE TO WIN 
       if (m % 4 == 0 && doesPlayerOneWin(newP)) 
        return true; 
       // PLAYER TWO CAN MOVE TO WIN 
       if (m % 4 == 2 && !doesPlayerOneWin(newP)) 
        return false; 
      } 
  } 
  // IF NO LEGAL MOVES, PLAYER TO MOVE WINS 
  if (!canMove && m % 4 == 0) 
      return true; 
  else if (!canMove && m % 4 == 2) 
      return false; 
  // OTHERWISE IF LOOP RUNS, PLAYER TO MOVE LOSES 
  if (m % 4 == 0) 
      return false; 
  else 
      return true; 
  

Answer 2

Assuming optimal choicesは実際には最適startegyです。

プレーヤーの移動を「選択」する一般的な方法は、min-max algorithmです。 [実際には、がKasparovに勝つために使用したアルゴリズムです]。 Min-Maxは、各プレイヤーのために最適な動きを選択して、その動きを選択します。

min-maxアルゴリズムは通常ヒューリスティックで、ゲームの各状態を評価しますが、あなたの場合は、最適な動きとブルートフォースの解を探しているので、min-maxを使用する必要がありますゲームが勝者/敗者と締結されるまでの各反復は、ボードの唯一の評価です。

この方法を使用すると、開始状態の値を使用して勝つプレイヤーを判断できます。これは、「私」とみなしたプレーヤーが勝者か敗者かを示します。

この特定のケースでは、ボードが最終状態のみで評価される場合、min-maxは@ PengOneのソリューションに非常に似ています。

Answer 3

このようなゲームを解決する理論があります。

あなたのゲームは公平なゲームです。両方のプレイヤーがすべてのポジションから同じ動きをします。チェスは公平ではありません。なぜなら白は白い数字しかコントロールできないからです。プレイヤーが移動していないときにゲームが終了し、失われます。すべてのゲームが一定時間内に終了するとします。

PengOneが示唆しているLとWのように、ポジションを分析してラベル付けすることができます。失うポジションは、可能なすべての移動が勝ちポジションになり、勝ちポジションが少なくとも1つのポジションになるポジションです失う位置に。再帰的ではあるが、明確なラベル付け。プレイヤーが移動していない場合、すべての連続したポジションが勝っているので（vacuous truth）、これは失われたポジションとして分類されます。

あなたに役立つもう少し情報を計算することができます。 mex（{0,1,5}）= 2、mex（{1,2,3}）= 0のように、mex（A）をAでない最小でない非負整数と呼んでください。これで、すべてのラベルにmexでラベルを貼り付けることができます。これは再帰的かつ明確なラベル付けでもあります。値が0の場合、位置は失われています。この分類の下では、位置が0のラベル失うことはできますが、数字1,2、とポジションを獲得したのきめの細かい分類を持っている....

これらの数字は、次の2つのゲームの和の値を計算することができます。 2つのゲームを個別に再生することで追加できます。移動中は、最初のゲームでも、2番目のゲームでもプレイできます。あなたのゲーム___X__X__のポジションは、実際には3つのゲームの合計である___,__,__です。

スプレイグ・グランディの定理。 a_1、a_2、...、a_NのN個のゲームの合計は、a_1 xor a_2 xor ... a_Nと評価されます。したがって、Nのゲームの合計は0

にそれらの値のXOR場合に限っ失っているあなたの最初の位置はXで区切っKの独立したゲームの合計、です。それぞれの空のストリップのSprague-Grundyの値を見つける必要があります。それらをxorし、結果が0なら戻ります。最初の50を計算しようとすると、値を計算するヒントが得られるかもしれません。

私は仕事の代替として、このサイトを使って好きではないので、私はここで終了します。あなたが立ち往生している場合は、あなたが完了することができることを願って、質問してください。何が価値があるために

Answer 4

は、ここではPythonで書かれたブルートフォースソルバーです。楽しい！あなたはN> 2でそれを実行して、ターンごとに大きなスパンを置くこともできます。失っているプレーヤーは一番左の有効な移動を再生するだけであることに注意してください。

まず、出力。私は異なるボードサイズ（ここでは2〜16）でゲームを走らせました。ここで

Size = 2 
.. 
11 
Player 1 Wins! 

Size = 3 
... 
11. 
Player 1 Wins! 

Size = 4 
.... 
.11. 
Player 1 Wins! 

Size = 5 
..... 
11... 
1122. 
Player 2 Wins! 

Size = 6 
...... 
..11.. 
2211.. 
221111 
Player 1 Wins! 

Size = 7 
....... 
11..... 
1122... 
112211. 
Player 1 Wins! 

Size = 8 
........ 
.11..... 
.1122... 
.112211. 
Player 1 Wins! 

Size = 9 
......... 
11....... 
1122..... 
112211... 
11221122. 
Player 2 Wins! 

Size = 10 
.......... 
....11.... 
22..11.... 
22..1111.. 
22221111.. 
2222111111 
Player 1 Wins! 

Size = 11 
........... 
11......... 
1122....... 
112211..... 
11221122... 
1122112211. 
Player 1 Wins! 

Size = 12 
............ 
.11......... 
.1122....... 
.112211..... 
.11221122... 
.1122112211. 
Player 1 Wins! 

Size = 13 
............. 
...11........ 
22.11........ 
22.11.11..... 
22.11.1122... 
22.11.112211. 
Player 1 Wins! 

Size = 14 
.............. 
......11...... 
22....11...... 
22....1111.... 
2222..1111.... 
2222..111111.. 
222222111111.. 
22222211111111 
Player 1 Wins! 

Size = 15 
............... 
11............. 
11...22........ 
1111.22........ 
1111.22.22..... 
1111.22.2211... 
1111.22.221122. 
Player 2 Wins! 

Size = 16 
................ 
.....11......... 
22...11......... 
2211.11......... 
2211.1122....... 
2211.112211..... 
2211.11221122... 
2211.1122112211. 
Player 1 Wins! 

はコードです：

N = 2 # number of pieces placed per turn 

CACHE = {} 

def compute_moves(board): 
    gaps = [0] * len(board) 
    previous = 0 
    for i in range(len(board) - 1, -1, -1): 
     if board[i]: 
      previous = 0 
      gaps[i] = 0 
     else: 
      previous += 1 
      gaps[i] = previous 
    return [i for i, gap in enumerate(gaps) if gap >= N] 

def do_move(board, index, player): 
    for i in range(N): 
     board[index + i] = player 

def undo_move(board, index): 
    for i in range(N): 
     board[index + i] = 0 

def search(board): 
    key = tuple(board) 
    if key in CACHE: 
     return CACHE[key] 
    moves = compute_moves(board) 
    for move in moves: 
     do_move(board, move, 1) 
     a, _ = search(board) 
     undo_move(board, move) 
     if not a: 
      result = (True, move) 
      break 
    else: 
     result = (False, moves[0] if moves else None) 
    CACHE[key] = result 
    return result 

def play(board): 
    player = 0 
    while True: 
     print ''.join(str(x or '.') for x in board) 
     _, index = search(board) 
     if index is None: 
      break 
     do_move(board, index, player + 1) 
     player = int(not player) 
    print 'Player %d Wins!' % (int(not player) + 1) 

for size in range(2, 17): 
    print 'Size = %d' % size 
    board = [0] * size 
    play(board) 
    print