文档章节

基于强化学习开发人机对弈五子棋游戏

断桥残雪断桥残雪
 断桥残雪断桥残雪
发布于 2016/12/07 17:17
字数 1658
阅读 1445
收藏 11

强化学习主要包括状态空间、价值函数、状态转移三个部分,通过状态之间的转移来得到每个状态的价值,强化学习的目标是使得总价值达到最大。注意,与监督学习不同的是,监督学习通常需要大量的样本来获得有价值的信息,而强化学习却不需要,强化学习可以不需要预先给定任何知识,只需要指定一定的策略和回报,它可以通过不断地尝试和探索,从而可以进行最优的决策,而且随着尝试的次数增多,决策也会越来越最优。(原文在个人微信公众号:deeplearningdigest)

 

今天通过一个实例来具体讲解状态空间、价值函数等概念,例子是编写一个可以人机对弈的五子棋程序。由于完整的棋盘导致状态空间太大,个人PC一时难以训练,因此这里我们使用的是5*5大小的棋盘。加入两个玩家的棋子为X和O,那么赢的情况就是:

  • 同一行或者同一列的棋子相同;

  • 正对角线或反对角线的棋子相同。

 

那么如何定义价值函数呢?首先,我们把棋盘上每一种布局看做一种状态空间,然后每一种状态空间又对应一个价值,我们把所有价值组合起来称为价值空间,价值空间中的每个状态的价值都是要通过价值函数得到。不同状态之间的价值相对大小决定着该状态赢得棋局的概率大小,例如如果状态A的价值大于状态B的价值,那么我们可以认为状态A能赢的概率大于状态B能赢的概率。

 

关于所有状态的价值初始化方法如下:假如我们棋子X为例,那么只要有三个X棋子在一条线上,说明此时棋盘状态表示X已经赢了,那么这个状态的价值就设置为1,也就是说能赢的状态的价值都设置为1;反之,如果有三个O棋子在一条直线上,也就代表X输了,于是此时棋盘状态的价值就设置为0。还有一些状态就是打平手了,我们把所有平局的状态的价值都设置为0;然后还有一些状态是表示棋还没下完,无法判断输赢或平局,这种情况价值设置为0.5,因为我们觉得双方都有可能会赢。

 

那么如何进行状态转移呢?首先状态转移只能是转移到棋盘上的空位置处,这里假设棋盘上的状态只有三种情况,分别是X、O、Empty,状态转移只能是转移到Empty的点。

 

具体玩家指定下一步是到哪一个Empty点的策略是:为了保证能在机器学习的exploration和exploitation二者之间做出一个折中,通常有两种算法,一种是贪婪算法,另外一种是随机算法贪婪算法的目的是选择出此刻最优的Empty点,而随机算法是去探索更多可能性。就好比平常我们在叫外卖时,你可以去点一个之前自己最喜欢的外卖,也可以去尝试一种新的口味,那么第一种情况对应的就是贪婪算法,也就是机器学习中的exploitation;第二种情况对应的就是随机算法,也就是机器学习中的exploration。

 

有了贪婪算法和随机算法过后,就要考虑何时使用贪婪算法和随机算法了,毫无疑问,贪婪算法使用的情况应该要占大多数,因此我们这里设置一个概率阈值0.1,在每一次状态转移之前,通过随机抽样0~1之间的数来采取不同的算法。如果它小于0.1,我们采取随机算法;如果它大于0.1,我们就采取贪婪算法。

 

随机算法的执行很简单,随机在Empty的位置集合里去挑选一个位置即可作为下一步的位置;而贪婪算法的执行过程是遍历所有的Empty位置得到所有的状态,并且计算每个状态的价值,找出其中最大价值的那个状态。与随机算法所不同的是,贪婪算法每一步都会更新价值空间,也就是说对上一个状态空间的价值进行更新,具体的更新公式如下:

 

