より高い人工知能のヒューマンマシンゲームプログラム実現(複数のアルゴリズム結合)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にコピーして見るともっときれいかもしれません.
コードは次のとおりです.
#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;
}