c博弈樹演算法詳解

① 博弈樹演算法是啥

就是用樹的節點來表示博弈過程中的每一步，比如在象棋里，雙方棋手獲得相同的棋盤信息。他們輪流走棋，目的就是將死對方，或者避免被將死。
由此，我們可以用一棵「博弈樹」（一棵n叉樹）來表示下棋的過程——樹中每一個結點代表棋盤上的一個局面，對每一個局面（結點）根據不同的走法又產生不同的局面（生出新的結點），如此不斷直到再無可選擇的走法，即到達葉子結點（棋局結束）。

② 系統框圖如下 java實現五子棋程序 可以實現人人對戰 人機對戰 簡單功能 悔棋 認輸

一、實驗題目

五子棋游戲。

二、問題分析

五子棋是雙人博弈棋類益智游戲，由圍棋演變而來，屬純策略型。棋盤通常15*15，即15行，15列，共225個交叉點，即棋子落點；棋子由黑白兩色組成，黑棋123顆，白棋122顆。游戲規則為黑先白後，誰先五子連成一條直線誰贏，其中直線可以是橫的、縱的、45度、135度。

本次Java編程我的目的是現實人機對戰，即游戲者一方是人，另一方計算機。這就要求程序不僅要具備五子棋的基本界面，還要編程指導計算機與人進行對弈。為了使程序盡可能智能，我採用了貪心策略、傳統搜索演算法、極大極小博弈樹演算法，對應游戲玩家的3個等級：簡單、中等、困難。

三、功能設計

我的程序基本功能是實現人機對弈五子棋。人和電腦交替下棋，誰先五子連成一條直線誰就贏。下面是我程序的功能模塊：

1.等級設置

核心功能是實現不同策略與演算法的對比運用，純貪心策略實現簡單等級對手，直接搜索演算法實現中等等級對手，極大極小博弈樹演算法實現困難等級對手。對應程序中的3選1單選按鈕。

2.悔棋功能

模擬棧機制實現人悔棋，不限步長的悔棋。對應程序中的悔棋按鈕。

3.棋面繪制

根據不同機計算機的屏幕解析度，繪制逼真的棋盤。

4.圖片引入

兩張古典的人物圖片，生動模擬對弈雙方。人物圖片旁的黑白棋缽圖片顯示黑白棋歸屬。

5.背景設置

支持用戶選擇背景，包括棋盤、棋盤邊框、窗口邊框，彰顯個性。

6.音樂播放

下棋時有棋子落地的聲音，一方勝利時有五子連成一片的聲音。同時在設置背景時相應的改變整個對弈過程中的背景音樂。

7.時間顯示

在棋盤正上方有一模擬文本框顯示當前棋局用時。

8.其他小功能

支持和棋、認輸、開啟新游戲、退出遊戲等操作。

四、數據結構與演算法設計

數據結構部分

1.當前棋局的存儲結構

我的五子棋程序選擇通常用到的15行*15列棋盤，可以開二維數組PositionFlag=newint[15][15]，PositionFlag[i][j]為0表示(i,j)點尚無棋，為1表示(i,j)點是人的棋子，為2表示(i,j)點是機器的棋子。之所以選擇二維數組，主要原因有兩點：

1.本程序需要頻繁隨機訪問15*15的交叉點，對應查詢該點狀態以及改變該點狀態，隨機訪問是數組的特點。

2.15*15=225開二維數組的內存需求相對現在內存為2G及以上的計算機完全可以接受，且數組實現簡單、操作方便。

基於以上兩點，盡管創建動態的順序表—鏈表可能可以節省少量內存（可以只存當前有棋的點，原數組對應位置為0的點可以不存），但選擇數組的優勢完全在上述兩點體現了出來。

2.實現悔棋操作的數據結構

由於每次悔棋只需回退當前幾步，後進先出原則，這正是棧這種典型數據結構的設計思想，於是我選擇棧。我自己先寫了用自定義數組模擬的棧，但由於是學Java語言且由於悔棋的存儲空間需要隨當前步數增大而增大（由於每局最多下225步，即最多要悔225步，所以自己開個225的數組完全可以避免存儲空間自增長的問題且內存完全可以接受，之所以不用自定義數組而用ArrayList類主要是為了嘗試Java中STL的用法），所有我最終改為用Java類庫中的ArrayList類。

確定用ArrayList類實現棧機制後就必須考慮每個ArrayList單元具體存儲什麼。剛開始我存儲的是當前的棋局，即整個局面，而每個局面對應一個二維數組，這樣是很佔用內存的。試想一下，在最壞情況下，225個ArrayList單元，每個單元存放一個15*15的二維數組，盡管225*15*15在Java的內存管理機制下不會爆棧，但也是極不劃算的。之所以說不劃算，是因為有更好的解決方案。由於每次悔棋只是在回退倒數一步，多步悔棋只需循環回退，所以可以只存儲當前棋局最後一步的下法，對應一個二維點，完全可以自定義一個二維坐標類chessOneStep。

演算法設計部分

