中国象棋⼈机对弈搜索算法学习-极⼤极⼩值，负极⼤值，alpha-beta算法
毛孩于震环极⼤极⼩值法
深度搜索（dfs）伪代码
/**
1。 p 为棋盘
2。 d 为规定的搜素最⼤深度，⽐如d层红⽅，d-1层为⿊⽅，d-2层为红⽅...依此类推，可采⽤mod2来判断当前是哪⼀⽅
4。评估棋盘的函数evaluation，当然需要看是哪⼀⽅，若红⽅为机器，⿊⽅为⼈，那么机器（红⽅）做为极⼤（INF），⼈作为极⼩(-INF)，让机器选择最合适的**/ int MiniMax(chessmap p , int d)
{
int bestvalue , value ;
if( Game Over )// 如果游戏结束
return evaluation(p);
if(depth <= 0) // 如果已经到了搜索树叶⼦结点
return evaluation(p);
if( d % 2 == RED) //轮到红⽅
bestvalue = - INF;
else
陈家案bestvalue = INF ;
for(each possible move m)
{
ph值范围MakeMove(m) ; //产⽣第i个局⾯（⼦节点）,p会相应变化
2012年牛奶value = MiniMax(p,d-1);//递归
UnMakeMove(m) ; // 恢复p
if(d % 2 == RED)
bestvalue = max(value ,bestvalue);//取最⼤
else
球面投影bestvalue = max(value ,bestvalue);//取最⼩
}
return bestvalue;
}
负极⼤值法：
负极⼤值法 依然是 极⼤极⼩值法，只是多了个负号。博弈树中⽗结点的值 是 其⼦节点的 负最⼤值。即 ⿊⽅取最⼤，红⽅取 负最⼤，这样⽐较最⼤就⾏了。代码要⽐极⼤极⼩值法要好简洁⼀些。
实现时，需要⽤变量保存每⼀次移动情况，DFS中只需要拥有⼀个最⼤深度的数组即可。结束时，取数组的第⼀个移动，作为当前的最好移动。
Alpha-beta搜索算法
⼝袋的例⼦
⽐如你的死敌⾯前有很多⼝袋，他和你打赌赌输了，因此他必须从中给你⼀样东西，⽽挑选规则却⾮常奇怪： 权益资本成本
每个⼝袋⾥有⼏件物品，你能取其中的⼀件，你来挑这件物品所在的⼝袋，⽽他来挑这个⼝袋⾥的物品。你要赶紧挑出⼝袋并离开，因为你不愿意⼀直做在那⾥翻⼝袋⽽让你的死敌盯着你。 假设你⼀次只能⼀只⼝袋，在⼝袋时⼀次只能从⾥⾯摸出⼀样东西。
很显然，当你挑出⼝袋时，你的死敌会把⼝袋⾥最糟糕的物品给你，因此你的⽬标是挑出“诸多最糟的物品当中是最好的”那个⼝袋。 你很容易把最⼩-最⼤原理运⽤到这个问题上。你是最⼤⼀⽅棋⼿，你将挑出最好的⼝袋。⽽你的死敌是最⼩⼀⽅棋⼿，他将挑出最好的⼝袋⾥尽可能差的物品。运⽤最⼩-最⼤原理，你需要做的就是挑⼀个有“最好的最差的”物品的⼝袋。 假设你可以估计⼝袋⾥每个物品的准确价值的话，最⼩-最⼤原理可以让你作出正确的选择。我们讨论的话题中，准确评价并不重要，因为它同最⼩-最⼤或Alpha-Beta的⼯作原理没有关系。现在我们假设你可以正确地评价物品。
最⼩-最⼤原理刚才讨论过，它的问题是效率太低。你必须看每个⼝袋⾥的每件物品，这就需要花很多时间。
那么怎样才能做得⽐最⼩-最⼤更⾼效呢？
我们从第⼀个⼝袋开始，看每⼀件物品，并对⼝袋作出评价。⽐⽅说⼝袋⾥有⼀只花⽣黄油三明治和⼀辆新汽车的钥匙。你知道三明治更糟，因此如果你挑了这只⼝袋就会得到三明治。事实上只要我们假设对⼿也会跟我们⼀样正确评价物品，那么⼝袋⾥的汽车钥匙就是⽆关紧要的了。 现在你开始翻第⼆个⼝袋，这次你采取的⽅案就和最⼩-最⼤⽅案不同了。你每次看⼀件物品，并跟你能得到的最好的那件物品(三明治)去⽐较。只要物品⽐三明治更好，那么你就按照最⼩-最⼤⽅案来办——去最糟的，或许最糟的要⽐三明治更好，那么你就可以挑这个⼝袋，它⽐装有三明治的那个⼝袋好。
⽐⽅这个⼝袋⾥的第⼀件物品是⼀张20美元的钞票，它⽐三明治好。如果包⾥其他东西都没⽐这个更糟了，那么如果你选了这个⼝袋，它就是对⼿必须给你的物品，这个⼝袋就成了你的选择。
这个⼝袋⾥的下⼀件物品是六合装的流⾏唱⽚。你认为它⽐三明治好，但⽐20美元差，那么这个⼝袋仍旧可以选择。再下⼀件物品是⼀条烂鱼，这回⽐三明治差了。于是你就说“不谢了”，把⼝袋放回去，不再考虑它了。
⽆论⼝袋⾥还有什么东西，或许还有另⼀辆汽车的钥匙，也没有⽤了，因为你会得到那条烂鱼。或许还有⽐烂鱼更糟的东西(那么你看着办吧)。⽆论如何烂鱼已经够糟的了，⽽你知道挑那个有三明治的⼝袋肯定会更好。
我：我的接受程度有下限，给我的太差，我肯定不⼲。
对⽅： 我肯定给你相对最差的，但是我⽆法确定每个⼝袋究竟有哪些物品，我不希望出现某个⼝袋好东西很多，我可给不起。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议