较高人工智能的人机博弈程序实现(多个算法结合)含C++源码

 本文由恋花蝶最初发表于http://blog.csdn.net/lanphaday上，您可以转载、引用、打印和分发等，但必须保留本文完整和包含本声明，否则必究责任。

 到昨天晚上，Topcoder Marathon Match 6结束了，我取得了第18名的成绩，已经是自己参加Marathon四次以来的最好名次啦，高兴ing，这次终于中国人的成绩超过日本人了。因为这次的题目比较偏：写一个人工智能程序和服务器端的程序进行博弈。人机博弈是一门比较专的学科，我们因为英文劣势，大部分中国高手都不能快速的在比赛中学习和实现一些复杂的算法，以致成绩不太如意；我挟之前对这方面的了解，做得还算行，所以把代码公开出来，可以多一点中文方面的资料和源码给大家参考，我也感到非常荣幸。
 比赛的题目请看这里：http://www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=10118&pm=6759 主要的游戏规则也是在这里的，我就不在这里重复啦，主要讲讲我的代码用到了什么算法。麻将虽小，五脏俱全，主要应用的算法有主要变量搜索(PVS)、历史启发(HH)、杀手启发(KH)、Null Move和迭代深化(ID)，可惜后来不够时间实现置换表(TT)，不然可以多一个算法了。代码里还实现了时间控制策略，可以几乎用尽20秒的测试时间，为争取更好的着法提供了保证。还有值得一提的是棋盘表示，我使用了棋盘表、棋子位置表结合的方式来表示，后来发现加上空位表的话，可以加快不少走法生成和估值的速度。反正棋盘表示是一切的基础，一种好的表示方法可以带来很大的性能提升。对于代码，大家注意class SE里的search_move和pvs两个函数，上述的算法和策略都在那里。class MG是关于棋盘表示、走法生成和估值的，class KH和class HH分别是杀手启发和历史启发。Null Move是简单有效的算法，不过我的实现里是比较简单的那种，如果有兴趣，可以查询其它资料。
 
 讲了这么多，应该说一下这份代码的计算能力：以6*6的棋盘为例，这份代码在VC6的release模式下编译运行可以在1秒内搜索并评估83万个叶子节点，计算层次在8-9层；如果用MiniMax算法不进行剪枝，只能搜索到3-4层（测试机器皆为超线程P4 3.0G＋1G内存）。这就是算法的力量吧。另声明一下，本代码未作优化，不代表我不懂，只是没有时间，看的朋友请海涵了。 

下面是代码，在VC和G++上皆可编译、执行

因为比赛期间写的，代码比较乱，但整体的风格还是可以的，复制到IDE上看可能会更好看些

#include  < iostream >
#include  < cstdlib >
#include  < ctime >
#include  < cassert >
#include  < vector >
#include  < algorithm >

using   namespace  std;

typedef unsigned  int  UINT;
typedef UINT MOVE;

const   int  INFINITY  =   100000000 ;
const   int  MAX_DEPTH  =   16 ;

const  UINT max_board_size  =   256 ;
const  UINT max_stones_cnt  =   256 ;

const  UINT empty  =   0 ;
const  UINT my_color  =   1 ;
const  UINT svr_color  =   2 ;

#ifdef WIN32
const  clock_t all_time  =   19200 ;
#else
const  clock_t all_time  =   19200000 ;
#endif

const  UINT check_time_cnt  =   0x00001fff ;

#define  is_empty(x) (x==empty)

#define  opp_color(x) (x==my_color?svr_color:my_color)

int  leaf_cnt  =   0 ;

