一个简单的完全信息动态博弈的解答

  版权申明:本文为博主窗户(Colin Cai)原创,欢迎转帖。如要转贴,必须注明原文网址

  http://www.cnblogs.com/Colin-Cai/p/8457744.html 

  作者:窗户

  QQ:6679072

  E-mail:6679072@qq.com

  前几天,看到博客园里有人给了一道博弈:

  事先给定一个正整数N,两个人轮流给出一个2~9的整数。若之前两人所有的数和当前自己报的数,其乘积大于等于N,则赢。

  比如给定数为8,A先报数8,则A赢;给定数为100,A先报9,B报2,A再报9,从而9*2*9>=100,A赢。

  首先想到的是minmax算法,这个是完全信息动态博弈的万能算法。虽然很多时候minmax算法是不实用的,但是这里我们还是试一试,虽然在这个例子里,它依然不实用,但我们要看看为何不实用。

  方法很简单,首先构造完全博弈树。我这里采用C语言写,本想采用lisp(scheme)表达起来最方便,但因为lisp对于很多人可能不是那么友好。

  对于完全博弈树,每一个选择就是一个节点。

  typedef struct _node_t {

          int score;/*分数,这里分数只有两档,WIN/LOSE*/

          struct _node_t* next[8];/*以下代表着8种选择,分别是2~9*/

  } node_t;

  接用指针数组中的偏移来代表所选择的数字的好处是,看上去相对节省一点空间(实际上可能是一样的)。

  我的程序全部使用递归的方法来写,应该相对容易理解。

  首先,建立博弈树是一个前序的过程,先建立树根,然后依次建立各个子树。

  然后,再用minmax来依次标记所有博弈树上节点。

  代码如下:

#include <stdio.h>
#include <stdlib.h>

#define WIN 1
#define LOSE 2

int node_cnt = 0;/*这个值的加入是为了观察博弈树的节点个数*/

typedef struct _node_t {
        int score;/*分数,这里分数只有两档,WIN/LOSE*/
        struct _node_t* next[8];/*以下代表着8种选择,分别是2~9*/
} node_t;
node_t* create_tree(unsigned N);/*建立目标是N的博弈树*/
void clear_tree(node_t* p);/*销毁博弈树*/
void play(node_t *p, unsigned N);/*计算机先手,与人博弈*/

int main(int argc, char **argv)
{
        unsigned N;
        node_t *p;

        /*手动输入目标N*/
        printf("N = ");
        fflush(stdout);
        scanf("%u", &N);

        p = create_tree(N);/*建立目标是N的博弈树*/
        play(p, N);/*计算机先手,与人博弈*/
        clear_tree(p);/*销毁博弈树*/
        return 0;
}

/*递归建立博弈树,current表示当前所有报数的乘积*/
node_t* _create_tree(unsigned N, unsigned current)
{
        node_t *ret;
        unsigned i;

        ret = malloc(sizeof(node_t));
        node_cnt++;
        if(current >= N) {/*如果达到终局条件,则节点为叶子*/
                ret->next[0] = NULL;/*以next[0]为不为NULL来判断次节点是不是叶子节点*/
                return ret;
        }
        /*2~9这8种选择递归构造博弈树,传入第二个参数应为current*(i+2),而不是current*i*/
        for(i=0U;i<8U;i++) {
                ret->next[i] = _create_tree(N, current*(i+2U));
        }
        return ret;
}

/*minmax算法,layer是节点层数,整个博弈树的根的层数为1*/
void mark_tree(node_t* p, int layer)
{
        if(p->next[0] == NULL) {
                if(layer%2 == 0) {/*如果是计算机的节点*/
                        p->score = WIN;
                } else {
                        p->score = LOSE;
                }
        } else {
                int i;
                /*8种选择递归标记*/
                for(i=0;i<8;i++) {
                        mark_tree(p->next[i], layer+1);
                }
                /*标记完了,则依然是minmax决定本节点的score*/
                if(layer%2 == 1) {/*如果是计算机选择的层*/
                        for(i=0;i<8;i++) {
                                if(p->next[i]->score == WIN)
                                        break;
                        }
                        if(i<8) {
                                p->score = WIN;/*子节点上只要有一个是WIN,这个节点就是WIN*/
                        } else {
                                p->score = LOSE;
                        }
                } else {/*如果是人选择的层*/
                        for(i=0;i<8;i++) {
                                if(p->next[i]->score == LOSE)
                                        break;
                        }
                        if(i<8) {
                                p->score = LOSE;/*子节点上只要有一个是LOSE,这个节点就是LOSE*/
                        } else {
                                p->score = WIN;
                        }
                }
        }
}

