简易象棋 - Githubissues

rainit2006 commented 7 years ago

https://www.zhihu.com/question/20256568 https://www.zhihu.com/question/29472711

rainit2006 commented 7 years ago

算法： 1，Max-Min算法 2， Alpha-Beta算法（对Max-Min算法进行了优化）上述两种算法就是假设我方走最大利益的棋，而对方选择走对方损失最小的棋。

3，Negamax算法(负极大值算法) 是假设我方走最大利益的棋，而对方也选择走对方利益最大的棋。 "负极值(Negamax)算法"是在"极大极小值(MiniMax)算法"提出近20年后才做一个小改进,在程序功能和效率上是没有区别的,唯一不同之处是前者更看起来简洁(后者一会儿取极大,一会儿取极小).你可以发现NegaMax在传递参数时用-alpha,来起到反向取极大(也就是负极大值)的作用,因此不需要一次判断取极大,一次判断取最极小,实际上它也是在"正极大"和"负极大"间相互交替进行,原理是一样而实现手法不同.

MinMax的估值函数Evalution()和Negamax的Evalution()返回值是不一样的。前者return RedScore - BlackScore固定格式;后者return Is红方走子局面? BlackScore - RedScore:RedScore - BlackScore; 且value = -Negamax(...)当红方走子时，返回 -(BlackScore - RedScore) == RedScore - BlackScore; 非红走子，返回 -(RedScore - BlackScore) == BlackScore - RedScore; 这和MinMax所起到的作用是一致的，但比MinMax更简洁。

rainit2006 commented 7 years ago

Alpha-Beta https://www.slideshare.net/NileshBandekar1/alpha-beta-pruning http://blog.codinglabs.org/articles/2048-ai-analysis.html https://www.youtube.com/watch?v=xBXHtz4Gbdo

伪代码例子，更直观一些

function minimax(node, depth)
    return alphabeta(node, depth, -∞, +∞)

function alphabeta(node, depth, α, β)
    if node が終端ノード or depth = 0
        return node の評価値
    if node が自分のノード
        foreach child of node
            α = max(α, alphabeta(child, depth-1, α, β))
            if α ≥ β
                return β // カット
       return α

    else node が対戦者のノード
        foreach child of node
            β := min(β, alphabeta(child, depth-1, α, β))
            if α ≥ β
                return α // カット
        return β

实现的程序代码例子，怎么感觉是negamax风格的算法呢：

int AlphaBeta(int depth, int alpha, int beta) {
　if (depth == 0) {
　　return Evaluate(); //计算当前局面优势。
        //计算方法：我方走的话：我方局势-对方局势。 对方走的话：对方局势-我方局势
　}
　GenerateLegalMoves();
　while (MovesLeft()) {
　　MakeNextMove(); //执行棋盘下一步
　　val = -AlphaBeta(depth - 1, -beta, -alpha);  //因为我方局势和对方局势肯定是取反的，所以加负号。
　　UnmakeMove();  //回退棋步以还原棋盘

      //当val大于当前alpha并小于beta，才是有意义的值
　　if (val >= beta) {
　　　return beta;
　　}
　　if (val > alpha) {
　　　alpha = val;
　　}
　}
　return alpha;
}

rainit2006 commented 7 years ago

オセロゲーム開発 http://uguisu.skr.jp/othello/alpha-beta.html

2048-AI程序算法分析 http://blog.codinglabs.org/articles/2048-ai-analysis.html

rainit2006 commented 7 years ago

http://www.cnblogs.com/speeding/archive/2012/09/20/2694704.html max-min风格的alpha-beta算法

负极大风格的alpha-beta算法

rainit2006 commented 7 years ago

五子棋的AI设计（好文章） http://www.cnblogs.com/goodness/archive/2010/05/27/1745756.html

rainit2006 / Artificial-Intelligence

简易象棋 #1