利用 minmax 搜尋樹撰寫的井字遊戲

minmax 搜尋樹

這是最規矩的寫法, 當然也是最容易延伸到別種問題的寫法。

基本上就是考慮所有的可能性。

你知道第一子下下去的時候有九種可能性, 下了以後對方有八種可能性, 也就是已經有 9*8=72 種可能性了, 再下去我們可以在下一子, 這一子的可能性有七種, 於是我們有 9*8*7=504 種可能性了, 假設只考慮到這麼多為止, 我們很容易可以把這些可能性用一個樹狀結構畫出來, 再定義每一個分支的 "好與壞", 由這 504 種可能中找到對我們最有利的下法來下。

那麼如何定義每一個分支路徑的好壞呢?

這就是所謂的 Min Max 的方法了: 首先我們假設每下一子都有所謂的代價 (Cost), 下得好的話代價很低, 甚至是負的, 下得不好的話代價很高, 也許遊戲就已經結束了。 所以在第一步的時候我們當然要在九種可能中找到代價最低的, 就下這一子, 當然這也就成了這一子的代價了, 但是到了第二步的時候就不一樣了, 第二步是對手下的, 你要假設對手很厲害, 他會讓他自己的代價很低, 相對的也就是讓你的代價越高越好, 所以你會發現你的對手會在八種可能性中找代價最高的來下, 到了第三子又是你來下了, 這時你會從七種可能性中找到代價最小的來下, 如此一層用 minimize 來決定代價, 一層用 maximize 來決定代價, 反覆下去就是所謂的 Min Max 方法, 或是人工智慧中的 AND OR 搜尋樹了。

上面這個方法還有一點點的問題, 就是到底代價 (Cost) 要如何估算呢? 當然對於任一個狀態而言, 估算的方式很多種, 例如: 你可以嘗試著計算在目前狀況下, 自己剩下可以贏的路線有幾種, 對手可以贏的路線有幾種, 拿後面的減掉前面的來估計說目前的狀況對你的代價為何?

範例執行程式:

這個程式就是利用上面的方法寫出來的, 所謂的 Level 就是預先想幾子, Level=1 就是只考慮這一子, 連對手下的下一子都不考慮, 用滑鼠玩玩看吧!

延伸問題:

這種設計程式的方法理論上可以延伸到
  1. 五子棋
  2. 西洋棋
  3. 跳棋...

程式設計課程 首頁

製作日期: 09/13/2008 by 丁培毅 (Pei-yih Ting)
E-mail: pyting@mail.ntou.edu.tw TEL: 02 24622192x6615
海洋大學 電機資訊學院 資訊工程學系 Lagoon