锐客网

  1. 首页 > 睿知 > it技术 > >

贪心策略java实现代码 贪心策略是什么( 七 )

IT技术算法


（5）display()
通过调用自定义面板类的显示回调函数用于重新显示游戏界面 ， 达到每下一步棋及时更新游戏界面的目的 。
（6）、GetValue(int flag, int num)
估值函数，根据经验把棋局分成只有1颗棋相连 ， 2颗棋相连且两端被封死，2颗棋相连且一端封死另一端活的，2颗棋相连且两端都是活的 ， 同理3颗棋、4颗棋也各自可分3种情况 。不同的情况对应不同的估价值 。估价值的设定是决定计算机一方是否智能的一个关键因素 。
（7）、GetPredictValue(int flag, int num)
对未连成一片但通过再下一颗子就能连成一片的局面进行估值，这在双方下棋的有限步骤内是能产生重要影响的 。如果每局棋仅考虑当前一步，是不可取的 。
（8）、Evaluate(int[][] Array, int x, int y)
根据棋面具体情况以及预先设定的估值函数 ， 对某个点对应的局面进行评估 。由于每次双方只能下一颗棋，所以可以每次取当前局面的所有点中对应估值最大值点的估值作为整个局面的估值 。
（9）、GetGreedNext()
计算机下棋方法1，对应难度等级为简单 ， 采用贪心思想 。每次下棋前在求得最有利点下棋，而是否最有利只是通过一步评估 。算法伪码描述为：
Max取负无穷大
for(行i从0到15)
{
For(列j从0到15)
{
If((i，j)对应的位置无棋)
{
a.假设放上一颗由人控制的棋，求估价值；
b.假设放上一颗由计算机控制的棋，求估价值；
c.取二者中较大值作为(i,j）处的估价值tmp；
d.取tmp与Max较大值赋值给Max.
}
}
}
最终Max对应的点就是当前整个局面中最大的估值点 。至于上述为什么要考虑双方都在该点下棋的情况呢？主要原因为下五子棋是个攻防兼备的过程，不仅要考虑自己对自己最有利，还要考虑对对手最不利，通俗来讲就是在自己赢的时候不能让对手先赢 。
（10）、GetSearchNext(int LookLength)
derectSearch(int [][]Array,boolean who,int deepth)
计算机下棋方法2：直接搜索法,对应难度等级为中等 。
每步棋最多有225个不同下法，若采用直接搜索法则对应的孩子节点有225个（在下棋过程中会逐渐减少），即每层有最多225个节点待扩展，这就决定了直接搜索进行不超过2次—主要原因有两点：
a.采用深度优先搜索需要递归，递归中状态过多可能会爆栈，我们知道递归是用栈机制来实现的；采用宽度优先搜索又需要存储为扩展的节点，这对内存容量要求很高 。
b.不管深搜还是广搜，在时间复杂度为O(N^m)的情况下都是不能接受的 。其中N为当前棋局的待扩展节点，最大225;m为搜索的深度 。
综上所述，在采用直接搜索法时搜索深度不能太深，严格来说是应该控制在2层以内，在计算机运算速度在10^7次每秒的情况下，理论和实验都表明超过2层就会变得很慢且这种趋势成指数级增长 。
直接搜索算法伪代码为
GetSearch(boolean flag ， int deep)
{
如果deep等于0，返回当前棋局估值；
for(行i从0到15)
{
For(列j从0到15)
{
If((i，j)对应的位置无棋)
{
如果轮到计算机下棋，置标志位为2
GetSearch(！flag，deep-1)；
如果轮到人下棋，置标志位为1；
GetSearch(！flag，deep-1)；
}
}
}
}
（11）、GetMinMaxsearchNext(int LookLength)
MinMaxsearch(int [][]Array,boolean who, int deepth)
计算机下棋算法3：极大极小博弈树法,对应难度等级为困难 。五子棋是个博弈游戏 ， 当前在寻找对自己最有利的下棋点时要尽可能保证对对手最不利，这种思想可以用极大极小博弈树

推荐阅读


上一篇：mongodb建立索引树，mongodb如何建立索引

下一篇：包含phpajaxmysql实时的词条