生成所有獨特的井字板的列表

Question

我想生成一個文本文件，其中包含所有19,683 Tic-Tac-Toe板佈局的0 =空白，1 = X和2 = 0的結構。不幸的是，數學這不是我的強項，我似乎無法在任何地方找到這方面的例子。

這不是爲了我向你保證的功課。我打算通過Minimax計算器運行這些數據，以生成包含代表基於電路板設置的最佳移動的RGB值的圖像。我正在爲不支持功能的平臺開發Tic-Tac-Toe（它是事件驅動的），所以我會將棋盤轉換爲我的遊戲中的一個數字，然後在圖像中查找像素的RGB，以指示最佳移動是。這是一個厚臉皮的解決方法，但不需要比145x145像素圖像更多的RAM（145x145 = 21,025，因此每個像素代表基於板有效推薦的移動）。這也意味着我不必咀嚼CPU時間，這是另一個加號。

Answer 1

既然你想要電路板佈局，只有少數（19683）。

你可以蠻力生成所有這些。每個盒子只有3種可能性。有9個盒子，只是貫穿所有的盒子。

編輯：

int c = 0; 
while (c < 262144){ 
    bool valid = (c & 3) < 3; 
    valid &= ((c >> 2) & 3) < 3; 
    valid &= ((c >> 4) & 3) < 3; 
    valid &= ((c >> 6) & 3) < 3; 
    valid &= ((c >> 8) & 3) < 3; 
    valid &= ((c >> 10) & 3) < 3; 
    valid &= ((c >> 12) & 3) < 3; 
    valid &= ((c >> 14) & 3) < 3; 
    valid &= ((c >> 16) & 3) < 3; 

    if (valid){ 
     int i = c; 
     int j = 0; 
     while (j < 9){ 
      cout << (i & 3) << " "; 
      i >>= 2; 
      j++; 
     } 
     cout << endl; 
    } 

    c++; 
} 

這將打印出所有19683的電路板佈局。我不確定你想要什麼格式，但從輸出中提取它應該相當容易。

Answer 2

你可以簡單地通過暴力破解。每個方格爲0,1或2，使...：

for (int i1 = 0; i1 <= 2; i++) { 
    for (int i2 = 0; i2 <= 2; i++) { 
     // ... 
     // lot's of nested for loops 
     // ... 
    } 
} 

或者，如果你不能與困擾;），那麼你可以爲它編寫一個遞歸函數：

int square[9]; 
void place(int square_num) { 
    if (square_num == 9) { 
     output the current configuration 
    } 

    for (int i = 0; i <= 2; i++) { 
     square[square_num] = i; 
     place(square_num+1); 
    } 
} 

然後只是做：將出現

place(0); 

和魔法。

順便說一句，這是在C++中。

Answer 3

有9個職位和3個字母（X，O，空）的字母表。可能組合的總數是3^9 = 19683.

for(int i = 0; i < 19683; ++i) 
{ 
    int c = i; 
    for (int j = 0; j < 9; ++j) 
    { 
     cout << (c % 3) << " "; 
     c /= 3; 
    } 

    cout << endl; 
} 

Answer 4

我的Tic Tac Toe實現的最小值生成一個包含5477個節點的樹。每個節點包含一個井字板狀態，並滿足下列條件：

• 董事會狀態是每個玩家必須輪流把XS和O的井字規則有效。即有沒有像板的位置：

  XXX
  XXX
  XXO

• 包含有考慮最終遊戲狀態按井字規則板狀態樹的所有葉子（玩家1次獲勝，球員2勝或平局）。即沒有樹一樣的分支：

  XOX
  OXO
  X
  |
  |
  XOX
  OXO < - 在具有該節點，因爲它的父具有端遊戲位置沒有點（X韓元）
  XO

• 給定樹節點可以具有多個父母（多個樹中的節點可以有同一個孩子）。因爲可以通過多個不同的移動序列獲得給定的棋盤狀態，當樹節點正在被創建時，如果已經有包含我將要（重新）生成的棋盤狀態的節點，則我重用（重新連接）該現有節點。這樣，當我從下到上評分樹節點時（按照Minimax理論），我不必爲樹分支的某個子集多次計算相同分數（如果我不重複使用，這將是相同的現有節點）。

I've also found a book which mentions the 5477 unique, distinct, valid Tic Tac Toe board states.：

井字棋是具有5477個不包括空位置

Answer 5

生成所有可能的遊戲板（深度優先搜索效果最好）和不重複的有效狀態在旋轉和鏡像下產生765個棋盤。 626是中場比賽，91場比賽X贏了，44場比賽O贏了，3場比賽抽籤。

如果你只是在最佳的舉動intresetd你可以簡單地使用 https://xkcd.com/832/作爲參考。製作一個不錯的海報。

但井字遊戲中的所有樂趣都在實現它。所以我把它留給讀者。只是一些使用技巧：

1. 董事會上的每瓦有3個狀態，所以你可以在基地3.董事會編碼爲數字對於比較簡單的數學我用基地4（每瓦2位，所以我只需要轉移）。然後我有一個散列函數，在所有可能的旋轉和鏡像（8種情況）下爲一塊電路板生成該數字，並返回最小值。通過這個我可以查找我是否已經玩過該板。

2. 從一塊空板開始，在每個可能的位置放置一個標記，檢查棋盤是否已經被玩過，標記它是否玩過，檢查遊戲是否結束並計數棋盤，否則緩衝交替玩家。

3. 第一個X只能設置在3個位置（考慮旋轉和鏡像），後面的所有移動最多隻能選擇8個。而不是編碼要播放的絕對磁貼，您只能計算空的磁貼並將其編碼爲3位。

4. 使用上述散列函數可以使我們獲得626個需要移動的板（您只需要反轉旋轉/鏡像即可實現數據的真實移動）。可能沒有更大的相對素數，因此每塊電路板都可以在沒有碰撞的情況下適合散列表。可以說這個數字是696（我知道，不是相對的素數）。在每塊電路板上3位，只需要261字節的數據來存儲每個可能遊戲的最佳移動。

5. 由於您演奏完美，可到達的電路板數量再次減少。構建一個用於播放X的數據集和一個用於播放O的數據集，然後您可以再次下降。

6. 想要使它更小？只需按照以下幾條基本規則進行編程：如果空閒，則第一個O應位於中間。用2「我的顏色」連續完成這一行。用一行中的2「其他顏色」阻擋該行等等。維基百科列出了8條規則，但我認爲我這樣做的時候少了一些。

7. 一個完美的井字遊戲對手很無聊。你永遠不會贏。爲什麼不讓遊戲從失敗中學習？跟蹤所有626板及其可能的移動。當移動導致損失時，從棋盤上移除棋子。如果董事會沒有更多的動作，從所有導致這個動作的棋盤上移除，導致它的動作（如果刪除了最後一步動作，則遞歸）。你的遊戲永遠不會以同樣的方式鬆散兩次。相似的移動導致一場勝利，你可以從可能的移動列表中移除對手，如果沒有剩下的話，你將前一步移動標記爲肯定勝出。這樣，如果你可以強制贏得勝利，你將永遠強制它從現在開始。玩X可以讓它鬆散91種方式？玩O你能把它全部放鬆嗎？

Answer 6

像早期的解決方案，但更易於閱讀和Python。

for i in range(3**9): 
    c = i 
    for j in range(9): 
     if j % 3 == 0: 
      print("") 
     print(str(c % 3) + " ", end='') 
     c //= 3 
    print("")