《2048》游戏在线试玩地址:
如何解决《2048》游戏源于外网的一个讨论帖子,而这个帖子则是讨论如何解决该游戏的最早开始,可谓是“缘起”:
What is the optimal algorithm for the game 2048?
关于该游戏的相关内容前面已经写过一些内容:
再探 游戏 《 2048 》 —— AI方法—— 缘起、缘灭(1) —— Firefox浏览器下自动运行游戏篇
========================================
自己为游戏《2048》编写了python版本的运行环境,没多久就又发现网上有其他网友也写了Python版本的《2048》游戏环境,也是出于好奇,想着看看到底是自己写的版本性能更好还是网友写的更好,于是做了一下对比,结果虽然要自己汗颜但还是有所收获的。
网友的实现版本:
https://github.com/moporgic/2048-Demo-Python
=================================================
我所实现的版本:
https://gitee.com/devilmaycry812839668/td-tuple-net-for-2048/tree/master/environ
其中,env_5bits_2048.py为单环境运行版本,env_vec.py为多环境矢量运行版本。
自己实现的这两个环境代码性能比网友的2048-Demo-Python要差上不止几倍速度。
为了更好的进行对比,又新开了一个代码库:
https://gitee.com/devilmaycry812839668/2048-Demo-Python
下面的讨论所用到的算法代码均在该代码库中。
=================================================
在项目https://gitee.com/devilmaycry812839668/2048-Demo-Python中共有4个《2048》游戏环境的实现,分别为文件:
py2048.py
py2048_1.py
py2048_2.py
env_5bits_2048.py
除此之外,还有调用这四个实现进行测试的主文件为main.py。
说明一下,虽然自己也编写过多环境矢量运行的代码env_vec.py,但是在实际运行过程中发现该代码运行效率十分低,远远低于其他版本的实现,因此这里就没有在项目库中将其加入。
py2048.py代码为moporgic编写的原始环境,通过下面的运行测试可以知道其性能是最好的。该版本实现用python的list类型来表示棋盘状态,同时对每一次的移动和所获奖励都是事实计算的,并没有采用缓存的机制。
py2048_1.py代码为移动缓存表方法,其在py2048.py的基础上将所有可能存在的行的移动后状态和所获奖励使用缓存表保存了下来,每一次对棋盘进行移动时部队下次棋盘状态和奖励进行计算而是直接从内存中的缓存表中取出对应行移动后的行和奖励值。与py2048.py最大的不同就是该实现将棋盘变化后的行状态通过预计算的方法保存到了缓存表中,通过对缓存表中数据的读取减少了计算量。但是非常不幸的是通过下面的测试我们知道该种实现并不能提升性能,甚至该版本远不如py2048.py版本。
py2048_2.py代码为移动缓存表改进后的方法。py2048_1.py对移动后的每行计算奖励后对其加和并减去惩罚值才可以得到真正的得分数,在py2048_1.py中每行在一次移动后需要两次循环遍历棋盘状态的各个行,以来读取缓存中移动后的行状态而奖励值,而在py2048_2.py中对移动后行状态及奖励的读取只需要在一次移动后遍历一次棋盘状态的各行即可,减少了对内存的读取。
env_5bits_2048.py 代码为个人设计的缓存表方法,该方法和py2048_1.py类似,都是在每次移动后对棋盘各行进行两次遍历,但与py2048_1.py最大的不同就是这里没有使用list类型来表示棋盘状态而是使用numpy.array,而这个方法也是性能最差的。
对于测试结果个人给出的解释(特指python语言中):
1. 对于计算量较小的操作,使用预计算的方式缓存起来并不划算,因为对内存读取是要耗费较大时间的,而这个时间有可能已经大于了CPU重新计算这个结果所需的时间;
2. 循环操作是比较耗时的,尤其是频繁的循环操作,如果能降低循环操作的次数(使用for遍历的次数)可以一定程度上减少运算时长;
3. 在数据量较小的情况下,对list类型数据进行按索引读取和相等比较操作的性能要远远优于numpy.array类型。
----------------------------------------------------
测试平台:
Ubuntu22.04系统,i7-10700k CPU 工作频率为5.0Ghz
性能测试:
moporgic原始环境万次游戏的平均用时: 73.3795, 总步数:26108430
移动缓存表方法万次游戏的平均用时: 132.7472, 总步数:26115191
移动缓存表改进后方法万次游戏的平均用时:115.6608, 总步数:26129569
个人设计的缓存表方法万次游戏的平均用时:342.4837, 总步数:25777707
-----------------------------------------------------------------------
标签:py2048,缓存,游戏,缘灭,py,2048,移动 From: https://blog.51cto.com/u_15642578/5734623