如何在井字遊戲中確定遊戲結束？

Question

我正在開發井字棋遊戲，我需要算法來檢查遊戲何時結束（以及誰贏了）。 在3x3遊戲中，我會檢查每個可能的贏局面（有8個能力）。但是在7x7中（需要連續4個符號或者對角線）是很多可能的贏球模式。

Answer 1

雖然一個非常基本的方法是從每個單元格看所有方向的運行，但是這裏有一種方法只能在單個「行」中檢查一次單元。 A「線」是一個行，列，或對角線，可以有可能獲得，就象是在拉斯維加斯投幣機:)

1. 對於每一「行」，移動到開始該「線」和;
2. 集計數器爲0。
3. 對於在「線」的每個小區（遍歷順序的行）：
   • 如果單元P1和計數器是> = 0，添加一個對抗
     • 如果計數器= 4，則P1獲勝。
   • 如果單元P1和計數器是否定的，計數器設置爲0
   • 如果單元P2和計數器是< = 0，減一計數器
     • 如果計數器= -4然後P2勝
   • 如果單元P2和計數器是正數，計數器設置爲0

重要編輯：如果單元不包含P1或P2，請將計數器重置爲0（doh！）。我省略了這個微不足道的步驟。否則「11-11」將被視爲勝利。給定起始點和每次迭代的行/列偏移（例如從（0,0）開始並且對於從NW到SE的最長對角線提前（1,1）），可以遍歷「線」。當然，長度小於4的對角線可以避免被完全檢查。

快樂編碼。

Answer 2

儘管所有的位置循環。對於每個位置，請檢查右下角和右下角的四個字段（始終包含字段本身）。進行適當的檢查以避免在檢查不存在的字段時炸燬應用程序。

Answer 3

簡單。使4 for循環，所有行，列，增加對角線，減少對角線。 在每個中，測試是否有連續4個部分。

Answer 4

如果您對每個玩家使用bitboard，則可以使用位移操作來測試棋盤獲勝。

的棋盤將具有以下結構：

6 14 22 30 38 46 54 
5 13 21 29 37 45 53 
4 12 20 28 36 44 52 
3 11 19 27 35 43 51 
2 10 18 26 34 42 50 
1 9 17 25 33 41 49 
0 8 16 24 32 40 48 

如果玩家佔據了遊戲板的位置，則相關聯的位將是1否則0（注意，位7，圖15，23，.. 。是0）。要檢查的玩家獲勝板，你可以使用以下功能：

bool haswon(int64_t board) 
{ 
    int64_t y = board & (board >> 7); 
    if (y & (y >> 2 * 7)) // check \ diagonal 
     return true; 
    y = board & (board >> 8); 
    if (y & (y >> 2 * 8)) // check horizontal - 
     return true; 
    y = board & (board >> 9); 
    if (y & (y >> 2 * 9)) // check/diagonal 
     return true; 
    y = board & (board >> 1); 
    if (y & (y >> 2))  // check vertical | 
     return true; 
    return false; 
} 

有了一個例子的幫助，我會盡量解釋：一個球員的下面棋盤包括垂直旁邊，斜贏得了獲勝組合第一行。

0101010 
1110111 
0111011 
1101110 
0001000 
1010101 
0011110 ... four occupied positions --> winning board 

爲水平檢驗的步驟是：

1. y = board & (board >> 8)

   0101010 0010101 0000000 
   1110111 0111011 0110011 
   0111011 0011101 0011001 
   1101110 & 0110111 = 0100110 
   0001000 0000100 0000000 
   1010101 0101010 0000000 
   0011110 0001111 0001110

2. y & (y >> 2 * 8)

   0000000 0000000 0000000 
   0110011 0001100 0000000 
   0011001 0000110 0000000 
   0100110 & 0001001 = 0000000 
   0000000 0000000 0000000 
   0000000 0000000 0000000 
   0001110 0000011 0000010

水平檢查結果在一個板具有一個位設置，這意味着板包括一個勝利和函數返回true。

我已經使用similar function檢查connect four比賽獲勝。我在John Tromp的The Fhourstones Benchmark來源中看到了這個迷人的功能。