摘要

运筹学无所不包括，无所不能！alpha-go所面对的问题根本上是属于博弈的，当然属于运筹学。博弈发展到凌驾于AI之上，那么有什么能凌驾于博弈呢，也许是运筹学里的看家技术——线形规划——呢。在作者之前博文中，已经介绍过了如何用+Leapms线性规划做排序，这里介绍如何用+Leapms线性规划做博弈，附代码。本博文及所有本作者博文里的文字、模型、代码、结果均为+Leapms原创！

一个简单的博弈问题

以一个简单的火柴问题为例：火柴问题出现在Wayne L. Winston著名的教科书Operations Research: Applications and Algorithms[1][2]中的静态动态规划一章。

首先需要理解博弈问题之所以出现在动态规划里的原因——绝大多数博弈问题其实很容易被转化为递归问题，而所有递归问题都可以用动态规划这样一种带有禁忌节算核心的枚举算法所求解。

所谓博弈问题是指论域之中有一个敌对的智能体，其目标与博弈主体的目标冲突，问题的目的是对博弈的主体（以及敌对智能体）给出最佳决策，以使得博弈主体（以及敌对智能体）能够获取各自的利益最大化。

回到火柴问题：在桌在上有 n 根火柴，“我”（博弈主体）和“对手”（敌对智能体）依次拿1-3根火柴，不许多拿也不许少拿，谁拿到最后一根谁输掉此次游戏。

这个火柴问题可以通过观察知道，如果桌面上有五根火柴，则无论我方如何拿几根火柴，对手都能在下一次使得我方输掉，而且任何4k+5 (k为大于等于0的整数）根火柴的情况都会使得当前将要拿火柴的人输掉。依据这个观察即可做出一个简单的递推程序。但这个不是本博文的目标，本博文的目的是把博弈的核心逻辑用模型的方法“描述性地”“描述”给计算机，让计算机自己推出结果。

博弈的逻辑其实是递归（当有递归原点时）。例如火柴问题可以这样被描述给计算机，当一方拿去1~3根火柴时，就等同于把 n-1 ~ n-3 的情形递归地推给了另一方。这个递归是有原点的，因为所需考虑的火柴数目是逐步减少的，且最终n=3,2,1的情形非常简单，可以直接给出结果。

对这样的问题，可以用(+Leapms)线性规划描述性地建模，并求解。

火柴问题的线型规划建模

设0-1变量 F[i], i=1,…,n 表示当桌面上有i根火柴时候的博弈获利。F[i]=1时表示获益为赢，f[i]=0时表示获益为输。用一般变量x[i]表示当桌面上有i根火柴时候的最优决策，x[i]的含义由其二进制表达来表示，当它的2进制第1位为1时表示可拿1根或查，第2位为1时表示可拿2根或查，第3位为1时表示可拿3根或火柴，当有多个二进制位为1时表示可选择一种情况拿火柴（例如1、2位都为1，表示拿1根或2根都会赢），当x[i]=0时表示此时无论拿1-3根中任意情况对方都有方法使我方输掉。

模型的目标是极大化所有f[i] ( 即：在博弈里叫做敌对智能体是理性智能体，是非常聪明的对手，它总能做出最优决策）：

　　max sum{i=1,…,n} F[i]

定义递归原点的约束，显然：

　　F[1]=0
　　F[2]=1
　　F[3]=1

　　x[1]=0
　　x[2]=1
　　x[3]=2

递归逻辑约束——当我方拿1-3根的三种情况都会导致敌手赢得游戏，则我方最优盈利为0。

　　3-F[i-1]-F[i-2]-F[i-3] >= F[i] | i = 4,…,n //（1）

上面的约束逻辑是：如果我方拿1-3根的三种情况都使得敌方盈利为1，则左侧为零，于是右侧我方获利被约束为0。

下面的约束用来保证正确的决策，即如果我方拿k根火柴导致地方获利为0，则使得d[i]的第k二进制位为1，否则为0。

　　x[i]=(1-F[i-1])+2(1-F[i-2])+4(1-F[i-3])|i=4,…,n //（2）

完整+Leapms模型及其求解

完整+Leapms模型如下(替换数据区的n=20可获得更大n值得解，比如n=1000)：

max sum{i=1,...,n}F[i]
subject to

	3-F[i-1]-F[i-2]-F[i-3]>=F[i]| i=4,...,n   //（1）
	x[i]=(1-F[i-1])+2(1-F[i-2])+4(1-F[i-3])|i=4,...,n  //（2）

	F[1]=0
	F[2]=1
	F[3]=1

	x[1]=0
	x[2]=1
	x[3]=2

where 
	n is a number
	F[i] is a variable of binary|i=1,...,n
	x[i] is a variable of number|i=1,...,n
	
data
	n=20

求解过程（使用load, mip两个命令）：

+Leapms>load
 Current directory is "ROOT".
 .........
        match.leap
        tictac.leap
 .........
please input the filename:match
================================================================
1:  max sum{i=1,...,n}F[i]
2:  subject to
3:
4:      3-F[i-1]-F[i-2]-F[i-3]>=F[i]| i=4,...,n
5:      x[i]=(1-F[i-1])+2(1-F[i-2])+4(1-F[i-3])|i=4,...,n
6:
7:      F[1]=0
8:      F[2]=1
9:      F[3]=1
10:
11:     x[1]=0
12:     x[2]=1
13:     x[3]=2
14:
15:  where
16:     n is a number
17:     F[i] is a variable of binary|i=1,...,n
18:     x[i] is a variable of number|i=1,...,n
19:
20:  data
21:     n=20
22:
================================================================
>>end of the file.
Parsing model:
1D
2R
3V
4O
5C
6S
7End.
..................................
number of variables=40
number of constraints=40
..................................
+Leapms>mip
relexed_solution=15; number_of_nodes_branched=0; memindex=(2,2)
The Problem is solved to optimal as an MIP.
找到整数规划的最优解.非零变量值和最优目标值如下：
  .........
    F2* =1
    F3* =1
    F4* =1
    F6* =1
    F7* =1
    F8* =1
    F10* =1
    F11* =1
    F12* =1
    F14* =1
    F15* =1
    F16* =1
    F18* =1
    F19* =1
    F20* =1
    x2* =1
    x3* =2
    x4* =4
    x6* =1
    x7* =2
    x8* =4
    x10* =1
    x11* =2
    x12* =4
    x14* =1
    x15* =2
    x16* =4
    x18* =1
    x19* =2
    x20* =4
  .........
    Objective*=15
  .........
+Leapms>

上面的结果表示，当n=20时，我方一定会赢，最优决策是取2根火柴。

 讨论

本文给出了火柴博弈问题的线型规划方法，不难看出这种递归建模思路可以被推广到很多棋牌博弈问题以及其他动态规划问题。但是受问题复杂程度不同，模型复杂度会不同。作者稍后考虑给出用+Leapms描述的其他动态规划问题的线性规划模型的例子。

参考文献