Java語言是面向對象的語言。我在進行五子棋游戲編程是總共傳創建了11個自定義的類。在編寫程序的過程中，我有一個明顯的體驗就是面向對象編程就是一項有關對象設計和對象介面技術，很多關鍵的技術就是如何設計自定義的對象。

下面我先概括給出我的所有類的作用：

1.mainFrame類：主框架類，我應用程序的入口；

2.chessPositon類：主控類，這個類是我程序的核心類，負責控制雙方的下棋，以及調用其他的類完成當前棋局的顯示繪制；

3.chessPanel類：面板類，調用其他底層類完成當前棋局的顯示繪制；

4.chessBoard類：棋盤繪制類，負責棋盤的繪制；

5.chessImage類：文件類，包含各種資源（背景圖片、背景音樂）以及靜態全局變數（publicstaticType）；

6.chessButton類：組件類，定義各種組件，包括按鈕、單選按鈕、文本框等；

7.chessMusic類：音樂類，負責調用Java庫類完成背景音樂、下棋音樂、取勝音樂等的播放；

8.chessPiece類：棋局類，定義棋局二維數組數據結構並完成相關操作；

9.chessList類：棧類，完成悔棋等操作；

10.chessOneStep類：棋子類，定義每步坐標以及下在該處獲得的估價值；

11.myCompare類：排序類，完成chessOneStep類的自定義排序

詳細設計

1.mainFrame類

作為我的五子棋程序的主類，mainFrame類主要實例化相關的對象，如chessbutton,chessborad等，從而完成框架的創建。更重要的是實例化chessposition，這是本程序的核心類，控制游戲雙方行棋過程完成人機互動下棋，然後將MyChessPosition與滑鼠響應addMouseListener（）關聯起來。

2.chessMusic類

一個好的游戲必須給人一種身臨其境的感覺，而聲音是營造這種氛圍的重要因素。參照網上各游戲運行商的音樂配置，我選擇相關逼真的聲音。包括背景音樂、下棋棋子落到棋盤發出的聲音以及一方勝出的配樂。所有這些功能的實現，依賴於自定義的chessMusic類，採用AudioInputStream配合Clip的方式完成音樂播放的軟硬體工作，然後定義兩個介面chessmusic(StringName)和Stop(),前者完成播放功能，後者完成關閉當前音樂功能。因為音頻文件相對較大，而我的程序提供在不同背景樂之間切換的功能，所以在打開另一個音頻文件之前必須關閉前一個正在播放的音頻文件，防止出現溢出。

3.chessImage類

適當的動畫或圖片能給游戲玩家帶來美的體驗。所以我的五子棋程序界面在不失和諧的前提下引入了盡可能多的圖片，包括對弈雙方、棋缽等。圖片引入的具體工作通過語句importjavax.imageio.ImageIO完成。同時，由於圖片要在用到它的類中被訪問，為了避免頻繁調用函數，我直接將圖片相關聯的對象定義為publicstatic，表明是公用的、靜態的。進一步引申開去，我將程序中用到的靜態全局變數都定義在chessImage類中。具體如下：

publicstaticDatebegin;//每局開始時間

publicstaticDatecur;//每局結束時間

;//結束端點1

;//結束端點2

publicstaticbooleanIsGameOver;//是否只有一方獲勝

[][]={{255,227,132},{0,255,127},{218,165,32}};//背景顏色

publicstaticintColorOfWindows[][]={{60,179,113},{245,245,245},{122,122,122}};//背景顏色

publicstaticintWitchMatch;//背景搭配

;//背景音樂

publicstaticintCurrentStep;//記錄當前步數

publicstaticintRank;//設置難度等級

;//判斷是否認輸

publicstaticbooleanIsTie;//判斷是否認輸

publicstaticStringMessage;//輸出提示信息

publicstaticImageIconImage;//圖標

publicstaticImageblackBoard;//白棋盤

publicstaticImagewhiteBoard;//黑棋盤

publicstaticImageblackChess;//白棋棋子圖片

publicstaticImagewhiteChess;//白棋棋子圖片

publicstaticImageRightPlayer;//白棋棋罐圖片

publicstaticImageLeftPlayer;//白棋玩家頭像圖片

publicstaticStringpath="src/";//圖片的保存路徑

4.chessButton類

這個是程序的組件類。定義了各種功能鍵，完善程序功能，營造逼真的人機對戰游戲效果。分為3類：效果。。

(1)、按鈕組件

本程序有5個按鈕，支持和棋、認輸、新游戲、退出、悔棋等。認輸和和棋按鈕終止當前的棋局，給出相應的提示信息；退出按鈕調用系統System.exit(0)的函數正常返回；悔棋按鈕調用後面要介紹的chessList類實現悔棋；新游戲按鈕則刷新當前棋局准備下一輪，要將記錄當前棋局的二維數組全部置0，刷新當前棋局開始時間等。

(2)、單選按鈕組件