class  MG
... {
private:
    UINT N_;
    UINT board_[max_board_size];
    UINT stones_[max_stones_cnt];
private:
    void extend(UINT pos, unsigned char* eht, unsigned char* est, UINT& area, UINT& round);

public:
    MOVE move_table[MAX_DEPTH][max_board_size];
    UINT curr_stones_cnt;
    UINT curr_board_size;
    void set_N(int n)...{
        N_ = n;
        curr_board_size = n*n;
        curr_stones_cnt = 0;
        memset(board_, 0, sizeof(UINT)*max_board_size);
        memset(stones_, 0, sizeof(UINT)*max_stones_cnt);
    }
    void make_move(int idx, int color)...{
        board_[idx]=color;
        stones_[curr_stones_cnt++] = idx;
    }
    void unmake_move(int idx)...{
        board_[idx] = empty;
        --curr_stones_cnt;
    }
    inline bool is_game_over()...{return curr_stones_cnt == curr_board_size;}
    UINT gen_move(int depth);
    int evaluatoin(int color);
    int evaluatoin_4_end(int color);
    void print_board()
    ...{
        int cnt = 0;
        for(UINT i = 0; i < curr_board_size; ++i)
        ...{
            if(is_empty(board_[i]))
                cout << "o ";
            else
                cout << ((board_[i]==my_color)?"@ ":"- ");
            ++cnt;
            if(cnt == N_)
            ...{
                cnt = 0;
                cout << endl;
            }
        }
    }
    bool can_move(MOVE move)...{return is_empty(board_[move]);}
    void remove_killers(int depth, int move_cnt, MOVE* killers, int killers_cnt)
    ...{
        for(int i = 0; i < killers_cnt; ++i)
        ...{
            MOVE m = killers[i];
            for(int j = 0; j < move_cnt; ++j)
            ...{
                if(move_table[depth][j] != m)
                    continue;
                for(int k = j+1; k < move_cnt; ++k)
                ...{
                    move_table[depth][k-1] = move_table[depth][k];
                }
                break;
            }
        }
    }
} ;

UINT MG::gen_move( int  depth)
... {
    int cnt = 0;
    for(UINT i = 0; i < curr_board_size; ++i)
    ...{
        if(is_empty(board_[i]))
            move_table[depth][cnt++] = i;
    }
    return cnt;
}

int  MG::evaluatoin( int  color)
... {
    if(curr_stones_cnt+1 == curr_board_size)
    ...{
        for(int i = 0; i < curr_board_size; ++i)
        ...{
            if(is_empty(board_[i]))
            ...{
                board_[i] = color;
                int value = -evaluatoin_4_end(opp_color(color));
                board_[i] = empty;
                return value;
            }
        }
    }
    ++leaf_cnt;
    unsigned char extended_hash_table[max_board_size] = ...{0};
    
    int my_score = 0, svr_score = 0;
    for(UINT i = 0; i < curr_stones_cnt; ++i)
    ...{
        UINT pos = stones_[i];
        if(extended_hash_table[pos])
            continue;
        UINT area = 0, round = 0;
        unsigned char extended_space_table[max_board_size] = ...{0};
        extend(pos, extended_hash_table, extended_space_table, area, round);
        if(board_[pos] == my_color)
        ...{
            my_score += area*area*round;
        }
        else
        ...{
            svr_score += area*area*round;
        }
    }
    if(color == my_color)
        return my_score - svr_score;
    return svr_score - my_score;
}

int  MG::evaluatoin_4_end( int  color)
... {
    ++leaf_cnt;
    unsigned char extended_hash_table[max_board_size] = ...{0};
    
    int my_score = 0, svr_score = 0;
    for(UINT i = 0; i < curr_stones_cnt; ++i)
    ...{
        UINT pos = stones_[i];
        if(extended_hash_table[pos])
            continue;
        UINT area = 0, round = 0;
        unsigned char extended_space_table[max_board_size] = ...{0};
        extend(pos, extended_hash_table, extended_space_table, area, round);
        if(board_[pos] == my_color)
        ...{
            my_score += area*area;
        }
        else
        ...{
            svr_score += area*area;
        }
    }
    if(color == my_color)
        return my_score - svr_score;
    return svr_score - my_score;
}

