人工智能之與或圖搜索問題-展示頁
2025-02-25 13:05本頁面
【正文】 n1 n2 n3 n4 n5 n6 n7 n8 14 博弈 是一類具有競爭性的智能活動 雙人博弈 ：即兩位選手對壘 ， 輪流依次走步 ，其中任何一方都完全知道對方過去已經(jīng)走過的棋步和今后可能的走步 ， 其結(jié)果是一方贏 (而另一方則輸 )， 或雙方和局 博弈樹搜索 15 博弈的例子 ： ? 一字棋 ? 跳棋 ? 中國象棋 ? 圍棋 ? 五子棋 16 博弈樹搜索 ? 博弈問題 ? 雙人對弈 ， 對壘的雙方輪流走步； ? 信息完備 ， 對壘雙方所得到的信息是一樣的 ，不存在一方能看到 ， 而另外一方看不到的情況； ? 零和 ， 即對一方有利的棋 ， 對另一方肯定是不利的 ， 不存在對雙方均有利或均無利的棋 ， 對弈的結(jié)果是一方贏 ， 而另一方輸 ， 或者雙方和棋 。 ? 若非終節(jié)點有 “ 或 ” 子節(jié)點 ， 當且僅當所有子節(jié)點均不能解時 ， 該非終節(jié)點才不能解 。 ? 若非終節(jié)點有 “ 與 ” 子節(jié)點時 ， 當且僅當其子節(jié)點均能解時 ， 該非終節(jié)點才能解 。第二章 與或圖搜索問題 目標 目標 初始節(jié)點 s a b c 1 基本概念 ? 與或圖是一個超圖 ， 節(jié)點間通過連接符連接 。 ? K連接符： …... K個 2 耗散值的計算 k(n, N) = Cn+k(n1, N)+… +k(ni, N) 其中： N為終節(jié)點集 Cn為連接符的耗散值 …... i個 n n1 n2 ni 3 目標 目標 初始節(jié)點 ? 解圖： 4 能解節(jié)點 ? 終節(jié)點是能解節(jié)點 ? 若非終節(jié)點有 “ 或 ” 子節(jié)點時 ， 當且僅當其子節(jié)點至少有一能解時 ， 該非終節(jié)點才能解 。 5 不能解節(jié)點 ? 沒有后裔的非終節(jié)點是不能解節(jié)點 。 ? 若非終節(jié)點有 “ 與 ” 子節(jié)點時 ， 當至少有一個子節(jié)點不能解時 ， 該非終節(jié)點才不能解 。 17 雙方的智能活動 ， 任何一方都不能單獨控制博弈過程 ， 而是由雙方輪流實施其控制對策的過程 。節(jié)點代表博弈的格局（即棋局），相當于狀態(tài)空間中的狀態(tài)，反映了博弈的信息， 并且與節(jié)點、或節(jié)點隔層交替出現(xiàn)。 在博弈樹中 ， 相當于博弈雙方輪流擴展其所屬節(jié)點 。 MIN 好招 22 從 MAX方的角度來看 ： 所有屬于 MAX方的節(jié)點都是 或節(jié)點 理由 ： 因為擴展 MAX方節(jié)點時， MAX方可選擇擴展最有利于自己的節(jié)點，只要可擴展的子節(jié)點中有一個對已有利， 則該節(jié)點就對已有利。 24 在博弈樹中 ， 先行一方的初始狀態(tài)對應(yīng)著樹的 根節(jié)點 ， 而任何一方獲勝的最終格局為目標狀態(tài) ，對應(yīng)于樹的 終葉節(jié)點 （ 可解節(jié)點或本原問題 ） 。 25 博弈樹特點 (1)博弈的初始狀態(tài)是初始節(jié)點； (2)博弈樹的 “ 與 ” 節(jié)點和 “ 或 ” 節(jié)點是逐層交替出現(xiàn)的； (3)整個博弈過程始終站在某一方的立場上 ， 所以能使自己一方獲勝的終局都是本原問題 ， 相應(yīng)的節(jié)點也是可解節(jié)點 ， 所有使對方獲勝的節(jié)點都是不可解節(jié)點 。 27 用數(shù)字序列加上一個說明來表示一個狀態(tài)： (3, 2, 1, 1, MAX) 數(shù)字序列 ：表示不同堆中錢幣的個數(shù) 說明 ：表示下一步由誰來分，即取 MAX或 MIN 28 現(xiàn)在取 N＝ 7 的簡單情況 ，并由 MIN先分 注 ： 如果 MAX走紅箭頭的分法，必定獲勝。 即 只能給出幾層走法 ， 然后按照一定的估算辦法 ， 決定走一好招 。 ? 假設(shè) 1毫微秒走一步 ， 約需 10的 145次方年 。 32 在人工智能中可以采用搜索方法來求解博弈問題，下面就來討論博弈中兩中最基本的搜索方法。 假設(shè)由 MAX來選擇走一步棋，問題是： MAX如何來選擇一步好棋 ？ 極大極小過程 34 極大極小過程 ? 極大極小過程是考慮雙方對弈若干步之后 ，從可能的走法中選一步相
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1