人工智能-博弈樹的搜索45-wenkub
2023-03-10 00:32:07 本頁面
【正文】 ：不可能窮舉。 博弈 ? 對弈過程的搜索圖呈現(xiàn)出與或圖表示的形式。 博弈 ? 設初始狀態(tài)為 (7， MIN)，建立問題的狀態(tài)空間圖，圖中所有終結(jié)點均表示該選手必輸?shù)那闆r，取勝方的目標是設法使棋局發(fā)展為結(jié)束在對方走步時的終結(jié)點上。 正方和反方是交替走步的 ， 因此 MAX節(jié)點和 MIN節(jié)點會交替出現(xiàn) 。 ? 信息完備，雙方所得到的信息是一樣的。??● ○ ??● ○ ??● ○ ?? ● ○ ● ?? ○ ● ?? ○ ● ?? ○ ● ?? ○ 博弈樹搜索 ? 20世紀 60年代，研制出的西洋跳棋和國際象棋的博弈程序達到了大師級的水平。 ? 零和，即對一方有利的棋，對另一方肯定是不利的，不存在對雙方均有利或無利的棋。 博弈 ? Grundy博弈是一個分錢幣的游戲。 MIN先走 MAX必勝 博弈 ? 結(jié)點 A是 MAX的搜索目標，而結(jié)點 B， C則為 MIN的搜索目標。 ? 實現(xiàn)一種取勝的策略就是搜索一個解圖的問題，解圖就代表一種完整的博弈策略。 ? 對各個局面進行評估 ? 評估的目的：對后面的狀態(tài)提前進行考慮，并且以各種狀態(tài)的評估值為基礎作出最好的走棋選擇。 MAX節(jié)點和 MIN節(jié)點 ? 命名博弈的雙方，一方為“正方”，對每個狀態(tài)的評估都是對應于該方的輸贏的。反方每走一步，都在選擇使對手輸?shù)酶嗟墓?jié)點，因此這類節(jié)點稱為“ MIN”節(jié)點。 ? 反復進行這種選取，就可以得到雙方各個節(jié)點的評估值。 對手 MIN的棋子用 (o)表示。 A B ╳ ╳ ╳ 〇 〇 C 〇 棋盤殘局舉例： A B ╳ ╳ ╳ 〇 〇 C 〇 ╳ B ╳ ╳ ╳ 〇 〇 C 〇 ╳ 〇 ╳ ╳ ╳ 〇 〇 C 〇 ╳ B ╳ ╳ ╳ 〇 〇 〇 〇 0 A ╳ ╳ ╳ ╳ 〇 〇 C 〇 〇 ╳ ╳ ╳ ╳ 〇 〇 C 〇 A ╳ ╳ ╳ ╳ 〇 〇 〇 〇 A B ╳ ╳ ╳ 〇 〇 ╳ 〇 〇 B ╳ ╳ ╳ 〇 〇 ╳ 〇
高考資料相關推薦
鄂ICP備17016276號-1