名稱：四子棋終結者 (中文版)
簡介：青衫（邱奕南）於2021年仿照Pascal Pons演算法所撰寫的四子棋遊戲。由於Pascal
      Pons的演算法可得知任一四子棋局面的勝負，因此使用本程式即可輕鬆打敗其他無法
      全面展開的四子棋遊戲。雖然程式本身也可下棋，但因為不敗，所以比較缺乏娛樂性，
      通常做為著棋參考使用。

保護：無
說明：（作者－青衫）

四子棋已證明為先手必勝，本遊戲採用的Pascal Pons演算法，可參考網址：

http://blog.gamesolver.org。

以下針對該演算法的教學網頁，做一些簡單的說明。

part1為一些簡介，不重要。part2提供了一些測試資料與其分數，可用來驗證程式的正確性
與效率性。如果想要自己寫程式，最好下載並使用這些測試資料。

part3開始進入主題。早期的棋類遊戲，多半採用Game Tree展開搜尋法，對於簡單的棋類遊
戲非常有效。較複雜的棋類遊戲，效果就很有限，例如虞希舜的象棋大師3將族，便是採用此
一方法。這個方法的核心主要有兩點，剛好對應part3和part4。

(part3)MinMax演算法：棋類是一來一往的遊戲，對敵人分數很高的著點，對我方便不利，
因此在展開搜尋時，在我方著子時要找最高分，在敵方著子時要找最低分，所以名字才叫MinMax。
而為了避免要判斷回傳最高分或最低分，通常會將對手方回傳的分數值轉負，如此各層只要
找最高分即可。

(part4)Alpha-Beta裁剪演算法：這是Game Tree搜尋法的精華所在，利用已知的分數，裁剪
掉已經不可能更好的著子變化。例如已經搜尋到下某個位置在第5手便會獲勝，那麼其他著子
只要超過5手還未分勝負的，便不用再往下展開了。這個演算法的重點，在於如何定義分數，
以及如何評估目前局面可能的最高分數，這關係到裁剪收斂的速度，也就是搜尋的效率。目
前關於四子棋的所有論文，都是採勝利點距離盤尾的剩餘手數做為分數，因此愈快獲勝，距
離盤尾就愈遠，分數也就愈高。評估目前局面可能的最高分數，基本上便是42-已著子數（7x6
的棋盤最多42子）。

標準Game Tree搜尋演算法的寫法為：

minmax(局面,目前局面已知的分數區間)
{
  if 局面已知為勝、負或和局 then 回傳分數
  評估目前局面可能的最高分，若不會更好便返回
  針對目前局面另一方可下的子，一一展開呼叫minmax取得分數轉負，同時更新已知的分數區間下限
  回傳前述展開後的最高分
}

(part5,part10)Game Tree搜尋的速度要快，就要儘早大幅限縮目前局面已知的分數區間，
以便濾除大部份無須展開的著點。對於四子棋而言，便是儘量先展開可能獲勝的著點。part5
說的是儘量從中間著點先展開，part10則是加上能形成【等四】情況時優先（請參考四玲瓏
的四子棋著手提示）。就這麼簡單的兩個方式，基本上就可以讓整個演算法，在可等待的時
間內，展開完四子棋某局面的分數計算。

(part7)同形局面暫存表：這是Alpha-Beta外，另一個很有效的裁剪法。因為四子棋同形反
覆的情況非常多，例如下了位置abcd四子的情況，那麼下列三種著子順序（即搜尋次序）都
會導致相同的局面：

adcb
cbad
cdab

以九子為例，下了九子的順序變化共有7^9=40353607，約4千萬種，實際上只有539062，大約
50萬個不同局面，只佔了1%多而已，其重複率非常之高。因此可以將已計算好的局面暫存起
來，如果遇到同形局面，便直接取用其回傳值，這樣就不用再往下展開搜尋。至此四子棋的
搜尋法，大抵已經成形，一個局面的分數計算已可在數分鐘內完成。後面的部份都只是一些
小改良而已，加速的幅度已不像前面的方法，動輒數十倍或數百倍以上之多。

(part8)分數區間二分搜尋法：因為我們要在可能的分數區間中（-42～42），找出目前局面
的實際分數。一種做法是採用二分搜尋法，取區間中間值，以只有1分區間的方式進行搜尋，
以得知實際分數是高還是低，然後限縮為一半的分數區間。反覆進行以得到最後的值。這種
方法對於複雜的局面會比較有幫助。

(part6)說明如何利用一個64位元長整數來表示一個四子棋的局面，可同時提升執行效率與記
憶體效率。