游戲界面支持設置個性化界面，包括背景顏色與背景音樂，跟重要的一點是設置難度（簡單、中等、困難）。單選按鈕只能多選一。背景顏色主要是存儲相關顏色搭配方案的RGB顏色，開2維數組，即對應RGB3原色數組的一維數組，然後通過改變WitchMatch全局變數的值來有用戶自己選擇顏色搭配，不同的顏色搭配對應不同的背景音樂表達一致的主題。難度設置主要是改變計算機的下棋演算法，不同難度通過Rank判斷進入不同的程序分支，實現不同智能等級的計算機下棋水平。

(3)、文本框

在不同的單選按鈕前添加相應的文本框，提示用戶可以實現的功能。同時我用顏色模擬出顯示當前棋局耗用時間的文本框。

不論按鈕還是單選按鈕都要關聯相應的消息，把相應功能的實現放在消息響應處理函數理。這些主要是實現Java庫提供的消息響應介面里的方法。

5.chessPiece類

主要完成當前棋面的存儲，存儲棋面的數據結構為二維數組int[][]PositionFlag；然後定義獲取、設置某點以及整個棋面的狀態的方法。

(1)、SetPositionFlag(intx,inty,intflag)//設置（x,y）處的狀態為flag

(2)、GetPositionFlag(intx,inty)//獲取（x,y）處的狀態

(3)、SetAllFlag(int[][]NewFlag)//設置當前整個棋面的狀態為NewFlag

(4)、GetAllFlag()//獲取當前整個棋面的狀態

(5)、DrawChessPiece(Graphicsg)//繪制當前局面的棋子

由於本類比較重要，所以附上了代碼，見源代碼1。

6.chessBoard類

功能為繪制棋盤線。由於圍棋的棋盤比較復雜，橫線、豎線較多，且為了使棋盤美觀，還要自定義窗口邊框、棋盤邊框、對弈雙方邊框等，對線寬、線型也有一定要求。有時要單像素線條，有時要多像素線條。對於多像素線條，我主要用了2種方法。

方法一：

在需要繪制多像素線條處首先繪制一條單像素線，然後根據線寬要求上下平移適當像素達到繪制多像素的目的。這樣的方法適合繪制水平線或豎直線，繪制其他斜率的線條容易造成走樣。在沒有想到比較好的反走樣編程思想後我選擇了調用Java庫中已經封裝好的函數。

方法二：

為了克服方法一繪制非水平或豎直線時造成的走樣，同時也為了更進一步學習Java語言，我猜想肯定會有類似OpenGL中設置線寬的畫刷，於是上網網路找到了相應的畫刷Stroke類。通過Java庫實現繪制不同線寬的直線，達到了反走樣效果。

7.chessOneStep類

這個類是為了配合chessList類實現悔棋以及在計算機下棋演算法實現返回有效狀態點而設計的。主要數據成員為

privateintx,y,weight；//其中x,y表示點坐標，weight表示將棋下到該點獲得的估價值。

主要方法如下：

(1)、GetX()//獲得當前對象的x坐標

(2)、GetY()//獲得當前對象的y坐標

(3)、GetWeight()//獲得當前對象的(x,y)處的估價值

8.chessList類

程序支持悔棋功能，為了實現悔棋，自定義了chessList類。這個類主要通過引入java.util.ArrayList和java.util.List實現集合的數據類型。然後自定義一些方法，如下：

（1）、AddStep(chessOneStepOneStep)//添加一步棋到List中

（2）、GetSize()//獲得當前List的大小

（3）、ClearList()//清空List

（4）、RemoveLast()//刪去List中的最後元素

由於每次刪除當前List中的最後一個元素，實現後進先出，所以可以模擬棧的功能實現悔棋。

9.myCompare類

由於在計算機下棋的極大極小博弈樹演算法中需要對自定義對象chessOneStep按weight進行排序，所以引入了myCompare類，通過實現Comparator介面中的compare方法完成自定義對象排序。

10.chessPanel類

程序的自定義面板類，主要負責完成當前框架內容的顯示。這是一個重要的與框架和圖形顯示密切相關的類。主要數據成員為

privatechessboardMyChessBoard;//當前顯示棋盤

privatechesspieceMyChessPiece;//當前顯示整個棋面的狀態

主要方法如下：

（1）、chesspanel(chessboardMyChessBoard1,chesspieceMyChessPiece1)//構造函數，分別用MyChessBoard1和MyChessPiece1初始化MyChessBoard和MyChessPiece

（2）display(chessboardMyChessBoard1,chesspieceMyChessPiece1)//自定義顯示回調函數，調用repaint()完成重新繪制游戲界面

（3）、paintComponent(Graphicsg)//核心方法，調用各種函數完成具體的繪制工作

11.chessPositon類

程序演算法核心類，總的功能是控制人和計算機輪流下棋，以及調用chessPanel類中的display(chessboard,chesspiece)方法完成界面的實時刷新。關於chessPositon類，我在此將重點介紹。chessPosition類的主要數據成員如下：

;//當前顯示棋盤

;//當前顯示整個棋面的狀態

;////當前顯示面板

=newchesslist();//當前下棋集合，用於悔棋

