極大極小算法

博弈:諸如下棋、打牌、戰(zhàn)爭(zhēng)等一類競(jìng)爭(zhēng)性的智能活動(dòng)。其中最簡(jiǎn)單的一種稱為雙方完備博弈

博弈是AI研究的起源和動(dòng)力之一，是啟發(fā)式算法所針對(duì)的一個(gè)重要領(lǐng)域1、提供了可構(gòu)造的任務(wù)領(lǐng)域，能明確判斷成功或失敗2、博弈問(wèn)題是對(duì)AI研究提出了嚴(yán)峻的挑戰(zhàn)。

如何表示博弈問(wèn)題的狀態(tài)、博弈的過(guò)程和博弈的知識(shí)？極大極小搜索思想1、極大極小策略是考慮雙方對(duì)弈若干步之后，從可能的步中選一步相對(duì)好的步法來(lái)走，即在有限的搜索深度范圍內(nèi)進(jìn)行求解定義一個(gè)靜態(tài)估價(jià)函數(shù)f,以便對(duì)棋局的態(tài)勢(shì)作出優(yōu)劣評(píng)估

規(guī)定：MAX和MIN代表對(duì)弈雙方P代表一個(gè)棋局(即一個(gè)狀態(tài)）有利于MAX的態(tài)勢(shì)，f(p)取正值有利于MIN的態(tài)勢(shì)，f(p)取負(fù)值態(tài)勢(shì)均衡，f(p)取零值2、MINMAX的基本思想：(1)當(dāng)輪到MIN走步時(shí)，MAX應(yīng)該考慮最壞的情況（即f(p)取極小值）(2)當(dāng)輪到MAX走步時(shí)，MAX應(yīng)該考慮最好的情況（即f(p)取極大值）(3)評(píng)價(jià)往回倒推時(shí)，相應(yīng)于兩位棋手的對(duì)抗策略，交替使用（1）和（2）兩種方法傳遞倒推值。算法分析和舉例例子：一字棋（或井字棋）算法分析設(shè)棋局為P，估價(jià)函數(shù)為e(P)。規(guī)定：(1)若P對(duì)任何一方來(lái)說(shuō)都不是獲勝的位置，則e(P)=e(所有空格都放上MAX的棋子后三字成一線的總數(shù))-e(所有空格都放上MIN的棋子后三字成一線的總數(shù))(2)若P是MAX必勝的棋局，則e(P)＝+∞。(3)若P是MIN必勝的棋局，則e(P)＝-∞。

比如P如右圖示,則e(P)=6-4=2叉代表MAX

方，圓圈代表MIN方

向上值的傳播規(guī)則：若父狀態(tài)在MIN層，那么孩子中最小值被傳遞上去若父狀態(tài)在MAX層,那么孩子中最大值被傳遞上去算法分析①M(fèi)AXMINMAX由于上圖所示位置具有最大的倒推值，它應(yīng)當(dāng)選取為MAX的第一步（正好是MAX的最好的優(yōu)先走步）算法分析②

現(xiàn)在圖中MAX有兩個(gè)可能“最好的”優(yōu)先走步，假設(shè)MAX走了圖上指明的那一步

MAXMIN算法分析③MAXMIN

如上圖，