1-博弈搜索(編輯修改稿)
2025-08-31 07:18 本頁面
【文章內(nèi)容簡介】 取任何冒險(xiǎn)行動(dòng) ,視對(duì)手將走出的棋局為 極小值 ； ? 考慮我方走步時(shí)（ 或 節(jié)點(diǎn)） ： 應(yīng)在對(duì)方造成的最壞的局勢中盡可能地選擇最好的棋著走，視自己可能走出的棋局為 極大值 。 曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 Slide 33 基于博弈搜索的搜索策略 ? 博弈問題及博弈樹 ? 博弈搜索控制策略 ? 博弈搜索算法及其應(yīng)用實(shí)例 ? 博弈樹的 α β 剪枝 ? 完整的博弈搜索策略 （盲目搜索策略） ? 有界深度博弈搜索策略 曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 Slide 34 完整的 博弈搜索策略 ?核心思想： 從博弈的 初始格局 開始，輪番考慮自己與對(duì)方可能的所有走步，生成出棋局的各個(gè)格局，直到達(dá)到分出勝負(fù)輸贏的 終止格局 為止，此搜索過程 產(chǎn)生的一棵 完整的博弈樹 。 曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 Slide 35 完整的 博弈搜索策略 ? 博弈問題實(shí)例 ： 有一堆數(shù)目為 N的錢幣，甲、乙二人輪流分堆。要求每人每次挑選其中某一堆錢幣，將其分成數(shù)目不等的兩小堆。分堆過程持續(xù)，直至其中一人無法再將任一堆錢幣分成數(shù)目不等的兩堆時(shí)，則認(rèn)輸。 ? 博弈問題描述： 分堆格局 (狀態(tài) ): (x1,x2,?,xn,M), 其中， xi: 第 i 堆錢幣的個(gè)數(shù)； M: 當(dāng)前走步人編號(hào) （ MAX, MIN） 走步規(guī)則： IF (x1,x2,… ,xn,M) ∧ (xi = Y+Z) ∧ (Y ≠ Z ) THEN (x1,x2,… ,xi1, Y, Z, xi+1, … , xn, ? M) 曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 Slide 36 完整的 博弈搜索策略 站在 MAX立場 與節(jié)點(diǎn) 或節(jié)點(diǎn) 與節(jié)點(diǎn) 完全取勝的完備策略 曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 Slide 37 ? 特點(diǎn)： ? 搜索策略簡單，易于控制， 可用于 簡單的博弈 或一個(gè)復(fù)雜博弈的 殘局 ； 完整的 博弈搜索策略 ?不適合 復(fù)雜的博弈問題搜索 指數(shù)爆炸 。 例， 中國象棋： 設(shè)每種格局有 40種走法，一盤棋雙方平均走 50步， 完整的博弈搜索 搜索節(jié)點(diǎn)數(shù)（ 402） 50 ≈ 10160，搜索深度達(dá) 100層。 ? 有必要引入 有界深度博弈搜索策略 。 曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 Slide 38 基于博弈搜索的搜索策略 ? 博弈問題及博弈樹 ? 博弈搜索控制策略 ? 完整的博弈搜索策略 （盲目搜索策略） ? 有界深度博弈搜索策略 （啟發(fā)式搜索策略） 曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 Slide 39 有界深度搜索策略 ? 核心思想： 根據(jù)對(duì)方已走出的棋步，構(gòu)造出具有一定深度的博弈樹，并從此局部博弈樹中 選擇 相對(duì)好 的 棋著 走 。 ? 需解決的 關(guān)鍵問題： 定義 估計(jì) 終結(jié)棋局 優(yōu)劣 的評(píng)價(jià)函數(shù)； 給出 棋局 優(yōu)劣性 傳遞的 計(jì)算方法。 曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 Slide 40 定義 棋局的 評(píng)價(jià)函數(shù) 設(shè) P 為 有界博弈樹 中棋局； ｈ (P): 棋局Ｐ優(yōu)劣的評(píng)價(jià)函數(shù)。 ? 例 1：從當(dāng)前棋局到離我方最后取勝的差距： 勝利在望 – ｈ (P)值較大， 敗局顯露 – ｈ (P)值較小； ? 例 2：從當(dāng)前棋局到到某個(gè)明顯有利于我方棋局的差距： 吃掉對(duì)方一子 , 或者 “ 叫吃 ” 。 ? ｈ (P)MAX贏 = ｈ (P)MIN輸 = +∞ ? ｈ (P)MAX輸 = ｈ (P)MIN贏 = ∞ ? ｈ (P)平 = 0 ? ｈ (P) – 任一終葉棋局Ｐ優(yōu)劣的評(píng)價(jià)函數(shù)的 定義原則： 曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 Slide 41 計(jì)算 棋局的 評(píng)價(jià)函數(shù) 有界博弈樹中任一棋局（節(jié)點(diǎn)Ｐ） 評(píng)價(jià) 函數(shù) 值的 計(jì)算 ： ? 對(duì)于 終葉節(jié)點(diǎn)Ｐ ： 賦 靜態(tài)評(píng)價(jià)函數(shù)值ｈ (P)。 ? 對(duì)于 非終葉節(jié)點(diǎn)Ｐ ：按 極小 極大走步原則 ，采用倒推的方法， 自下而上 地由子節(jié)點(diǎn) 計(jì)算 父節(jié)點(diǎn)的 動(dòng)態(tài)評(píng)價(jià)函數(shù)值ｈ (P)。 曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 Slide 42 站在 MAX立場 基于 極小 極大原則 的 評(píng)價(jià) 函數(shù) 計(jì)算實(shí)例 靜態(tài) 啟發(fā)式評(píng)價(jià)函數(shù)值 動(dòng)態(tài) 評(píng)價(jià)函數(shù)值 曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 Slide 43 基于博弈搜索的搜索策略 ? 博弈問題及博弈樹 ? 博弈搜索控制策略 ? 有界深度搜索算法及其應(yīng)用實(shí)例 ? 博弈樹的 α β 剪枝 曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院 Slide 44 有界深度搜索 算法 及其應(yīng)用實(shí)例 ? 針對(duì) 當(dāng)前 對(duì)方 給出的棋局 s ： 按寬度優(yōu)先法 自上而下地 生成 規(guī)定深度 的博弈樹； 為有界深度博弈樹的所有 葉節(jié)點(diǎn) 賦 靜態(tài)評(píng)價(jià)函數(shù)估計(jì)值 根據(jù) 極小 極大走步原則 自下而上地 逐級(jí) 計(jì)算各 非終葉節(jié)點(diǎn)的 動(dòng)態(tài) 評(píng)價(jià)函數(shù)估計(jì)值， 直至求到起始節(jié)點(diǎn)的 評(píng)價(jià)函數(shù)值 ｈ (s)為止。 ? 比較我方可走的各棋局的 評(píng)價(jià)函數(shù)估計(jì)值， 從中選擇 最好 的棋步走。 ? 再根據(jù)對(duì)方走出的棋局 s，重復(fù)上述過程。 曲阜師范大學(xué)
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1