finalprivatestaticintINF=(1<<30);//表示正無窮大的常量，用於極大極小博弈數搜索演算法

publicstaticbooleanCanGo;//控制當前下棋一方

類的設計集中體現在成員方法的設計上。實現人機對戰，只有語言是遠遠不夠的，還要加入演算法，用演算法引導計算機下棋。下面介紹該類的方法成員：

（1）、chessposition(chesspanel,chessboard,chesspiece)//帶有參數的構造函數

（2）、chessposition()

不帶參數的構造函數

（3）、mouseClicked(MouseEventevent)

滑鼠響應函數，負責人的下棋，根據滑鼠點擊的位置轉換得到所在棋盤的相對位置。如果該位置不合法，即超出棋盤有效范圍，點擊無響應；如果該位置上已有棋，彈出消息框給出提示。這二者都要求重新給出下棋位置，即當前滑鼠響應無效…直到點擊到棋盤有效區域。

（4）、IsOver(int[][]Array,intx,inty)

判斷當前int[][]Array對應的棋局是否結束，即一方五子連成一條直線。此處有兩種思路，一種對當前棋面上的所有棋子都進行一次判斷，具體為水平方向、豎直方向、與水平線成45度方向、與水平線成135度方向，只要有一個方向五子連成一條直線就說明有一方獲勝，游戲結束；另一種思路為只在當前下棋的4個方向進行判斷，我的程序採用的是第二種，所以IsOver方法除了int[][]Array參數外，還有x,y參數，（x,y）表示當前下棋的坐標點。

（5）display()

通過調用自定義面板類的顯示回調函數用於重新顯示游戲界面，達到每下一步棋及時更新游戲界面的目的。

（6）、GetValue(intflag,intnum)

估值函數，根據經驗把棋局分成只有1顆棋相連，2顆棋相連且兩端被封死，2顆棋相連且一端封死另一端活的，2顆棋相連且兩端都是活的，同理3顆棋、4顆棋也各自可分3種情況。不同的情況對應不同的估價值。估價值的設定是決定計算機一方是否智能的一個關鍵因素。

（7）、GetPredictValue(intflag,intnum)

對未連成一片但通過再下一顆子就能連成一片的局面進行估值，這在雙方下棋的有限步驟內是能產生重要影響的。如果每局棋僅考慮當前一步，是不可取的。

（8）、Evaluate(int[][]Array,intx,inty)

根據棋面具體情況以及預先設定的估值函數，對某個點對應的局面進行評估。由於每次雙方只能下一顆棋，所以可以每次取當前局面的所有點中對應估值最大值點的估值作為整個局面的估值。

（9）、GetGreedNext()

計算機下棋方法1，對應難度等級為簡單，採用貪心思想。每次下棋前在求得最有利點下棋，而是否最有利只是通過一步評估。演算法偽碼描述為：

Max取負無窮大

for(行i從0到15)