V(s)=V(s)+alpha*[V(s')-V(s)]

 

其中V表示价值空间,s表示上一个状态,s'表示下一个状态,alpha表示一个类似学习率一样的参数,本文中设置为0.99,这里可以类比梯度下降算法,只不过这里使用的是时间上的差分。

 

按照以上的描述,我们就可以设计一个会下五子棋的Agent了,这个Agent先让它自己与自己对弈一定次数,次数越多,技术越强。它具备了基本的技术以后,就可以进行人机对弈了,并且,随着人机对弈次数越来越多,它也会变得越来越强大了。

 

由于五子棋状态空间较多,计算量较大,而如果设置机器人自身对弈次数较小的话,演示效果不佳;因此这里给出9宫格的演示结果(三个连成一条线就代表赢了),首先让Agent自己与自己下了30000局,然后我来和它下,结果如下图所示,X代表我,O代表Agent:

 

第一步,我走(0,0):

 

 

然后机器走出(1,1):

 

 

第二步,我走(1,0),然后机器走出(2,0):

 

 

第三步,我走出(0,2),然后机器走出(0,1):

 

 

第四步,我走出(2,1),然后机器走出(2,2),最后只剩一个地方我走了(1,2),因此最终达成平局。

 

 

 

从上可以看出,机器以及具备了基本的下棋技能。对于五子棋,演示方式也是和上面的一样。下面给出开发人机对弈的五子棋程序Python代码:

 

 

 

 

 

 

 

 

 

 

 

 

© 著作权归作者所有

断桥残雪断桥残雪
粉丝 52
博文 139
码字总数 94909
作品 0
广州
程序员
私信 提问
在线五子棋

在线五子棋对弈平台,采用JS开发,没使用Flash等富客户端。实现玩家实时对弈,非人机对弈,自动搜索在线网友作为游戏对手:http://yx.sturgeon.mopaas.com/...

redraiment
2014/01/03
561
5
java swing实现五子棋小游戏项目教程

大家好,今天给大家演示一下由Java swing实现的小游戏五子棋,该小游戏完成了五子棋的所有基本功能,可在Java环境下运行,jdk版本不限,是Java学习的很好的参考资料,下面我们来看看项目的运...

明礼馨德的博客
2017/12/20
0
0
利用开源HTML5引擎lufylegend.js结合javascript实现的五子棋人机对弈

前言 本文主要介绍利用开源引擎lufylegend.js开发基于Html5的游戏--五子棋,主要叙述其详细开发过程。 游戏规则 玩过五子棋的都应该知道五子棋的规则,这里就简单介绍其规则。 1、传统五子棋的...

lynnlovemin
2013/09/05
0
0
基于java五子棋游戏开发(含源文件)

获取项目源文件,联系Q:1225467431,指导其它毕设,课设 摘要:五子棋作为中国古代的传统黑白棋种之一,有着广泛的群众基础,是一种老少皆宜的棋类休闲游戏。开发一款五子棋游戏可以使广大棋牌...

切梦刀
01/04
0
0
百行 HTML5 代码实现四种双人对弈游戏

简介: 本文是一个非常具有挑战性的编程,因为 100 行代码,约莫 10000 个字符左右,将实现围棋、五子棋、四子棋和翻转棋四种双人对弈游戏。请注意,这四个对弈游戏不是初级编程者的习作,而...

idea_biu
2012/09/05
148
0

没有更多内容

加载失败,请刷新页面

加载更多

一套基于SpringBoot+Vue+Shiro 前后端分离 开发的代码生成器

一、前言 最近花了一个月时间完成了一套基于Spring Boot+Vue+Shiro前后端分离的代码生成器,目前项目代码已基本完成 止步传统CRUD,进阶代码优化: 该项目可根据数据库字段动态生成 controll...

郑清
12分钟前
2
0
javascript-十六进制随机颜色

<script> // 编写一个函数,获得一个十六进制的随机颜色的字符串(如#20CD4F) // function randomColor(){ // var r = random(0,255).toString(16); // var g = random(0,255).toString(16......

ACKo
14分钟前
2
0
springBoot +mybatis 出现sql 语句在数据库可以查询到,但是赋值到实体类上就没有的情况?

1.不要老是反复查看自己是否写错了,为啥有的能出来有的出不来? 可以查看配置文件中是否配置全: 如果在application.yml 文件中是如下配置: mybatis: mapper-locations: classpath:mapp...

kuchawyz
27分钟前
2
0
正则表达式

一、RegExp对象 进行验证和查找的API 1、创建对象: (1)用/创建(直接量):var reg=/正则/ig,表达式固定不变时使用 (2)用new创建:var reg=new RegExp(‘正则’,‘ig’),表达式需要...

wytao1995
27分钟前
2
0
实战限流(guava的RateLimiter)

关于限流 常用的限流算法有漏桶算法和令牌桶算法,guava的RateLimiter使用的是令牌桶算法,也就是以固定的频率向桶中放入令牌,例如一秒钟10枚令牌,实际业务在每次响应请求之前都从桶中获取...

程序员欣宸
28分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部