博弈树(game tree)简介

admin

博弈树（game tree）是一種特别的根树，它是人工智能范畴一個首要的钻研课题。博弈树可以暗示两名遊戲介入者之間的一場博弈（遊戲），他們瓜代行棋，试圖获胜。

比方，斟酌在 3\times3空中瑜伽, 的九宫格棋盘长进行的“井字棋”遊戲（tic-tac-toe）。

该遊戲中所有计谋的调集可以由一棵庞大的根树来暗示，树中的每一個极點都對應於棋盘的一個結构（configuration）。所谓“棋盘的一個結构”，是在遊戲进程中經由過程標识表记標帜棋盘上的小方格获得的。

但要注重，棋盘上的某些標识表记標帜方案不是結构：4個小方格標识表记標帜为×，1個小方格標识表记標帜为¡的這類环境——因为遊戲介入者是瓜代行棋的，以是永久没法到达如许的標识表记標帜方案。

在此树中，根對應於所有小方格都为空的結构。继而，遊戲者A行棋——她有9個選擇。是以，根有9個孩子极點，每一個孩子极點對應於在9個小方格之一內寫下符号×。斟酌根的一個孩子极點v（棋盘上恰有一個符号×）。在v處，轮到遊戲者B行棋。B有8個選擇，是以v将有8個孩子极點（参看下圖，为简便起见，疏忽掉了對称的环境）。

不竭画下去可以看到這棵树最多有9层，此中偶数层（根地點的最高层记做0层）對應着轮到遊戲者A行棋，而奇数层對應着轮到遊戲者B行棋。有三個同類符号位於统一直線上的极點對應於有一個遊戲者获胜的环境，如许的极點是该根树的叶子。雷同的，所有九個小方格都被標识表记標帜的节點也是叶子节點（它可能對應於無人获胜的环境，如上圖9.1所示）。這就是该遊戲的博弈树，也称作對策树或遊戲树。

固然依照本来的法则，存在着两邊都不获胜的环境（比方上上圖(c)），可是为了简略阐發起见，增长一個前提：當九個小方格都被標识表记標帜且没呈現三個同類符号位於统一直線上的环境時，断定为先手遊戲者A获胜。因而，當遊戲竣事時（即，在叶子极點處）一定有一胜景利者。

叶子极點對應於遊戲的终极状况，将其標识表记標帜为1或0，别离對應於遊戲者A获胜或失败；對付遊素描,戏者B而言，数值的寄义是相反的。

一样地可以阐發获得，對應於轮到A行棋的偶数层极點按照其孩子极點的標号對本身举行標号的举動和逻辑運算“或”一致，是以可以用∨暗示。

因而，该博弈树中的每一個分枝點可以按层数分为∨极點和∧极點。對付一個∨极點而言，若是它有一個子极點標识表记標帜为1，则该极點的標识表记標帜为1；若是它所有的子极點標识表记標帜均为0，则它的標识表记標帜为0。對付一個∧极點而言，若是它有一個子节點標识表记標帜为0，则该极點的標识表记標帜为0；若是它所有的子极點標识表记標帜均为1，则它的標识表记標帜为1。這類树凡是称作與或兆活果實，树（AND–OR tree）。

下面给出该博弈树平分枝點的0-1標识表记標帜的诠释。若是不管遊戲者B若何行棋，都存在着遊戲者A的获胜计谋，则该节點被標识表记標帜为1；而该节點標识表记標帜为0则暗示不管遊戲者A若何行棋，都始终存在着遊戲者B的获胜计谋。處於偶数层极點處的遊戲者A應當選擇頸椎病貼膏,任一将使得她获胜的孩子极點（举行一步行棋）。但是，在奇数层极點處，她的運气是把握在遊戲者B手中的。

當已知博弈树時，因为分枝點的0-1標识表记標帜是由其孩子极點的標识表记標帜决议的，是以可使用树的後序遍從来计较它們。

下面再看另外一個简略的二人博弈：一堆石子共有5颗，甲乙二人轮番從中取石子，每人每次可以取走一颗或两颗，取到最後一颗石子者为负。這個二人博弈的（未標号）博弈树如(a)所示，极點中的数值暗示那時残剩的石子数。面對的結构为0的遊戲者获胜。而(b)中极點中的数值暗示该博弈树的0-1標识表记標帜，根的標识表记標帜为0，暗示乙存在必胜计谋。

固然，先计较全数的博弈树再举行极點標识表记標帜的做法的開消比力大；而α-β剪枝（alpha-beta剪枝）法子可以将其大大低落。