{

For(列j從0到15)

{

If((i，j)對應的位置無棋)

{

a.假設放上一顆由人控制的棋，求估價值；

b.假設放上一顆由計算機控制的棋，求估價值；

c.取二者中較大值作為(i,j）處的估價值tmp；

d.取tmp與Max較大值賦值給Max.

}

}

}

最終Max對應的點就是當前整個局面中最大的估值點。至於上述為什麼要考慮雙方都在該點下棋的情況呢？主要原因為下五子棋是個攻防兼備的過程，不僅要考慮自己對自己最有利，還要考慮對對手最不利，通俗來講就是在自己贏的時候不能讓對手先贏。

（10）、GetSearchNext(intLookLength)

derectSearch(int[][]Array,booleanwho,intdeepth)

計算機下棋方法2：直接搜索法,對應難度等級為中等。

每步棋最多有225個不同下法，若採用直接搜索法則對應的孩子節點有225個（在下棋過程中會逐漸減少），即每層有最多225個節點待擴展，這就決定了直接搜索進行不超過2次—主要原因有兩點：

a.採用深度優先搜索需要遞歸，遞歸中狀態過多可能會爆棧，我們知道遞歸是用棧機制來實現的；採用寬度優先搜索又需要存儲為擴展的節點，這對內存容量要求很高。

b.不管深搜還是廣搜，在時間復雜度為O(N^m)的情況下都是不能接受的。其中N為當前棋局的待擴展節點，最大225;m為搜索的深度。

綜上所述，在採用直接搜索法時搜索深度不能太深，嚴格來說是應該控制在2層以內，在計算機運算速度在10^7次每秒的情況下，理論和實驗都表明超過2層就會變得很慢且這種趨勢成指數級增長。

直接搜索演算法偽代碼為

GetSearch(booleanflag，intdeep)

{

如果deep等於0，返回當前棋局估值；

for(行i從0到15)

{

For(列j從0到15)

{

If((i，j)對應的位置無棋)

{

如果輪到計算機下棋，置標志位為2

GetSearch(！flag，deep-1)；

如果輪到人下棋，置標志位為1；

GetSearch(！flag，deep-1)；

}

}

}

}

（11）、GetMinMaxsearchNext(intLookLength)

MinMaxsearch(int[][]Array,booleanwho,intdeepth)

計算機下棋演算法3：極大極小博弈樹法,對應難度等級為困難。五子棋是個博弈游戲，當前在尋找對自己最有利的下棋點時要盡可能保證對對手最不利，這種思想可以用極大極小博弈樹

③ 博弈樹與博弈矩陣的區別如何應用

C語言是一門通用計算機編程語言，應用廣泛。C語言的設計目標是提供一種能以簡易的方式編譯、處理低級存儲器、產生少量的機器碼以及不需要任何運行環境支持便能運行的編程語言。盡管C語言提供了許多低級處理的功能，但仍然保持著良好跨平台的特性，以一個標准規格寫出的C語言程序可在許多電腦平台上進行編譯，甚至包含一些嵌入式處理器（單片機或稱MCU）以及超級電腦等作業平台。二十世紀八十年代，為了避免各開發廠商用的C語言語法產生差異，由美國國家標准局為C語言訂定了一套完整的國際標准語法，稱為ANSI C，作為C語言最初的標准。

④ C語言 五子棋 博弈樹演算法 葉子節點的分值是如何計算的

其實這個不是難點的，那個分數是當前落子後所形成的以這個棋子為中心的9x9矩陣中所形成的棋型，計算其他地方的棋型顯然沒有什麼意義，再有就是不是C語言才可以寫演算法的，對於極大極小原理，博弈樹和alpha-beta剪枝演算法都是基於這個原理的，如果你是剛學編程不久，而且沒有數據結構的基礎是寫不出來運用博弈樹演算法的五子棋的，先把基礎打好再說。。

⑤ 博弈演算法里的剪枝怎麼用（具體的）

極大極小過程，以及阿爾法-貝塔剪紙。極小極大搜索方法是博弈樹搜索的基本方法，現在博弈樹搜索中最常用的α-β剪枝搜索方法，就是從這一方法發展而來的。
首先假定，有一個評價函數可以對所有的棋局進行評估。當評價函數值大於0時，表示棋局對我方有利，對對方不利。當評價函數小於0時，表示棋局對我方不利，對對方有利。而評價函數值越大，表示對我方越有利。當評價函數值等於正無窮大時，表示我方必勝。評價函數值越小，表示對我方越不利。當評價函數值等於負無窮大時，表示對方必勝。假設雙方都是對弈高手，在只看一步棋的情況下，我方一定走評價函數值最大的一步棋，而對方一定走評價函數值最小的一步棋。會下棋的讀者都知道，在只看一步的情況下最好的棋，從全局來說不一定就好，還可能很不好。因此為了走出好棋，必須多看幾步，從多種可能狀態中選擇一步好棋。
想一想人是如何下棋的呢？人實際上採用的是一種試探性的方法。首先假定走了一步棋，看對方會有那些應法，然後再根據對方的每一種應法，看我方是否有好的回應......這一過程一直進行下去，直到若干步以後，找到了一個滿意的走法為止。初學者可能只能看一、兩個輪次，而高手則可以看幾個，甚至十幾個輪次。
極小極大搜索方法，模擬的就是人的這樣一種思維過程。當輪到我方走棋時，首先按照一定的搜索深度生成出給定深度d以內的所有狀態，計算所有葉節點的評價函數值。然後從d-1層節點開始逆向計算：對於我方要走的節點（用MAX標記，稱為極大節點）取其子節點中的最大值為該節點的值（因為我方總是選擇對我方有利的棋）；對於對方要走的節點（用MIN標記，稱為極小節點）取其子節點中的最小值為該節點的值（對方總是選擇對我方不利的棋）。一直到計算出根節點的值為止。獲得根節點取值的那一分枝，即為所選擇的最佳走步。
在圖3.5所示的例子中，假定搜索深度為2，D～J是7個葉節點，在它們下邊括弧中的數字是這些節點的評價函數值（假定可以計算得到）。A、B、C是三個極小節點，它們分別取各自子節點最小值為自己的值，得到三個節點的值分別為-6、-2和-4。s是極大節點，從A、B、C三個節點的值中取最大值，得到-2。由於-2來自於節點B，所以搜索的結果是應選擇B作為我方的走步。對於我方來說，-2並不是一個好的結果，但卻是在對方不犯錯誤的情況下，對我方最有利的結果。因為從圖中可以看出，如果選擇A為我方的走步，如果對方回應D的話，我方可以得到評價值9，固然對我方有利。但是如果對方是一個高手的話，他一定回選擇E，而不是D。在這種情況下，我方只能得到-6，結果豈不是更差。因此，極小極大過程是一種假定對手每次回應都正確的情況下，如何從中找出對我方最有利的走步的搜索方法。
值得注意的是，不管設定的搜索深度是多少層，經過一次搜索以後，只決定了我方一步棋的走法。等到對方回應一步棋之後，需要在新的棋局下重新進行搜索，來決定下一步棋如何走。極小極大搜索策略是考慮雙方對弈若干步之後，從可能的走步中選一步相對好棋的著法來走，即在有限的搜索深度范圍內進行求解。為此要定義一個靜態估計函數f，以便對棋局的勢態（節點）作出優劣估值，這個函數可根據勢態優劣特徵來定義（主要用於對端節點的"價值"進行度量）。一般規定有利於MAX的勢態，f（p）取正值，有利於MIN的勢態，f（p）取負值，勢均力敵的勢態，f（p）取0值。若f（p）＝＋∞，則表示MAX贏，若f（p）＝－∞，則表示MIN贏。下面的討論規定：頂節點深度d＝0，MAX代表程序方，MIN代表對手方，MAX先走。
圖3.5是一個表示考慮兩步棋的例子，圖中端節點給出的數字是用靜態函數f（p）計算得到，其他節點不用f（p）估計，因為不夠精確，而應用倒推的辦法取值。例如A、B、C是MIN走步的節點，MAX應考慮最壞的情況，故其估值應分別取其子節點f（p）估值中最小者，而s是MAX走步的節點，可考慮最好的情況，故估值應取A、B、C值中的最大者。這樣求得f（s）＝－2，依此確定了相對較優的走步應是走向B，因為從B出發，對手不可能產生比f（s）＝－2更差的效果。實際上可根據資源條件，考慮更多層次的搜索過程，從而可得到更准確的倒推值，供MAX選取更正確的走步。當用端節點的靜態估計函數f（p）求倒推值時，兩位選手應採取不同的策略，從下往上逐層交替使用極小和極大的選值方法，故稱極小極大過程。

⑥ acm初學者要准備什麼 看什麼書啊

剛剛接觸信息學領域的同學往往存在很多困惑，不知道從何入手學習，在這篇文章里，我希望能將自己不多的經驗與大家分享，希望對各位有所幫助。
一、語言是最重要的基本功

無論側重於什麼方面，只要是通過計算機程序去最終實現的競賽，語言都是大家要過的第一道關。亞洲賽區的比賽支持的語言包括C/C++與JAVA。筆者首先說說JAVA，眾所周知，作為面向對象的王牌語言，JAVA在大型工程的組織與安全性方面有著自己獨特的優勢，但是對於信息學比賽的具體場合，JAVA則顯得不那麼合適，它對於輸入輸出流的操作相比於C++要繁雜很多，更為重要的是JAVA程序的運行速度要比C++慢10倍以上，而競賽中對於JAVA程序的運行時限卻往往得不到同等比例的放寬，這無疑對演算法設計提出了更高的要求，是相當不利的。其實，筆者並不主張大家在這種場合過多地運用面向對象的程序設計思維，因為對於小程序來說這不旦需要花費更多的時間去編寫代碼，也會降低程序的執行效率。

接著說C和C++。許多現在參加講座的同學還在上大一，C的基礎知識剛剛學完，還沒有接觸過C++，其實在賽場上使用純C的選手還是大有人在的，它們主要是看重了純C在效率上的優勢，所以這部分同學如果時間有限，並不需要急著去學習新的語言，只要提高了自己在演算法設計上的造詣，純C一樣能發揮巨大的威力。

而C++相對於C，在輸入輸出流上的封裝大大方便了我們的操作，同時降低了出錯的可能性，並且能夠很好地實現標准流與文件流的切換，方便了調試的工作。如果有些同學比較在意這點，可以嘗試C和C++的混編，畢竟僅僅學習C++的流操作還是不花什麼時間的。

C++的另一個支持來源於標准模版庫（STL），庫中提供的對於基本數據結構的統一介面操作和基本演算法的實現可以縮減我們編寫代碼的長度，這可以節省一些時間。但是，與此相對的，使用STL要在效率上做出一些犧牲，對於輸入規模很大的題目，有時候必須放棄STL，這意味著我們不能存在「有了STL就可以不去管基本演算法的實現」的想法；另外，熟練和恰當地使用STL必須經過一定時間的積累，准確地了解各種操作的時間復雜度，切忌對STL中不熟悉的部分濫用，因為這其中蘊涵著許多初學者不易發現的陷阱。

通過以上的分析，我們可以看出僅就信息學競賽而言，對語言的掌握並不要求十分全面，但是對於經常用到的部分，必須十分熟練，不允許有半點不清楚的地方，下面我舉個真實的例子來說明這個道理——即使是一點很細微的語言障礙，都有可能釀成錯誤：

在去年清華的賽區上，有一個隊在做F題的時候使用了cout和printf的混合輸出，由於一個帶緩沖一個不帶，所以輸出一長就混亂了。只是因為當時judge team中負責F題的人眼睛尖，看出答案沒錯只是順序不對（答案有一頁多，是所有題目中最長的一個輸出），又看了看程序發現只是輸出問題就給了個Presentation error（格式錯）。如果審題的人不是這樣而是直接給一個 Wrong Answer，相信這個隊是很難查到自己錯在什麼地方的。

現在我們轉入第二個方面的討論，基礎學科知識的積累。

二、以數學為主的基礎知識十分重要

雖然被定性為程序設計競賽，但是參賽選手所遇到的問題更多的是沒有解決問題的思路，而不是有了思路卻死活不能實現，這就是平時積累的基礎知識不夠。今年World Final的總冠軍是波蘭華沙大學，其成員出自於數學系而非計算機系，這就是一個鮮活的例子。競賽中對於基礎學科的涉及主要集中於數學，此外對於物理、電路等等也可能有一定應用，但是不多。因此，大一的同學也不必為自己還沒學數據結構而感到不知從何入手提高，把數學撿起來吧！下面我來談談在競賽中應用的數學的主要分支。

1、離散數學——作為計算機學科的基礎，離散數學是競賽中涉及最多的數學分支，其重中之重又在於圖論和組合數學，尤其是圖論。

圖論之所以運用最多是因為它的變化最多，而且可以輕易地結合基本數據結構和許多演算法的基本思想，較多用到的知識包括連通性判斷、DFS和BFS，關節點和關鍵路徑、歐拉迴路、最小生成樹、最短路徑、二部圖匹配和網路流等等。雖然這部分的比重很大，但是往往也是競賽中的難題所在，如果有初學者對於這部分的某些具體內容暫時感到力不從心，也不必著急，可以慢慢積累。

競賽中設計的組合計數問題大都需要用組合數學來解決，組合數學中的知識相比於圖論要簡單一些，很多知識對於小學上過奧校的同學來說已經十分熟悉，但是也有一些部分需要先對代數結構中的群論有初步了解才能進行學習。組合數學在競賽中很少以難題的形式出現，但是如果積累不夠，任何一道這方面的題目卻都有可能成為難題。

2、數論——以素數判斷和同餘為模型構造出來的題目往往需要較多的數論知識來解決，這部分在競賽中的比重並不大，但只要來上一道，也足以使知識不足的人冥思苦想上一陣時間。素數判斷和同餘最常見的是在以密碼學為背景的題目中出現，在運用密碼學常識確定大概的過程之後，核心演算法往往要涉及數論的內容。

3、計算幾何——計算幾何相比於其它部分來說是比較獨立的，就是說它和其它的知識點很少有過多的結合，較常用到的部分包括——線段相交的判斷、多邊形面積的計算、內點外點的判斷、凸包等等。計算幾何的題目難度不會很大，但也永遠不會成為最弱的題。

4、線性代數——對線性代數的應用都是圍繞矩陣展開的，一些表面上是模擬的題目往往可以藉助於矩陣來找到更好的演算法。

5、概率論——競賽是以黑箱來判卷的，這就是說你幾乎不能動使用概率演算法的念頭，但這也並不是說概率就沒有用。關於這一點，只有通過一定的練習才能體會。

6、初等數學與解析幾何——這主要就是中學的知識了，用的不多，但是至少比高等數學多，我覺得熟悉一下數學手冊上的相關內容，至少要知道在哪兒能查到，還是必要的。

7、高等數學——純粹運用高等數學來解決的題目我接觸的只有一道，但是一些題目的敘述背景往往需要和這部分有一定聯系，掌握得牢固一些總歸沒有壞處。

以上就是競賽所涉及的數學領域，可以說范圍是相當廣的。我認識的許多人去搞信息學的競賽就是為了逼著自己多學一點數學，因為數學是一切一切的基礎。

三、數據結構與演算法是真正的核心

雖然數學十分十分重要，但是如果讓三個只會數學的人參加比賽，我相信多數情況下會比三個只會數據結構與演算法的人得到更為悲慘的結局。

先說說數據結構。掌握隊列、堆棧和圖的基本表達與操作是必需的，至於樹，我個人覺得需要建樹的問題有但是並不多。（但是樹往往是很重要的分析工具）除此之外，排序和查找並不需要對所有方式都能很熟練的掌握，但你必須保證自己對於各種情況都有一個在時間復雜度上滿足最低要求的解決方案。說到時間復雜度，就又該說說哈希表了，競賽時對時間的限制遠遠多於對空間的限制，這要求大家盡快掌握「以空間換時間」的原則策略，能用哈希表來存儲的數據一定不要到時候再去查找，如果實在不能建哈希表，再看看能否建二叉查找樹等等——這都是爭取時間的策略，掌握這些技巧需要大家對數據結構尤其是演算法復雜度有比較全面的理性和感性認識。

接著說說演算法。演算法中最基本和常用的是搜索，主要是回溯和分支限界法的使用。這里要說的是，有些初學者在學習這些搜索基本演算法是不太注意剪枝，這是十分不可取的，因為所有搜索的題目給你的測試用例都不會有很大的規模，你往往察覺不出程序運行的時間問題，但是真正的測試數據一定能過濾出那些沒有剪枝的演算法。實際上參賽選手基本上都會使用常用的搜索演算法，題目的區分度往往就是建立在諸如剪枝之類的優化上了。

常用演算法中的另一類是以「相似或相同子問題」為核心的，包括遞推、遞歸、貪心法和動態規劃。這其中比較難於掌握的就是動態規劃，如何抽象出重復的子問題是很多題目的難點所在，筆者建議初學者仔細理解圖論中一些以動態規劃為基本思想所建立起來的基本演算法（比如Floyd-Warshall演算法），並且多閱讀一些定理的證明，這雖然不能有什麼直接的幫助，但是長期堅持就會對思維很有幫助。

四、團隊配合

通過以上的介紹大家也可以看出，信息學競賽對於知識面覆蓋的非常廣，想憑一己之力全部消化這些東西實在是相當困難的，這就要求我們盡可能地發揮團隊協作的精神。同組成員之間的熟練配合和默契的形成需要時間，具體的情況因成員的組成不同而不同，這里我就不再多說了。

五、練習、練習、再練習

知識的積累固然重要，但是信息學終究不是看出來的，而是練出來的，這是多少前人最深的一點體會，只有通過具體題目的分析和實踐，才能真正掌握數學的使用和演算法的應用，並在不斷的練習中增加編程經驗和技巧，提高對時間復雜度的感性認識，優化時間的分配，加強團隊的配合。總之，在這里光有紙上談兵是絕對不行的，必須要通過實戰來鍛煉自己。

大家一定要問，我們去哪裡找題做，又如何檢驗程序是否正確呢？這大可不必擔心，現在已經有了很多網上做題的站點，這些站點提供了大量的題庫並支持在線判卷，你只需要把程序源碼提交上去，馬上就可以知道自己的程序是否正確，運行所使用的時間以及消耗的內存等等狀況。下面我給大家推薦幾個站點，筆者不建議大家在所有這些站點上做題，選擇一個就可以了，因為每個站點的題都有一定的難易比例，系統地做一套題庫可以使你對各種難度、各種類型的題都有所認識。

1、Ural：

Ural是中國學生對俄羅斯的Ural州立大學的簡稱 ，那裡設立了一個Ural Online Problem Set，並且支持Online Judge。Ural的不少題目演算法性和趣聞性都很強，得到了國內廣大學生的厚愛。根據「信息學初學者之家」網站的統計，Ural的題目類型大概呈如下的分布：

題型
搜索
動態規劃
貪心
構造
圖論
計算幾何
純數學問題
數據結構
其它

所佔比例
約10%
約15%
約5%
約5%
約10%
約5%
約20%
約5%
約25%

這和實際比賽中的題型分布也是大體相當的。有興趣的朋友可以去看看。

2、UVA：

UVA代表西班牙Valladolid大學(University de Valladolid)。該大學有一個那裡設立了一個PROBLEM SET ARCHIVE with ONLINE JUDGE ，並且支持ONLINE JUDGE，形式和Ural大學的題庫類似。不過和Ural不同的是，UVA題目多的多，而且比較雜，而且有些題目的測試數據比較刁鑽。這使得剛到那裡做題的朋友往往感覺到無所適從，要麼難以找到合適的題目，要麼Wrong Answer了很多次以後仍然不知道錯在那裡。 如果說做Ural題目主要是為了訓練演算法，那麼UVA題目可以訓練全方位的基本功和一些必要的編程素質。UVA和許多世界知名大學聯合辦有同步網上比賽，因此那裡強人無數，不過你先要使自己具有聽懂他們在說什麼的素質：）

3、ZOJ：

ZOJ是浙江大學建立的ONLINE JUDGE，是中國大學建立的第一個同類站點，也是最好和人氣最高的一個，筆者和許多班裡的同學就是在這里練習。ZOJ雖然也定位為一個英文網站，但是這里的中國學生比較多，因此讓人覺得很親切。這里目前有500多道題目，難易分配適中，且涵蓋了各大洲的題目類型並配有索引，除此之外，ZOJ的JUDGE系統是幾個網站中表現得比較好的一個，很少出現Wrong Answer和Presentation error混淆的情況。這里每月也辦有一次網上比賽，只要是注冊的用戶都可以參加。

說起中國的ONLINE JUDGE，去年才開始參加ACM競賽的北京大學現在也建立了自己的提交系統；而我們學校也是去年開始參加比賽，現在也有可能推出自己的提交系統，如果能夠做成，到時候大家就可以去上面做題了。同類網站的飛速發展標志著有越來越多的同學有興趣進入信息學的領域探索，這是一件好事，同時也意味著更激烈的競爭。

看看這篇文章對你有什麼幫助！我也是ACM初學者！

⑦ 求五子棋C語言AI演算法(原創思路)

我有個簡單的思路： 先定義一條線上棋子的各種布局，比如初步定義長度為五個子 ◎◎◎◎● ◎◎●◎× ◎●◎×× ◎×◎×◎ 等等。白圈是自己的子，黑圈是對方的子，叉子是未走的格子。 程序里有個布局表，再定義各個布局的分數，比如連五最99分，連三30分等等。 ...

⑧ C語言，用「博弈樹」方法編程的人工智慧程序的實例 最好源程序中有「注釋」，請發我郵箱[email protected]

這么點分