iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 8
0

勝負判斷分析

3x3map

窮舉法

在 3x3 的圈圈叉叉遊戲中,獲勝的組合只有 8 種,以上圖為例,每個格子裡面的數字代表 block id,我們窮舉出所有獲勝連線:

// 橫向
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]

// 縱向
[0, 3, 6]
[1, 4, 7]
[2, 5, 8]

// 右斜
[2, 4, 6]

// 左斜
[0, 4, 8]

上述是 3x 3的棋盤,3子連成一條線為獲勝條件的所有獲勝可能。所以判斷獲勝最簡單的方式,就是我們去檢查,上面這 8 種組合當中,有哪一種或哪幾種組合是全部同一色棋的,就是獲勝者,且在規則之下,絕對不會有同時兩者獲勝的狀況發生。

但是,由於我們是伸縮自如的圈圈叉叉,不只棋盤大小會改變,獲勝條件也會改變,所以如果要窮舉所有的狀況,可能會做到天荒地老。

適應各種條件之勝負判斷

為了要讓我們的程式可以在各種條件組合之下也能正確的判斷勝負,我們必須要找到規則才行。

解決的方法有很多種,我相信我的方法應該不會是最好的方法,但是是可行的方法,如果有更好更簡單的解法,我也很想要知道,在這邊,我先分享我的方法來拋磚引玉。

首先,棋盤再怎麼放大縮小,他只有四種方向,橫的,直的,右斜,左斜,我在程式中命名為 row, column, forwardSlash( / ), backSlash( \ )。今天我們先來處理最直覺的 row 跟 column 兩個方向,其他兩個方向我們明天來討論。

橫向勝負判斷分析

以 row 方向來看,為了找到獲勝者,我想要用迴圈去掃描每一個row,只要有同一花色的棋子,連續出現大於等於獲勝條件( winnerCondition )的次數的話,就是我們找到一條連線了。在計算連續出現同一花色的過程當中,記得注意是同一 row 的連續,如果是換行的狀況,以下圖 block id 為例,[1, 2, 3] 或是 [2, 3, 5] 這樣的狀況,就不能稱為連成一條線,雖然這邊的提醒有點廢話,但是在寫程式的時候,一不注意會不小心忽略,所以還是在這邊講一下。
3x3-row

所以在程式裡面,我想要準備一個 array of array,命名為 arrs
如果是 3x3 棋盤的話,我的 arrs 如下:

arrs = [ 
    [0, 1, 2],
    [3, 4, 5],
    [6, 7, 8]
]

如果是如下圖的 4x4 棋盤的話:
4x4map

arrs如下:

arrs = [ 
    [0, 1, 2, 3], 
    [4, 5, 6, 7], 
    [8, 9, 10, 11], 
    [12, 13, 14, 15] 
]

依此類推,所以只要給定一個 gameScale,我們就可以產生出對應的 arrs

const _ = require('lodash');
const arrs = _.range(0, gameScale)
    .map((item) => {
        return _.range(item * gameScale, (item + 1) * gameScale);
    });

補充一下 lodash 的 range() 方法,第一個參數是起始值,第二個是結束值,第三個是遞增間隔,其中第三個參數是optional,沒有填的話,預設是1。
充分利用 lodash 讓你的程式碼更易讀及維護

縱向勝負判斷分析

column 方向的判斷跟 row 是一樣的,只是轉個方向。

3x3-column

如果是3x3的話,在 column 方向,我們也需要找到 arrs :

arrs = [
	[0, 3, 6],
	[1, 4, 7],
	[2, 5, 8]
]

4x4的話,其對應的 arrs 為:

arrs = [
	[0, 4, 8, 12],
	[1, 5, 9, 13],
	[2, 6, 10 ,14],
	[3, 7, 11, 15]
]

跟 row 一樣,只要給定一個 gameScale ,我們就可以產生出對應的 arrs

const _ = require('lodash');
const arrs = _.range(0, gameScale)
    .map((item) => {
        return _.range(item, item + gameScale * (gameScale - 1) + 1, gameScale);
    });

由於我們分別判斷 row, column, forwardSlash( / ), backSlash( \ ) 四種方向的勝負,最終的話,我們需要整合四個方向的結果,但是一開始為了化繁為簡,我們先單獨討論一個方向的勝負。

勝負判斷核心想法

首先來討論 row,我們剛剛已經得到以 row 的 arrs 了,如果要判斷勝負的話,我需要一個這樣的函數

const rowResult = getWinCase(blocks, arrs, winnerCondition);

三個輸入,一個輸出,其中輸入是我們熟悉的三個參數,輸出的話,我希望得到一個像下面這樣的物件

const rowResult = { 1: [], -1: [] };

其中,如前面定義所說,1代表圈圈,-1代表叉叉。
以 3x3 為例,如果我的圈圈在 id 為 0, 1, 2 的這三個格子連成一條線, rowResult 會類似下面的表示

// rowResult
{ 1: [ [0, 1, 2] ], -1: [] }

關於 getWinCase(),我的詳細完整做法,放在 github 跟大家分享交流,這邊簡單說明一下我的想法,其實說白了也是暴力法。

要知道,每一個 block 會有三種狀態,一是上面放了圈圈,二是上面放了叉叉,三是上面什麼都沒放。我會用兩層的巢狀迴圈來做檢查,在掃描同一 row 的時候,為了檢查出是否有花色連續的棋子,我分成下面的狀況來處理:

// getWinCase() 的處理邏輯

1. 當下的花色跟前一個花色`相同`
    a. 當下是狀態圈圈或是叉叉
        i. O -> O
        ii. X -> X
    b. 當下狀態是沒放
        i. null -> null
2. 當下的花色跟前一個花色`不同`
    a. 當下是狀態圈圈或是叉叉
        i. X -> O
        ii. O -> X
        iii. null -> O
        iv. null -> X
    b. 當下狀態是沒放
        i. O -> null
        ii. X -> null

如果我有發現是連續花色的棋子,我就會把他的 id 依序暫存起來,加入到一個陣列當中,等到我發現不連續了,或是換行了,我就來檢查剛剛暫存的那個 id 的陣列,長度是否大於等於獲勝條件 winnerConditon ,如果有,獲勝者就出爐了,找到一條線,如果沒有,就清空暫存的陣列,然後繼續往下檢查是否有連續花色的棋子,不斷的重複這個步驟,直到檢查完所有方格。
getWinCase() 的參考程式如下:
tic-tac-toe/src/containers/TicTacToe/utils.js

按照上面的方法,我們就可以做出 row 和 column 兩個方向的勝負判斷了!
明天,我們就要來挑戰,左斜和右斜方向的正負判斷!


上一篇
Day07 - Tic Tac Toe篇:勝負判斷事前準備
下一篇
Day09 - Tic Tac Toe篇:勝負判斷方法(2/2)
系列文
以經典小遊戲為主題之ReactJS應用練習30

尚未有邦友留言

立即登入留言