void  MG::extend(UINT pos, unsigned  char *  eht, unsigned  char *  est, UINT &  area, UINT &  round)
... {
    const UINT round_cnt = 4;
    int is[round_cnt] = ...{-N_, -1, 1, N_};

    ++area;
    eht[pos] = 1;

    for(UINT i = 0; i < round_cnt; ++i)
    ...{
        int new_idx = pos + is[i];
        if(new_idx < 0 || new_idx >= curr_board_size)
            continue;
        if(i == 1 && pos % N_ == 0)
            continue;
        if(i == 2 && new_idx % N_ == 0)
            continue;
        if(is_empty(board_[new_idx]) && (!est[new_idx]))
        ...{
            ++round;
            est[new_idx] = 1;
            continue;
        }
        if(eht[new_idx])
            continue;
        if(board_[new_idx] == board_[pos])
            extend(new_idx, eht, est, area, round);
    }
}

class  HH
... {
private:
    UINT board_[2][max_board_size];
public:
    void reset()...{memset(board_, 0, sizeof(UINT)*max_board_size);}
    void update_value(int depth, int color, MOVE move);
    MOVE get_best(MOVE* move_list, int color, int cnt);
} ;

void  HH::update_value( int  depth,  int  color, MOVE move)
... {
    board_[color-1][move] += (1 << depth);
}

MOVE HH::get_best(MOVE *  move_list,  int  color,  int  cnt)
... {
    int real_color = color-1;
    MOVE* p = move_list;
    int best = board_[real_color][*move_list];
    int best_idx = 0;
    for(int i = 1; i < cnt; ++i)
    ...{
        ++move_list;
        if(board_[real_color][*move_list] <= best)
            continue;
        best = board_[real_color][*move_list];
        best_idx = i;
    }
    MOVE tmp = *p;
    *p = p[best_idx];
    p[best_idx] = tmp;
    return *p;
}

struct  KH_item
... {
    MOVE move;
    int cnt;
} ;

class  less_than
... {
public:
    inline bool operator()(const KH_item& lhs, const KH_item& rhs)
    ...{
       return lhs.cnt < rhs.cnt;
    }
} ;

const   int  max_kh_item_cnt  =   4 ;

class  KH
... {
private:
    KH_item KH_table[MAX_DEPTH][max_kh_item_cnt];
    int cnt_table[MAX_DEPTH];
public:
    void add_to_kh(MOVE move, int depth)
    ...{
        int cnt_mini_idx = 0;
        int cnt_mini = KH_table[depth][0].cnt;
        int i = 0;
        for(i = 0; i < cnt_table[depth]; ++i)
        ...{
            KH_item& tmp = KH_table[depth][i];
            if(tmp.move == move)
            ...{
                ++tmp.cnt;
                return;
            }
            if(tmp.cnt < cnt_mini)
            ...{
                cnt_mini_idx = i;
                cnt_mini = tmp.cnt;
            }
        }
        if(i < max_kh_item_cnt)
        ...{
            KH_table[depth][i].move = move;
            ++(cnt_table[depth]);
        }
        else
        ...{
            KH_item& tmp = KH_table[depth][cnt_mini_idx];
            tmp.move = move;
            tmp.cnt = 1;
        }
    }
    int get_killers(MOVE* killers, int depth)
    ...{
        sort<KH_item*>(KH_table[depth], KH_table[depth]+cnt_table[depth], less_than());
        int i = 0;
        for(i = 0; i < cnt_table[depth]; ++i)
        ...{
            killers[i] = KH_table[depth][i].move;
        }
        return i;
    }
    void reset()
    ...{
        memset(cnt_table, 0, sizeof(int)*MAX_DEPTH);
        memset(KH_table, 0, sizeof(KH_item)*MAX_DEPTH*max_kh_item_cnt);
    }
} ;

class  SE
... {
private:
    MG mg;
    HH hh;
    KH kh;
    int N_;
    int best_move;
    int max_depth_;
public:
    void print_board()
    ...{
        mg.print_board();
    }
    void set_N(int N)
    ...{
        N_ = N;
        used_time = 0;
        best_move = 0xffff;
        mg.set_N(N);
    }
    vector<int> get_best_move()
    ...{
        int row = best_move / N_;
        int col = best_move % N_;
        vector<int> move;
        move.push_back(row);
        move.push_back(col);
        return move;
    }
    void do_move(int row, int col, int color)
    ...{
        mg.make_move(row*N_+col, color);
    }
    void make_sure_best_move_first(MOVE* moves, int cnt, MOVE best_move);
    vector<int> search_move(int max_depth);
    int pvs(int, int, int, int, int);
private:
    clock_t bgn_time;
    clock_t used_time;
    clock_t curr_time_limit;
} ;

