45極小極大分析法

1、14.5 極小極大分析法 在博弈過程中，任何一方都希望自己取得勝利。因此，當(dāng)某一方當(dāng)前有多個(gè)行動方案可供選擇時(shí)，他總是挑選對自己最為有利而對對方最為不利的那個(gè)行動。24.5.1 靜態(tài)估值靜態(tài)估值 根據(jù)問題的特性信息定義一個(gè)估價(jià)函數(shù)估價(jià)函數(shù)，用來估算當(dāng)前博弈樹節(jié)點(diǎn)的得分。 此時(shí)估算出來的得分稱為靜態(tài)估值靜態(tài)估值。3例例1：一字棋游戲。：一字棋游戲。 設(shè)有如圖所求的九個(gè)空格，由a，b二個(gè)對弈，輪到誰走棋就往空格上放一只自己的棋子，誰先使自已的棋子構(gòu)成“三子成一線”誰就取得了勝利 。設(shè)a的棋子用來表示，b的棋子用來表示。 根據(jù)問題的特性信息定義一個(gè)估價(jià)函數(shù)估價(jià)函數(shù)，用來估算當(dāng)前博弈樹節(jié)點(diǎn)的得分_-靜

2、態(tài)估值靜態(tài)估值(decide which one is better)4估價(jià)函數(shù)定義：設(shè)棋局為p，估價(jià)函數(shù)為e(p).若p是勝負(fù)未定的棋局，則e(p)= e(+p)- e(-p) 其中 e(+p)表示棋局p上有可能使成為三子一線的數(shù)目。e(-p) 表示棋局p上有可能使成為三子一線的數(shù)目。5e(p) = 6 4 = 2e(-p) 表示棋局p上有可能使成為三子一線的數(shù)目。6 根據(jù)問題的特性信息定義一個(gè)估價(jià)函數(shù)估價(jià)函數(shù)，用來估算當(dāng)前博弈樹節(jié)點(diǎn)的得分_-靜態(tài)估值靜態(tài)估值(decide where next black one will go)例例2：5 chesspiece game 4.5.2 極小

3、極大分析法基本思想極小極大分析法基本思想(1)站在站在x方方 設(shè)博弈的雙方中一方為x，另一方為y，站在站在x方方立場上為其尋找一個(gè)最優(yōu)行動方案。(2)向前搜索向前搜索若干步 為了找到當(dāng)前的最優(yōu)行動方案，需對各個(gè)可能的方案所產(chǎn)生的后果進(jìn)行比較。 考慮每一方案實(shí)施后對方可能采取的所有行動，并計(jì)算計(jì)算每一方案每一方案可能的得可能的得分分。為比較不同方案的優(yōu)劣比較不同方案的優(yōu)劣，需向前搜索向前搜索若干步。8example 3274-114 根據(jù)估價(jià)函數(shù)估價(jià)函數(shù)，估算當(dāng)前博弈樹節(jié)點(diǎn)的得分。7分是最好的格局。在眾多的可能格局中，如何達(dá)到最好的?9 (3)倒推值倒推值-極小極大分析法極小極大分析法 當(dāng)端節(jié)點(diǎn)

4、的估值計(jì)算出來后，再推算出父節(jié)推算出父節(jié)點(diǎn)的得分點(diǎn)的得分，這樣計(jì)算出的父節(jié)點(diǎn)的得分稱為倒推倒推值值 。對對“或或”節(jié)點(diǎn)節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最大最大的得分作為父節(jié)點(diǎn)的得分；對對“與與”節(jié)點(diǎn)節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最小最小的得分作為父節(jié)點(diǎn)的得分;1032274-1-1114-2-2643532example 411極小極大分析法-當(dāng)前最好的行動行動方案對對“或或”節(jié)點(diǎn)節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最大最大的得分作為父節(jié)點(diǎn)的得分，這是為了使自己在可供選擇的方案中選一個(gè)對自己最有利的方案；對對“與與”節(jié)點(diǎn)節(jié)點(diǎn)，選其子節(jié)點(diǎn)中一個(gè)最小最小的得分作為父節(jié)點(diǎn)的得分，這是為了立足于最壞的情況。 估價(jià)函數(shù)是估價(jià)函數(shù)是站在

5、站在x方方立場上估計(jì)分?jǐn)?shù), 當(dāng)格局對對方有利時(shí),估價(jià)估價(jià)函數(shù)給出的函數(shù)給出的估計(jì)分值分值 小小(對對x方方而言而言). 如果一個(gè)行動方案能獲得較大的倒推值，則它就是當(dāng)前最好的行動行動方案。1232274-1-1114-2-2643532example 5當(dāng)前最好的行動行動方案分別是？13所有可能的格局example 6站在x方方向前搜索 根據(jù)估價(jià)函數(shù)估價(jià)函數(shù)，估算當(dāng)前博弈樹節(jié)點(diǎn)的得分。當(dāng)前最好的行動行動方案是？1423232274-1-1224-2-264353446-56-51863268213343example 6當(dāng)前最好的行動行動方案是？15例例7：一字棋游戲。：一字棋游戲。 設(shè)有如圖

6、所求的九個(gè)空格，由a，b二個(gè)對弈，輪到誰走棋就往空格上放一只自己的棋子，誰先使自已的棋子構(gòu)成“三子成一線”誰就取得了勝利 。設(shè)a的棋子用來表示，b的棋子用來表示。16估價(jià)函數(shù)定義：設(shè)棋局為p，估價(jià)函數(shù)為e(p).(1) 若p是a必勝的棋局，則e(p)=+. (2) 若p是b必勝的棋局，則e(p)= .(3) 若p是勝負(fù)未定的棋局，則e(p)= e(+p)- e(-p) 其中 e(+p)表示棋局p上有可能使成為三子一線的數(shù)目。e(-p) 表示棋局p上有可能使成為三子一線的數(shù)目。17e(p) = 6 4 = 2e(-p) 表示棋局p上有可能使成為三子一線的數(shù)目。18 假定：1. a先走棋，站在a的

7、立場上。2. 博弈樹每次僅擴(kuò)展兩層3. 具有對稱性的兩個(gè)棋局算作一個(gè)棋局。 圖中節(jié)點(diǎn)旁的數(shù)字分別表示相應(yīng)節(jié)點(diǎn)的靜態(tài)估值或倒推值。 由圖可以看出，對于a來說最好的一步棋是s3,因?yàn)?s3比s1和s2有較大的倒推值。 在a走s3這一步棋后，b的最優(yōu)選擇是s4,因?yàn)檫@一步棋的靜態(tài)估值較小，對a不利。 不管b選擇s4 或s5，a都要再次運(yùn)用極小極大分析法產(chǎn)生深度為2的博弈樹，以決定下一步應(yīng)該如何走棋，其過程與上面類似。 圖如下頁19一字棋極小極大搜索s0s1s2s3s4s520雙方博弈4步后的當(dāng)前格局summary 雙方博弈過程中出現(xiàn)過的格局 初始格局max-min help one side to to take action.212232274-1-1224-2-264353446-56-543example 8當(dāng)前最好的行動