node_t* create_tree(unsigned N)
{
        node_t* ret;

        ret = _create_tree(N, 1U);/*递归构建博弈树,未标记score*/
        printf("node_cnt = %d\n", node_cnt);
        mark_tree(ret, 1);/*标记score*/
        return ret;
}

/*递归销毁*/
void clear_tree(node_t* p)
{
        if(p->next[0] != NULL) {
                int i;
                for(i=0;i<8;i++)
                        clear_tree(p->next[i]);
        }
        free(p);
}

/*既然博弈树已出,计算机只要每次都把节点往WIN节点上赶就必胜了*/
/*如果计算机不是WIN节点,那么就出2,尽量拖长博,期待人犯错*/
void play(node_t *p, unsigned N)
{
        int layer = 1;
        int i;
        unsigned now = 1U;

        while(1) {
                if(layer%2) {
                        if(p->score == WIN) {
                                for(i=0;i<8;i++) {
                                        if(p->next[i]->score == WIN) {
                                                break;
                                        }
                                }
                                i += 2;
                        } else {
                                i = 2;
                        }
                        printf("computer: %d\n", i);
                        now *= (unsigned)i;
                        i -= 2;
                } else {
                        printf("I: ");
                        fflush(stdout);
                        scanf("%u", &i);
                        now *= (unsigned)i;
                        i = i-2;
                }
                p = p->next[i];
                printf("now: %u\n", now);
                if(now >= N) {
                        printf("GAME OVER\n%s win\n", layer%2?"computer":"I");
                        return;
                }
                layer++;
        }
}

  程序中没有判断malloc是否成功也没判断人的选择是否是2~9,因为这只是一个示例。

  运行一下

# ./a.out
N = 10000
node_cnt = 3271801
computer: 2
now: 2
I: 9
now: 18
computer: 2
now: 36
I: 5
now: 180
computer: 4
now: 720
I: 7
now: 5040
computer: 2
now: 10080
GAME OVER
computer win

  其中,node_cnt是观察博弈树的节点个数,如上,当N到10000的时候,节点个数3271801,非常庞大。

  很显然,这种方法不靠谱。我们必须要想办法压缩博弈树,只压缩到博弈树的节点级,无论是存储还是庞大的计算量,都足以压垮我们的系统。当然,如果有个办法大尺度的压缩博弈树,那么则是可行的。比如经典的博弈游戏抢30,每次报往后1-3,最终谁抢到目标数谁赢,其策略就是让对方面对的剩余数为4的倍数,则己方立于不败之地,这个本质上其实就是一个博弈树的压缩。只是可惜的是,博弈树并没有通用的如此简化的压缩手段,也是为什么像围棋这样复杂的博弈我们到了今天才算是个可能的解决。当然,本题也有大尺度的压缩。

  我们的博弈变形一下:初始的时候目标为N;双方轮流选择;每次假如目标为x,而自己选择的是y(y为2~9的整数),如果y>=x,则胜利,否则,目标变为x/y。很显然,这个博弈和之前提到的博弈完全等价,区别只在于,目标数在不断变化,而不需要去记录之前双方的计数。而且,如果初始目标大于等于2,那么过程中的目标都大于1。带来的方便就是,状态变少,只有一个目标数和一个选择人,只是目标数之前为正整数,这里的目标数为一个正实数(其实是有理数)。如此,为我们的处理带来了方便。

  我们去回忆minmax算法的思想,每次当博弈树某节点面临自己选择的时候,都去选择分数最大的节点。此博弈里,只有输赢两档分数,那么如果轮到己方选择,本节点被标为WIN,那么只需要在子节点中随便找一个WIN的节点即可;而本节点被标为LOSE,就选择一个2,拉长战线,期望对方犯错。那么,我们只需要一个方法推出所有先手必输的正实数N,或者所有先手必胜的N,两边都有无穷多个,可幸运的是,本博弈完全可以把这些正实数归纳进一个个的区间。

  我们试图归纳一下:

  首先,(1,9]是先手必胜点,因为只要选择9就赢了。

  (9,18]是先手必输点,因为这个区间里无论选择2~9里的哪个整数,都会让对方落入(1,9]的先手必胜点。

  (18,36]是先手必胜点,因为这个区间里只要选择2,会让对方落入(2,18]的先手必输点;

  (36,54]是先手必胜点,因为这个区间里只要选择3,会让对方落入(2,18]的先手必输点;

  ....

  (144,162]是先手必胜点,因为这个区间里只要选择9,会让对方落入(2,18]的先手必输点;

  从而(18,162]是先手必胜点。

  (162,324]是先手必输点,无论怎么选择,都会落入(18.162]。

  (324,2916]是先手必胜点。

  ...

  很容易用数学归纳法证明出:

  (18n,9 * 18n]为先手必胜点,(9 * 18n,18n+1]为先手必输点,其中n为非负整数。

  于是整个博弈就规约为对数的运算。于是我们就可以重新写程序如下:

