遊戲樹

维基百科,自由的百科全书
跳转至: 导航搜索

遊戲樹(game tree)是指組合博弈理論中用來表達一個賽局中各種後續可能性的,一個完整的遊戲樹(complete game tree)回有一個起始節點,代表賽局中某一個情形,接著下一層的子節點是原來父節點賽局下一步的各種可能性,依照這規則擴展直到賽局結束。遊戲樹相同於擴展形式的博弈理論中的。 遊戲樹中形成的葉節點代表各種遊戲結束的可能情形,例如井字遊戲會有26,830個葉節點。

一個井字遊戲的遊戲樹範例

遊戲樹在人工智慧的應用相當重要,若要尋找某賽局中最佳的步法的一個方式,是利用極小化極大演算法在遊戲樹中搜尋最佳解[1][2],例如在井字遊戲電腦可以很快速地找到最佳解並做出決策,但是對於象棋圍棋這一類大型的博弈遊戲,列出完整遊戲樹可能使電腦計算能力難以應付,因此對這類遊戲通常會採用部分的遊戲樹(partial game tree)來進行搜尋,典型的部分遊戲樹通常是限制遊戲樹的層數,並剔除不佳的步法(例如自殺),一般而言搜尋的層數越多,能走出較佳步法的機會也越高。

若是兩人遊戲,除了可以用遊戲樹表達之外,也可以用And–or tree表示。

相關條目[编辑]

參考資料[编辑]