井字OX遊戲

【Scratch 專案】 井字OX遊戲 TicTacToe

緣起

這個遊戲從小玩到大，可是始終沒有實作過。受了一些啟發（之後有機會再說是什麼啟發），就想趁著放假來把它完成。之前已經做了兩人版，再繼續改下去就不是什麼難事。然而，前面提到的「啟發」似乎沒有什麼幫助，又正好在 Youtube 找到了下面這段影片，看完之後對「極小極大搜尋演算法 (minmax algorithm) 」忽然頓悟，於是就開始著手把影片中的程式改成 Scratch 版本。

動手

之前做的兩人版的確很有幫助，因為最重要的部分是判斷哪一邊贏或是平手，這段程式寫好了也驗證過，就直接拿來用。如影片所做的，先把電腦這邊改為隨機找空格下，再開始把電腦這邊改為 minmax 演算法，所以隨機下的程式也還保留著。

minmax algorithm 的 pseudo code 如下：

沒錯，要用到遞迴，這個以前覺得沒什麼用，現在才發現解任何問題都要用到的「遞迴」。在 Scratch 中做遞迴不是什麼難事，還陪學生練習了很多次，但是在 Scratch 中的函式積木與一般程式語言的函式有兩點很大的不同，一是 Scratch 的函式不能回傳值、二是 Scratch 函式中的變數不是區域變數（Scratch 的區域變數是跟著角色分身）。第一個問題還好解決，適時的改變某個變數就能解決，但第二個問題就必需自己建立堆疊 (stack)，這個問題在之前畫「科赫雪花 (Koch snowflake)」時就已做過，對傑夫老師來說一點也不難。〈抱歉，好像不是這個專案，我再找找堆疊用在哪裡〉

再來，pseudo code 中有個 +∞ 與 -∞（正無限大與負無限大），這個有些人可能在 Scratch 中看過，但不知道怎麼弄出來的。其實很簡單，就是 1/0 與 -1/0，不用去打字也不需要煩惱該用什麼值來代替。

除錯

程式寫好了，當然就是開始 debug，第一個 bug 當然就是電腦總是算錯。如果玩家第一手下在位置 1 (左上)，電腦應該下在位置 5 (中央)，但總算出位置 7, 8, 9 三個位置會贏(回傳值 1)。這問題的確很難解，老師查了半天，直覺是剛剛說的回傳值的問題，但就是想不通。再仔細比對影片所附的程式，終於領悟了，少了一行把最小(或最大)值傳回的程式。剛剛還說回傳值不是難點，馬上就打臉了。

改好了之後，當然會有 bug！仔細看看算出來的值，從來沒有 0 (和局)。難到是檢查勝負的函式錯了？仔細檢查之後，果然有錯，而且錯的地方有兩個，其中一個低級錯誤就不說了，另一個是沒考慮到連成一線的是三個空格，這樣造成了判斷沒有結果，回傳值是 null (空值)。

改完了判斷函式之後，還是有 bug！因為時間晚了，傑夫老師就到被窩裡頭去想。果然，半夢半醒之間，就有靈感出現，pseudo code 的函式有個參數 depth 老師偷懶省略掉了，因為有個變數 hands 會紀錄下到第幾手，但是在 minmax 函式中並沒有改變 hands 這個值，也就是說，判斷函式不知道下到最後一手，就不會有和局 0 的結果出現。

隔天早上，解決了這個問題，電腦終於下到中間格子了，玩家與電腦可以繼續玩下去。可是就在電腦的最後一手，電腦竟然下錯讓玩家贏，這讓傑夫老師開始懷疑起自己的人生(誤)程式。minmax 函式已經沒什麼好懷疑的了，問題還是在於判斷函式，因為最後兩個空格，電腦算出的值都是 -1 (輸)，但那是不可能的，因為位置 7 (左下) 才會輸、9 (右下) 會是和。幸好是最後一步，stack 沒內容，只需要記住棋盤內容與 hands 變數就可以容易複製出資料，棋盤內容存在一個清單之中，匯出匯入就好了。

Debug 了許久，繼續懷疑人生的當下，忽然發現 hands 這個變數怪怪的，原來雙人版中，是先判斷輸贏後再把 hands 加 1，但在剛剛的修改變成了先加 1 再判斷輸贏，那麼判斷最後一手的 hands 變數值就不是 9 了，而應該是 10。

終於

終於解決了，找人玩了一下，如果玩家故意下錯電腦會贏，這就對了。

後記

1. 程式架構可以寫的更好，因為算是移植影片中的程式，而影片作者也提過程式可以寫的更好。

2. 之前寫的判斷輸贏程式就有 bug，多次掉入自己挖的坑！

3. 設定是玩家 O 先下，電腦 X 後下，要再修改成誰先下都可以。

4. UI 操作要做防呆，電腦在計算的時候，滑鼠亂點是可以下 X 的。暫時用貓咪說出下每一格的計算值，表示電腦在做計算。

5. 堆疊 (stack) 的部分，push/pop 原本是對清單中第一項操作，程式比較簡單一些些，而且清單第一項顯示在最上面，符合一般堆疊說明的圖示。但因為要 debug，改成對清單最後一項操作，這樣在跑的過程中，比較容易看出現在運算到哪，也比較容易看出是否有異狀。

最後，如果有人可以用其他方法解決遞迴的兩個問題，歡迎來跟傑夫老師說喔～ Bye now.