打了一辈子德州,居然输给了新手AI!(中篇)

  • 205
  • A+

打了一辈子德州,居然输给了新手AI!(上篇):https://www.moshike.com/a/347.html 


完美信息博弈类游戏


    对于围棋游戏来说,是一场零和完美信息博弈,这是指在任何时刻,双方玩家都知道前面游戏的全部状态(完美信息),并且在有限步数之后游戏的结果非胜即负(零和)。

    知道了游戏的有限状态,计算机就可以通过暴力枚举的方法来计算后面所有可能的下法,形成一颗巨大的搜索树,这颗搜索树可以列举出在当前状态下所有可能的下法,每个子搜索树都能独立求解,计算机就可以根据计算的结果安排对应的策略,从而达到最终的胜利。

    举个栗子,比如,小明是一个普通中国家庭长大的小孩,在他的一生中,面临着很多个选择,如何才能在未来走向人生巅峰呢?如果可以列举出他未来所有的可能性,把每一步的选择拆解成“子未来”,那么就可以计算出成功胜算最大的选择了。(例子可能不够恰当,理解意思就好,嘻嘻)

小明同学的人生探险


    所以,假设我们有无限大的计算资源,就可以将一局游戏的博弈拆解成一个一个的子博弈(列举出所有的可能性),从而计算出胜算最大的打法,就可以打赢比赛了。但是,以棋类游戏中比较简单的西洋棋来说,它的分支因子大概是40左右,这表示预测之后20步的动作需要计算40的20次方(这是多大,就算是1GHz的处理器,也要计算3486528500050735年),请注意,这还是比较简单的西洋棋。

电脑:“我压力太大了,哇的一声炸开花”


    所以,科学家们利用一些剪枝、搜索等算法以缩减计算范围,从而在有限的游戏时间内找出最佳策略。


不完美信息博弈类游戏

 终于讲到了今天的主角口袋德州。口袋德州(德州扑克)就是很典型的不完美信息博弈类游戏它的策略设置中存在隐藏的信息这类模型也有大量的应用场景,比如谈判、拍卖等等。不完美信息博弈不能如完美信息博弈那样通过分解而进行求解,因为一个子博弈的最佳策略可能依赖于其它尚未得到的子博弈的策略和输出。换句话说,我们无法通过预测到对方下注的多少从而猜测到对方手里的牌是什么,因为也许对方的牌并不好,但他通过下注欺骗你,让你选择弃牌

    所以,这件事对于没心机的计算机是相当困难的,对手第一手就all in了,但是他的牌到底好不好呢?

    因此,当我看到AI在德州上也打败了人类,还些许有些小激动,maybe未来,机器人也可以具有女人的第六感了。那AI到底是如何打败人类的呢?论文中提及和很多很难理解(其实自己也看不太懂,逃)的算法,为了方便理解德州怎么玩,我们以一个简单的博弈模型来举例,试图理解聪明的AI。

我们来设计一个简单的游戏。

游戏玩家有AB两人。A可以抛一次硬币,正反面都只有自己才可以看到,抛完后他有两个选择:sell,卖掉硬币;②play,和B玩游戏。

 if : A选择了sell

   if : 硬币落在正面,A卖掉后得到五毛钱;

   else:硬币落在反面,A卖掉后输掉五毛钱。

 if : A选择了play

   游戏继续,接下来由B来猜硬币是落在正面还是反面:

              if : B猜对了,A赔一元,B赚一元;

              else:B猜错了,A赚一元,B赔一元。


打了一辈子,居然输给了新手AI!(下篇):https://www.moshike.com/a/354.html 




德州扑克
德州扑克