围棋落子搜索的数学模型

9.2　围棋落子搜索的数学模型

由于围棋是一种策略性双人棋类游戏，棋手在相互对弈的过程中所下的每一步棋，都是经过深思熟虑、精密决策的结果。在对弈时，棋手不仅要考虑当前所下棋子取得的效果，也要照顾到长远的利益。同时，棋手在下棋的过程中只针对当前盘面进行决策，对于同样的盘面，棋手不用去考虑其中经历的不同步骤。可以说，棋手在下定一手棋后所能获得的收益，只与当前棋盘的状态和即将选取的行动有关，而与以往的历史没有关系。所以，从宏观上看围棋落子的过程应被看成马尔科夫决策过程。

我们知道，任何马尔科夫决策过程都可以用五重组

｛T，S，A（i），p（·｜i，a），r（i，a）｝

表示，围棋落子过程也不例外。

决策时刻T：显然地，围棋是一个有限阶段的决策问题。在有限步对弈后，就能看到决策的结果。设一盘棋的总行棋步数为N，则在［1，N］的时间内，黑白双方交替进行决策。由于黑方先行，所以在奇数时刻黑方进行决策，而在偶数时刻白方进行决策。

状态空间S：现在定义状态。记s＝（B（m），W（n））为状态，其中B（m）为一向量，具体形式（p_b1，p_b2，…，p_bm），描述了到目前为止盘面上所有黑棋的位置；W（n）为一向量，具体形式（p_w1，p_w2，…，p_wn），描述了到目前为止盘面上所有白棋的位置。从前面的解释我们可以知道，状态空间S是相当大的。

可用行动集A（s）：在状态空间上的行动集合｛a＝A（·）｝可以定义为在面对盘面s时所有可下点的集合。如果无可下点可走，则将PASS作为可用行动集。

转移概率p（·｜s，a）：

我们认为，在还有可下点可走的情况下，每一个可下点被执行的概率是等概的。这样的假设前提是下棋者完全没有经验知识。实际上，经验可以指导我们以更高的概率选择更容易获胜的点作为最终的行棋。但是，由于围棋经验的好坏难以定量衡量，因此我们很难给出加入经验后各可行状态的转移概率。所以，我们在建立马尔科夫决策模型时，只简单的考虑从当前状态等概地转移到下一个可行状态的情况。

报酬：R_b表示到目前为止黑棋所占领地域的大小；R_w表示到目前为止白棋所占领地域的大小。围棋落子模型是一类较特殊的马尔科夫决策模型，因为在整个决策过程中所有的报酬不累加为最后的总报酬。只有最后一次决策后双方获得的报酬才是最后的总报酬。但这不影响决策时刻争取高报酬的重要性。