より高い人工知能のヒューマンマシンゲームプログラム実現(複数のアルゴリズム結合)C++ソースコードを含む
19726 ワード
より高い人工知能のヒューマンマシンゲームプログラム実現(複数のアルゴリズム結合)C++ソースコードを含む
本文は恋花蝶が最初に発表したhttp://blog.csdn.net/lanphaday に登録してあるものです.
昨日の夜、Topcoder Marathon Match 6が終わって、私は18位の成績を取って、もう自分がMarathonに4回参加して以来の最高順位で、嬉しい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の2つの関数、上述のアルゴリズムと策略はすべてそこにあります.class MGは碁盤の表示、歩き方の生成と推定値について、class KHとclass HHはそれぞれ殺し屋の啓発と歴史の啓発である.Null Moveは簡単で効率的なアルゴリズムですが、私の実装では比較的簡単で、興味があれば、他の資料を調べることができます. こんなにたくさん話して、このコードの計算能力を言うべきです:6*6の碁盤を例にして、このコードはVC 6のreleaseモードの下でコンパイルして運行して1秒以内に83万個の葉のノードを検索して評価することができて、計算の階層は8-9層です;MiniMaxアルゴリズムで枝切りを行わなければ、3-4階までしか検索できません(テストマシンはいずれもハイパースレッドP 4.0 G+1 Gメモリ).これがアルゴリズムの力でしょう.また、このコードは最適化されていません.私が分からないわけではありません.ただ、时間がありません.見ている友达は許してください.
以下はコードで、VCとG++の上ですべてコンパイルして実行することができます
試合中に書かれているので、コードが乱れていますが、全体的なスタイルはまあまあです.IDEにコピーして見るともっときれいかもしれません.
コードは次のとおりです.
本文は恋花蝶が最初に発表したhttp://blog.csdn.net/lanphaday に登録してあるものです.
昨日の夜、Topcoder Marathon Match 6が終わって、私は18位の成績を取って、もう自分がMarathonに4回参加して以来の最高順位で、嬉しい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の2つの関数、上述のアルゴリズムと策略はすべてそこにあります.class MGは碁盤の表示、歩き方の生成と推定値について、class KHとclass HHはそれぞれ殺し屋の啓発と歴史の啓発である.Null Moveは簡単で効率的なアルゴリズムですが、私の実装では比較的簡単で、興味があれば、他の資料を調べることができます. こんなにたくさん話して、このコードの計算能力を言うべきです:6*6の碁盤を例にして、このコードはVC 6のreleaseモードの下でコンパイルして運行して1秒以内に83万個の葉のノードを検索して評価することができて、計算の階層は8-9層です;MiniMaxアルゴリズムで枝切りを行わなければ、3-4階までしか検索できません(テストマシンはいずれもハイパースレッドP 4.0 G+1 Gメモリ).これがアルゴリズムの力でしょう.また、このコードは最適化されていません.私が分からないわけではありません.ただ、时間がありません.見ている友达は許してください.
以下はコードで、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;
}