void  SE::make_sure_best_move_first(MOVE *  moves,  int  cnt, MOVE best_move)
... {
    for(int i = 0; i < cnt; ++i)
    ...{
        if(moves[i] == best_move)
        ...{
            moves[i] = moves[0];
            moves[0] = best_move;
        }
    }
}

vector < int >  SE::search_move( int  max_depth)
... {
    leaf_cnt = 1;
    bgn_time = clock();    //³õʼʱ¼ä
    //¼ÆËã±¾´ÎʱÏÞ
    UINT leave_space_cnt = mg.curr_board_size - mg.curr_stones_cnt;
    if(leave_space_cnt >= 2)
        leave_space_cnt /= 2;
    curr_time_limit = (all_time - used_time) / leave_space_cnt;
    if(curr_time_limit > all_time || curr_time_limit < 0)
    ...{
        curr_time_limit = 1;
    }

    if(leave_space_cnt < mg.curr_board_size/3)
        curr_time_limit = ((double)curr_time_limit) * (1.4);
    else if(leave_space_cnt < mg.curr_board_size/2)
        curr_time_limit = ((double)curr_time_limit) * (1.3);

    if(N_ > 12)
        curr_time_limit = ((double)curr_time_limit) * (0.9);

    hh.reset();
    kh.reset();
    int md = 0;
    int backup_max_depth = max_depth;
    while(md < max_depth)
    ...{
        ++md;
        max_depth_ = md;
        pvs(md, my_color, 0, -INFINITY, INFINITY);

        if(max_depth >= backup_max_depth)
        ...{
            //»¹ÓÐʱ¼ä£¿
            if(clock()-bgn_time < curr_time_limit)
            ...{
                //²»»á¶ÑÕ»Òç³ö£¿ÔÙËã¶àÒ»²ã
                if(max_depth < MAX_DEPTH - 1)
                    ++max_depth;
            }
        }
        if(clock()-bgn_time >= curr_time_limit)
        ...{
            break;
        }
    }
    clock_t curr_used = clock() - bgn_time;
    used_time += curr_used;    //Ôö¼ÓÓõôµÄʱ¼ä
    return get_best_move();
}

