雙人五子棋

【Scratch 專案】 改編 雙人五子棋

分析

跟著程式執行順序看(trace)一次程式，會發現其實程式並不難，流程圖很容易就畫出來了。傑夫老師改編專案基本上不改流程，最主要修改了資料結構與『判斷算法』函式。

這個專案有個厲害的地方：程式中的『廣播訊息(消息)』，這裡的消息是個字串變數，是個很高明的做法。

再來就是資料結構，原專案用了三個清單：棋子的 x 座標、棋子的 y 座標、還有棋盤上的棋子。棋盤最左上角座標為 (0,0)，最右下角座標為 (12,12)。而三個清單的第 n 個項目，就是記錄第 n 個落下的棋子的 x, y 座標以及顏色，換句話說，這個清單順序不能亂，亂了就對不上了。

順便說說空間佔用，當 13x13 個格子都佔滿了，使用了 169x3 個空間，有點多。

最麻煩的是判斷勝負，每落一顆子就要判斷一次。因為這份資料結構的設計，只能從落子順序第一個棋子的資料，一一去清單中找看看四個方向是否有連線。如果一直沒有找到，會找到落子順序中最後一個，而且不會因為發現沒法連線就break掉，推算一下時間複雜度：

n*n*4*4 = O(n^2)

判斷連線

若這盤棋的黑棋落子順序如下圖紅字，則資料如右邊表格所示：

當第 9 顆子(黑)落下時，會執行勝負判斷，我們來看往右找的『判斷算法 1,2,3,4,0,0,0,0』怎麼執行的：

「計數器2」代表的是開始找的第一顆旗子，「計數器3」就從頭開始一個一個找它右邊第一個位置 (x1=1) 有沒有黑色棋子，如果找到了就把「已連接的棋子」改變 1，再開始從頭找右邊第二個位置 (x2=2) 有沒有黑色棋子。以此方式找 4 次，以這樣的資料，當「計數器2」＝1時到第 4 次 (x4=4) 時沒有找到，暫時沒有人獲勝。

「計數器2」 繼續改變直到 9，也就是第 9 顆棋子當開始棋子。「計數器3」依然是從 1 開始找右邊第一個位置 (x1=1) 找到；「計數器3」又從 1 開始找右邊第一個位置 (x2=2)；一直到第4次 (x4=4) 都有找到，「已連接的棋子」變數為 5，分出勝負。

仔細想想，就能知道不用往左邊找，也不用往上、往左上、往右上找，因為每個棋子都會被當成開始的那一個 (計數器2)，只要往4個方向就可以了。

改編

我想作者應該是不想把程式搞的複雜才這樣設計資料結構的，畢竟是書中範例程式太複雜不好說明。

傑夫老師的改編就只開一個大小 169 的清單，利用2維<->1維轉換記錄每個位置棋子顏色，再以落子的位置往8個方向各比(最多)4次，就能判斷是否有連線了。這樣連線判斷就可以做得很有效率了，這樣也節省了空間。

清單2維<->1維轉換在 Scratch 中是個很常用的技巧，唯獨行、列要像其他程式語言一樣從 0 開始轉換才會比較方便，這點原專案已經有做到，讓傑夫老師少改了很多程式。請各位可以自己試試看，如果有問題歡迎來問傑夫老師喔，Bye now~