#include <stdio.h>
#include <stdlib.h>

#define WIN 1
#define LOSE 2

void play(unsigned N);

int main(int argc, char **argv)
{
        unsigned N;

        printf("N = ");
        fflush(stdout);
        scanf("%u", &N);
        play(N);
        return 0;
}

typedef struct {
        unsigned p;
        unsigned q;
} num_t;

void div_num(num_t *num, unsigned num2, unsigned *res)
{
        unsigned i;

        i = num->p/(num->q * num2);
        if( num->p > num->q * num2 * i)
                i++;/*区间是左开右闭,不整除则加1*/
        *res = i;
}

void play(unsigned N)
{
        unsigned now = 1U;
        unsigned i;
        unsigned log_num;
        unsigned tmp;
        unsigned power_num[10];
        int layer = 1;
        num_t num, num2;
        unsigned div_res;

        num.p = N;
        num.q = now;

        tmp = 1U;
        for(log_num=0;log_num<10;log_num++) {
                power_num[log_num] = tmp;
                if(N <= tmp) {
                        log_num--;
                        break;
                }
                tmp *= 18U;
        }

        while(1) {
                if(layer%2) {
                        do {
                                div_num(&num, power_num[log_num], &div_res);
                                log_num--;
                        } while(div_res < 2U);
                        if(div_res > 9U) {/*落入先手必输区间,那么给个2拉长等待对手犯错*/
                                i = 2U;
                        } else {/*必胜区间,就这么来吧*/
                                i = div_res;
                        }
                        printf("computer: %u\n", i);
                } else {
                        printf("I : ");
                        fflush(stdout);
                        scanf("%u", &i);
                }
                now *= i;
                num.q = now;
                printf("now: %u\n", now);
                if(now >= N) {
                        printf("GAME OVER\n%s win\n", layer%2?"computer":"I");
                        return;
                }
                layer++;
        }
}

   如此,本质上是用目标数对数级数量的区间去压缩本来是目标数的乘幂级(指数可能1.618,没有证明)数量的博弈树,其运算量的差距可想而知。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏冰霜之地

高效的多维空间点索引算法 — Geohash 和 Google S2

每天我们晚上加班回家,可能都会用到滴滴或者共享单车。打开 app 会看到如下的界面:

76750
来自专栏数据小魔方

Python数据可视化与basemap数据地图系列2——点线图

前一篇介绍了如何使用mpl_toolkits包中的basemap模块制作填充地图,这一节继续分享线图+点图的应用。

34720
来自专栏数据结构与算法

网络最大流算法—EK算法

前言 EK算法是求网络最大流的最基础的算法,也是比较好理解的一种算法,利用它可以解决绝大多数最大流问题。 但是受到时间复杂度的限制,这种算法常常有TLE的风险 ...

56280
来自专栏云时之间

NLP系列学习:常用的语言平滑模型

不过在MIT的NLP课程ppt中总结说有三种模式:Discounting, Interpolationg, Back-off

41290
来自专栏marsggbo

LaTeX IEEE模板

网上有很多LaTeX软件,在线编辑器推荐Overleaf。但是我个人还是更喜欢离线写东西,所以尝试过各种编辑器,例如VSCode等等,这些编辑器都需要自己搭环境...

37720
来自专栏生信小驿站

R语言之可视化⑦easyGgplot2散点图目录

ggplot2.stripchart是一个易于使用的函数(来自easyGgplot2包),使用ggplot2绘图系统和R软件生成条带图。 条形图也被称为一维散点...

12810
来自专栏日常分享

从实例中了解动态规划的基本思想

动态规划,是一种解决棘手问题的方法,它将问题分成小问题,并从解决小问题作为起点,从而解决最终问题的一种方法。

9410
来自专栏生信宝典

R语言学习 - 散点图绘制

散点图 散点图在生物信息分析中是应用比较广的一个图,常见的差异基因火山图、功能富集分析泡泡图、相关性分析散点图、抖动图、PCA样品分类图(后续推出)等。凡是想展...

39470
来自专栏生信宝典

R语言可视化学习笔记之ggridges包

作者:严涛 浙江大学作物遗传育种在读研究生(生物信息学方向)伪码农,R语言爱好者,爱开源。

20640
来自专栏tkokof 的技术,小趣及杂念

HGE系列之管中窥豹(变形网格)

  近来实在忙了一些,一直没有时间继续这个HGE系列,但实际上,时间紧之类的说辞深究起来往往都是有些苍白无力的,尤其当你一心想做成某事时,时间总归是可以挤出来的...

10820

扫码关注云+社区

领取腾讯云代金券