(part9)採用避免下會輸的棋，取代找會下贏的棋，如此可省下一層的搜尋，大抵可加快一倍。

(part11,part12)同形暫存表的小改良，只能加快一些些。

以該教學網頁寫出來的程式，評估第一著子後的局面分數，大約需要2～3分鐘，顯然不適合
用在即時互動的遊戲上。也就是說，原作者還有一些沒有寫出來的東西，必須試著將它補齊：

1.局面分數緩存表（Cache）

和同形局面暫存表類似，只不過同形局面暫存表是記錄在某個區間分數範圍內的回傳值，並
非實際分數，這裡記錄的是實際展開後所得的分數。也就是說，玩家在排某個著手變化時，
可能會來來回回的切換，此時已經展開計算過的著手局面，如果有記錄下來，便不用再次展
開了。這在人機互動上是個很有效的加速方法。

這裡要再多提的一點是，同形局面還包括了對稱同形。也就是說，第一手下第2欄，跟第一手
下第5欄，其結果是相同的，只是著子相互對稱而已。因此用來表示局面的key值，與經過對
稱計算後的key值，其實是一樣的，我們可以取其最小值來表示，如此緩存表可提升一倍的效
率。同形局面暫存表不建議這麼做，因為key值對稱計算需要多耗時，在大量展開計算時很可
觀，而多合併的一個同形局面遇到機率其實很低，加速的效果難以抵掉多出的耗時，總而言
之就是不划算。

key值的對稱計算程式寫法為（該網頁的程式裡沒有）：

typedef unsigned __int64 uint64;
inline uint64 Mirror(uint64 data)
{
  return ((data & 0x000000000000007f) << 42) | ((data & 0x0001fc0000000000) >> 42) |
          ((data & 0x0000000000003f80) << 28) | ((data & 0x000003f800000000) >> 28) |
          ((data & 0x00000000001fc000) << 14) | ((data & 0x00000007f0000000) >> 14) |
          (data & 0x000000000fe00000);
}

2.內定局面分數記錄表

前面有說過，第一次展開計算第一著子的局面分數，需要2～3分鐘，對於玩家而言，基本上
是無法忍受的等待時間。對於這部份，我們可以將一些較為耗時的局面分數事先計算出來，
並加以記錄。如此玩家在使用時，便可以直接取用這些已事先計算好的分數，而不用再展開
計算。

(1)前幾手的局面：由於需時較久的，大部份都是手數較少的局面，因此可將前n手的所有局
   面分數全部都先計算出來，並加以記錄。以取前10手為例，總共有330M個變化（3億多），
   產生出約120萬個局面，全部計算完費時約3天。從第11手開始，最慢大約可在4秒內計算
   完一個局面。但一次要計算7個著手局面，仍可能長達10幾秒以上，對於玩家而言，還是
   有點過慢。而再往下展開第11手以上，局面變化數愈來愈多，但用時降幅卻愈來愈小，很
   難達到真正快速的要求，因此我們必須另找其他方法才行。

(2)找展開節點數較多的局面：真正費時較久的，其實是展開節點數較多的局面，因此我們
   必須找出展開節點數較多的局面，計算其分數並記錄下來。這種方式可記錄其他計算較久
   的局面，而避免全面展開計算並記錄龐大的局面資料。於是我們便從第11手開始針對各種
   變化，進行第一次（無暫存資料）的展開計算，找出超過一定節點數以上的局面，並記錄
   其分數，同時再往下一層找出可能仍超過該節點數的子局面。依據實測的數據資料，0.1
   秒大約可以展開1M個節點，如此計算7手可在1秒內完成，是個比較適合的門檻值。展開後，
   共約有1315萬個局面，費時約9天。

最後實測結果，採用前述的局面分數記錄表，整個棋局分析的操作過程非常順暢，幾乎感覺
不到分數計算的停頓。至此，才算是實用的四子棋程式。

最後再說明一下，次著評估分數的校正。因為前面所謂的局面分數計算，是指下了棋後，該
局面的勝負分數，和次著的評估分數仍有一點小差異，特別是即將分出勝負時（實作後便會
知道）。以下為實際的次著評估分數流程：

對於要評估的7種著手
{
  if 該欄已滿 then 略過
  else if 下了後我方即勝 then 直接計算分數(正分)
  else if 下了後對手次著即勝 then 直接計算分數(負分)
  else if 下了後我方次著必勝 then 直接計算分數(正分)
  else 呼叫計算函數解出下該子後的分數並轉負
}