人工智能-博弈樹的搜索45-展示頁
2025-02-25 00:32本頁面
【正文】 的兩堆時就得認輸。 博弈 ? Grundy博弈是一個分錢幣的游戲。 博弈 ? 下棋的雙方是對立的 ， 命名博弈的雙方 ， 一方為“ 正方 ” ， 這類節(jié)點稱為 “ MAX”節(jié)點；另一方為“ 反方 ” ， 這類節(jié)點稱為 “ MIN”節(jié)點 。 ? 零和，即對一方有利的棋，對另一方肯定是不利的，不存在對雙方均有利或無利的棋。 正在與深藍下棋的卡斯帕羅夫 ? 博弈問題特點： ? 雙人對弈，輪流走步。??● ○ ??● ○ ??● ○ ?? ● ○ ● ?? ○ ● ?? ○ ● ?? ○ ● ?? ○ 博弈樹搜索 ? 20世紀 60年代，研制出的西洋跳棋和國際象棋的博弈程序達到了大師級的水平。 ? 1958約翰 ?麥卡錫提出博弈樹搜索算法 ? 1997年， IBM公司研制的“深藍”國際象棋 程序，采用博弈樹搜索算法，該程序戰(zhàn)勝了國際象棋世界冠軍卡斯帕羅夫。 ? 信息完備，雙方所得到的信息是一樣的。 ? 博弈的特性 ① 兩個棋手交替地走棋 ； ② 比賽的最終結果，是贏、輸和平局中的一種； ③ 可用圖搜索技術進行，但效率很低； ④ 博弈的過程，是尋找置對手于必敗態(tài)的過程； ⑤ 雙方都無法干預對方的選擇。 正方和反方是交替走步的 ， 因此 MAX節(jié)點和 MIN節(jié)點會交替出現(xiàn) 。有 一堆數(shù)目為 N的錢幣，由兩位選手輪流進行分堆，要求每個選手每次只把其中某一堆分成數(shù)目不等的兩小堆。 博弈 ? 設初始狀態(tài)為 (7， MIN)，建立問題的狀態(tài)空間圖，圖中所有終結點均表示該選手必輸?shù)那闆r，取勝方的目標是設法使棋局發(fā)展為結束在對方走步時的終結點上。 博弈 搜索策略要考慮的問題是： ? 對 MIN走步后的每一個 MAX結點，必須證明 MAX對 MIN可能走的每一個棋局對弈后能獲勝，即 MAX必須考慮應付 MIN的所有招法，這是一個與的含意，因此含有 MAX符號的結點可看成與結點。 博弈 ? 對弈過程的搜索圖呈現(xiàn)出與或圖表示的形式。 博弈 中國象棋 ? 一盤棋平均走 50步，總狀態(tài)數(shù)約為 10的161次方。 ? 結論：不可能窮舉。 ? 評估的方法：用評價函數(shù)對棋局進行評估。 ? 評估的標準：由于下棋
高考資料相關推薦
鄂ICP備17016276號-1