root.c

   1 #include <stdlib.h>
   2 #include <limits.h>
   3 #include "shogi.h"
   4
   5 #if defined(USI) || defined(MNJ_LAN) || defined(XBOARD)
   6 static int is_move_ignore( unsigned int move );
   7 #endif
   8
   9 int
  10 make_root_move_list( tree_t * restrict ptree )
  11 {
  12   unsigned int * restrict pmove;
  13   int asort[ MAX_LEGAL_MOVES ];
  14   unsigned int move;
  15   int i, j, k, h, value, num_root_move, iret, value_pre_pv;
  16   int value_best;
  17
  18   pmove = ptree->move_last[0];
  19   ptree->move_last[1] = GenCaptures( root_turn, pmove );
  20   ptree->move_last[1] = GenNoCaptures( root_turn, ptree->move_last[1] );
  21   ptree->move_last[1] = GenDrop( root_turn, ptree->move_last[1] );
  22   num_root_move = (int)( ptree->move_last[1] - pmove );
  23
  24   value_pre_pv = INT_MIN;
  25   value_best   = 0;
  26   for ( i = 0; i < num_root_move; i++ )
  27     {
  28       value = INT_MIN;
  29       move  = pmove[i];
  30
  31       MakeMove( root_turn, move, 1 );
  32       if ( ! InCheck( root_turn )
  33 #if defined(USI) || defined(MNJ_LAN) || defined(XBOARD)
  34            && ! is_move_ignore( move )
  35 #endif
  36            )
  37         {
  38           iret = no_rep;
  39           if ( InCheck(Flip(root_turn)) )
  40             {
  41               ptree->nsuc_check[2]
  42                 = (unsigned char)( ptree->nsuc_check[0] + 1U );
  43               if ( ptree->nsuc_check[2] >= 2 * 2 )
  44                 {
  45                   iret = detect_repetition( ptree, 2, Flip(root_turn), 2 );
  46                 }
  47             }
  48
  49           if ( iret == perpetual_check ) { value = INT_MIN; }
  50           else {
  51             ptree->current_move[1] = move;
  52             value = -search_quies( ptree, -score_bound, score_bound,
  53                                    Flip(root_turn), 2, 1 );
  54
  55             if ( value > value_best ) { value_best = value; }
  56             if ( I2IsPromote(move) ) { value++; }
  57             if ( move == ptree->pv[0].a[1] )
  58               {
  59                 value_pre_pv = value;
  60                 value        = INT_MAX;
  61               }
  62           }
  63         }
  64       UnMakeMove( root_turn, move, 1 );
  65       asort[i] = value;
  66     }
  67
  68   /* shell sort */
  69   for ( k = SHELL_H_LEN - 1; k >= 0; k-- )
  70     {
  71       h = ashell_h[k];
  72       for ( i = num_root_move-h-1; i >= 0; i-- )
  73         {
  74           value = asort[i];
  75           move  = pmove[i];
  76           for ( j = i+h; j < num_root_move && asort[j] > value; j += h )
  77             {
  78               asort[j-h] = asort[j];
  79               pmove[j-h] = pmove[j];
  80             }
  81           asort[j-h] = value;
  82           pmove[j-h] = move;
  83         }
  84     }
  85
  86   /* discard all of moves cause mate or perpetual check */
  87   if ( asort[0] >= -score_max_eval )
  88     {
  89       for ( ; num_root_move; num_root_move-- )
  90         {
  91           if ( asort[num_root_move-1] >= -score_max_eval ) { break; }
  92         }
  93     }
  94
  95   /* discard perpetual checks */
  96   else for ( ; num_root_move; num_root_move-- )
  97     {
  98       if ( asort[num_root_move-1] != INT_MIN ) { break; }
  99     }
 100
 101   for ( i = 0; i < num_root_move; i++ )
 102     {
 103       root_move_list[i].move   = pmove[i];
 104       root_move_list[i].nodes  = 0;
 105       root_move_list[i].status = 0;
 106 #if defined(DFPN_CLIENT)
 107       root_move_list[i].dfpn_cresult = dfpn_client_na;
 108 #endif
 109     }
 110   if ( value_pre_pv != INT_MIN ) { asort[0] = value_pre_pv; }
 111   root_nmove = num_root_move;
 112
 113   if ( num_root_move > 1 && ! ( game_status & flag_puzzling ) )
 114     {
 115       int id_easy_move = 0;
 116
 117       if ( asort[0] > asort[1] + ( MT_CAP_DRAGON * 3 ) / 8 )
 118         {
 119           id_easy_move = 3;
 120           easy_min     = - ( MT_CAP_DRAGON *  4 ) / 16;
 121           easy_max     =   ( MT_CAP_DRAGON * 32 ) / 16;
 122           easy_abs     =   ( MT_CAP_DRAGON * 19 ) / 16;
 123         }
 124       else if ( asort[0] > asort[1] + ( MT_CAP_DRAGON * 2 ) / 8 )
 125         {
 126           id_easy_move = 2;
 127           easy_min     = - ( MT_CAP_DRAGON *  3 ) / 16;
 128           easy_max     =   ( MT_CAP_DRAGON *  6 ) / 16;
 129           easy_abs     =   ( MT_CAP_DRAGON *  9 ) / 16;
 130         }
 131       else if ( asort[0] > asort[1] + MT_CAP_DRAGON / 8
 132                 && asort[0] > - MT_CAP_DRAGON / 8
 133                 && I2From(pmove[0]) < nsquare )
 134         {
 135           id_easy_move = 1;
 136           easy_min     = - ( MT_CAP_DRAGON *  2 ) / 16;
 137           easy_max     =   ( MT_CAP_DRAGON *  4 ) / 16;
 138           easy_abs     =   ( MT_CAP_DRAGON *  6 ) / 16;
 139         }
 140
 141       if ( easy_abs )
 142         {
 143           Out( "\n    the root move %s looks easy (type %d).\n",
 144                str_CSA_move(pmove[0]), id_easy_move );
 145           Out( "    evasion:%d, capture:%d, promotion:%d, drop:%d, "
 146                "value:%5d - %5d\n",
 147                ptree->nsuc_check[1]        ? 1 : 0,
 148                UToCap(pmove[0])            ? 1 : 0,
 149                I2IsPromote(pmove[0])       ? 1 : 0,
 150                I2From(pmove[0]) >= nsquare ? 1 : 0,
 151                asort[0], asort[1] );
 152           easy_value = asort[0];
 153         }
 154     }
 155
 156   return asort[0];
 157 }
 158
 159
 160 #if defined(USI) || defined(MNJ_LAN) || defined(XBOARD)
 161 static int CONV
 162 is_move_ignore( unsigned int move )
 163 {
 164   int i;
 165
 166   for ( i = 0; moves_ignore[i] != MOVE_NA; i += 1 )
 167     {
 168       if ( move == moves_ignore[i] ) { return 1; }
 169     }
 170
 171   return 0;
 172 }
 173 #endif