int  SE::pvs( int  depth,  int  color,  int  nullmove,  int  alpha,  int  beta)
... {
    if(mg.is_game_over())
        return mg.evaluatoin_4_end(color);
    if(depth <= 0)
        return mg.evaluatoin(color);
    if((leaf_cnt & check_time_cnt) == 0)    //¼ì²âÊÇ·ñ³¬Ê±
    ...{
        if(clock()-bgn_time >= curr_time_limit)
            return mg.evaluatoin(color);
    }

    // Null Move
    if(depth < max_depth_ && nullmove == 0)
    ...{
        int value = -pvs(depth-2, opp_color(color), 1, -alpha-1, -alpha);
        if(value >= beta)
        ...{
            return value;
        }
    }

    // killer move
    int best;
    MOVE bm = 0xffff;
    MOVE killers[max_kh_item_cnt];
    int killers_cnt = kh.get_killers(killers, depth);

    if(killers_cnt > 0 && depth == max_depth_)
        make_sure_best_move_first(killers, killers_cnt, best_move);

    for(int k = 0; k < killers_cnt; ++k)
    ...{
        MOVE m = killers[k];
        if(!mg.can_move(m))
            continue;
        mg.make_move(m, color);
        best = -pvs(depth-1, opp_color(color), 0, -alpha-1, -alpha);
        if(best >= beta)
        ...{
            if(depth == max_depth_)
                best_move = m;
            kh.add_to_kh(m, depth);
            hh.update_value(depth, color, m);
            mg.unmake_move(m);
            return best;
        }
        else if(best > alpha)
        ...{
            alpha = best;
            bm = m;
        }
        mg.unmake_move(m);
        if((leaf_cnt & check_time_cnt) == 0)    //¼ì²âÊÇ·ñ³¬Ê±
        ...{
            if(clock()-bgn_time >= curr_time_limit)
                break;
        }
    }

    // PVS
    int move_cnt = mg.gen_move(depth);

    if(depth == max_depth_)
        make_sure_best_move_first(mg.move_table[depth], move_cnt, best_move);

    if(killers_cnt == 0 || bm == 0xffff) // bm == 0xffff±íʾkillersÎÞЧ£¡
    ...{
        if(depth == max_depth_)
            bm = mg.move_table[depth][0];
        else
            bm = hh.get_best(mg.move_table[depth], color, move_cnt);
        mg.make_move(bm, color);
        best = -pvs(depth-1, opp_color(color), 0, -beta, -alpha);
        mg.unmake_move(bm);
    }
    else
    ...{
        // remove killers from move_table
        if(killers_cnt > 0)
            mg.remove_killers(depth, move_cnt, killers, killers_cnt);
        MOVE bm_;
        if(depth == max_depth_)
            bm_ = mg.move_table[depth][0];
        else
            bm_ = hh.get_best(mg.move_table[depth], color, move_cnt);
        mg.make_move(bm_, color);
        int best_ = -pvs(depth-1, opp_color(color), 0, -beta, -alpha);
        if(best_ > best)
        ...{
            best = best_;
            bm = bm_;
        }
        mg.unmake_move(bm_);
    }
    for(int i = 1; i < move_cnt; ++i)
    ...{
        if(best >= beta)
            break;
        if(best > alpha)
            alpha = best;

        if((leaf_cnt & check_time_cnt) == 0)    //¼ì²âÊÇ·ñ³¬Ê±
        ...{
            if(clock()-bgn_time >= curr_time_limit)
                break;
        }

        MOVE m = hh.get_best(mg.move_table[depth]+i, color, move_cnt-i);
        mg.make_move(m, color);
        int value = -pvs(depth-1, opp_color(color), 0, -alpha-1, -alpha);
        if(value > alpha && value < beta)
        ...{
            best = -pvs(depth-1, opp_color(color), 0, -beta, -value);
            bm = m;
        }
        else if(value > best)
        ...{
            best = value;
            bm = m;
        }
        mg.unmake_move(m);
    }
    if(depth == max_depth_)
        best_move = bm;
    if(best >= alpha)
    ...{
        kh.add_to_kh(bm, depth);
        hh.update_value(depth, color, bm);
    }
    return best;
}

class  PseudoTonga
... {
public:
    vector<int> move(int row, int col);
    vector<int> init(int N, int row, int col);
private:
    int N_;
    SE se;
    void do_move(int row, int col, int color);
} ;

vector < int >  PseudoTonga::init( int  N,  int  row,  int  col)
... {
    N_ = N;
    se.set_N(N);
    
    int r = 0, c = 0;

    if(row >= 0 || col >= 0)
    ...{
        return move(row, col);
    }
    
    vector<int> move;
    r = c = N/2;
    do_move(r, c, my_color);
    move.push_back(r);
    move.push_back(c);
    cout << "player: row = " << move[0] << ",  col = " << move[1] << "; " ;
    return move;
}

vector < int >  PseudoTonga::move( int  row,  int  col)
... {
    do_move(row, col, svr_color);
    cout << "server: row = " << row << ",  col = " << col << "; ";
    vector<int> move;
    int d = 3;
    move = se.search_move(d);
    do_move(move[0], move[1], my_color);
    cout << "player: row = " << move[0] << ",  col = " << move[1] << "; ";
    cout << "leaf count is " << leaf_cnt << endl;
    return move;
}

void  PseudoTonga::do_move( int  row,  int  col,  int  color)
... {
    se.do_move(row, col, color);
}

int main()
{
 PseudoTonga pt;
 pt.init(6, 2, 2);
 pt.move(2,4);
 return 0;
}