人工智能
實驗二：利用α-β搜尋過程的博弈樹搜尋算法編寫一字棋遊戲
一、實驗目的與要求
(1)了解極大極小算法的原理和使用方法，并學會用α-β剪枝來提高算法的效率。
(2)使用C語言平台，編寫一個智能井字棋遊戲。
(3)結合極大極小算法的使用方法和α-β剪枝，讓機器與人對弈時不但有智能的特征，而且計算的效率也比較高。
二、實驗原理
一字棋遊戲是一個流傳已久的傳統遊戲。遊戲由兩個人輪流來下，分别用“X”和“O”來代替自身的棋子。棋盤分9個格，雙方可以在輪到自己下的時候，可以用棋子占領其中一個空的格子。如果雙方中有一方的棋子可以連成一條直線，則這一方判勝，對方判負。當所有的格子都被占領，但雙方都無法使棋子連成一條直線的話，則判和棋。
這是一個智能型的一字棋遊戲，機器可以模拟人與使用者對弈。當輪到機器來下的時候，機器會根據目前棋局的形勢，利用極大極小算法算出一個評價值，判斷如何下才對自身最有利，同時也是對方來說對不利的，然後下在評價值最高的地方。另外利用α-β剪枝，使機器在搜尋評價值的時候不用擴充不必要的結點，進而提高機器計算的效率。
在使用者界面方法，用一個3×3的井字格來顯示使用者與機器下的結果。當要求使用者輸入資料的時候會有提示資訊。使用者在下的過程中可以中途按下“0”退出。當使用者與計算機分出了勝負後，機器會顯示出比賽的結果，并按任意鍵退出。如果使用者在下棋的過程中，輸入的是非法字元，機器不會做出反應。
三、實驗步驟和過程
1.α-β搜尋過程
在極小極大搜尋方法中，由于要先生成指定深度以内的所有節點，其節點數将随着搜尋深度的增加承指數增長。這極大地限制了極小極大搜尋方法的使用。能否在搜尋深度不變的情況下，利用已有的搜尋資訊減少生成的節點數呢？設某博弈問題如下圖所示，應用極小極大方法進行搜尋
MINIMAX過程是把搜尋樹的生成和格局估值這兩個過程分開來進行，即先生成全部搜尋樹，然後再進行端節點靜态估值和倒推值計算，這顯然會導緻低效率。如圖1中，其中一個MIN節點要全部生成A、B、C、D四個節點，然後還要逐個計算其靜态估值，最後在求倒推值階段，才賦