double go::search_uct(int col)
{
  //  9路...21,   13路...30,   19路...45,
  int create_node_limit = (int)(board_size * 2.37);
  HASH_GO *phg = HashGoReadLock();  // 未登録の場合は空き場所を返す。
                                    // 同時にロックがかかる。
  // 1手目に対して2手目がすべての同じ(絶対手)の場合
  if ( phg->flag == 0 ) {
    create_node(col, 1, phg);
  }
  if ( phg->sort_done == 0 ) create_node(col, 0, phg);

  int child_num = phg->child_num;
  int upper_num = get_upper_num(phg->games_sum);
  if ( upper_num < 2         ) upper_num = 2;
  if ( upper_num > child_num ) upper_num = child_num;

  // 今までのMCでの石の存在確率で、未展開の着手をソートしなおす
  if ( ((phg->games_sum+1)&0x7f)==0 ) {
    resort_stone_existing_prob(phg,col,upper_num);
  }
  if ( ((phg->games_sum+1)&0xff)==0 && depth <= 1 && fHistroy ) {
    update_history(phg);
  }

  if ( phg->games_sum > create_node_limit &&
       upper_num > get_upper_num(phg->games_sum-1) &&
       upper_num < child_num ) {
    add_rave_move(phg, col,upper_num);  // raveの点数が高い手を追加
  }

  int select = -1;
  double max_value = -10000;
  for (loop=0; loop<upper_num; loop++) {
    CHILD *pc  = &phg->child[loop];

    double uct_value;
    if ( pc->games ) {
      double logdiv = log(phg->games_sum) / pc->games;
      double uct = 0.31 * sqrt( logdiv );  // UCB1
      uct_value = pc->value + uct;

      // RAVE
      if ( pc->rave_games ) {
        int r_g = pc->rave_games;
        const double K = 100.0;  // 100対戦数ぐらいではraveを優先。
        double rave = 0.31 * sqrt( log(phg->rave_games_sum) / r_g );
        double rave_value = pc->rave_value + rave;
        double beta = sqrt(K / (3 * pc->games + K));
        if ( board_size == 19 ) {
          double W1 = (1.0 / 0.9);    // Fuegoを参考
          double W2 = (1.0 / 20000);
          beta = r_g / (r_g + pc->games * (W1 + W2 * r_g));
        }  
        uct_value = beta * rave_value + (1 - beta) * uct_value;
      }
    } else {  // 未展開ノード
      uct_value = 10000;
    }
    if ( uct_value > max_value ) {
      max_value = uct_value;
      select = loop;
    }
  }

  // 実際に着手
  TE te_uct, *p_te = &te_uct;
  CHILD *pc = &phg->child[select];
  p_te->iti   = pc->iti;
  p_te->color = col;

  add_stone(p_te);
  // super-ko. 同一局面に戻るので無理やり別の手を選ぶ
  if ( is_same_old_position() ) {
    del_stone(p_te);
    select = 最小回数の手;      // 最小回数の手を選んでみる
    pc = &phg->child[select];
    p_te->iti = pc->iti;
    add_stone(p_te);
  }

  update_prob_list_all(p_te->iti,col); // 3x3パターン確率を更新
  if ( IsUseBigPattern() ) {           // 大きなパターン確率を更新
    update_pattern_hash_incremental_all(p_te->iti,col);
  }

  if ( depth > 0 && p_te->iti && path[depth-1] ) {
    int move  = get_361z_from32z(path[depth-1])+1;
    int reply = get_361z_from32z(p_te->iti)+1;
    killer[col-1][move][reply]++;
  }
  path[depth] = p_te->iti;  // 手順を（位置を）記憶
  hash_path[depth] = hashcode64;
  depth++;

  double win = 0;

  if ( pc->games < create_node_limit || 深さ限界? || 連続PASS? ) {
    // 連の死活情報で確率分布を補正
    if ( board_size != 9 ) string_capture_prob_hosei(phg,p_te->iti);
    // 今打った石で死んだ敵連のダメに打つ確率を下げる
    dead_string_board_prob_minus(p_te->iti,col);
    // 死んだ石が動く手を仕留める手を
    capture_horizon_plus(phg, p_te->iti);
    // セキの場合は自爆しないように確率を0に
    set_zero_for_seki(phg);
    set_zero_for_seki_naname(phg);
    // 欠け眼に見える眼形を潰さないように
    not_false_eye_minus(phg);
    // 次に打てば3目中手になる手に対して中手を打たせる
    next_3moku_nakade_shape(phg);
    // 2眼で活きようよもがく石を仕留める
    next_2eye_stop_set(phg);
    plus_not_live_big_eye(phg);

    UnLock(phg->entry_lock);  // プレイアウトのみを並列に行う
    win = -one_simulation_start(FLIP(col));
    go *pgo = &local[thread_id+1];
    if ( pgo->playout_moves > 0 ) {
      TE *p2_te = &pgo->te[0][0];
      HASH_GO *phg2 = HashGoReadLock();
      if ( phg2->flag == 0 ) create_node(FLIP(col), 1, phg2);
      int z = p2_te->iti;
      int n = get_361z_from32z(z)+1;
      if ( z==0 ) n = 0;
      if ( phg2->sort_done ) {
//      PRT("ソート済！別経路同一 depth=%d:",depth); print_path();
        for (n=0;n<phg2->child_num;n++) {
          if ( z == phg2->child[n].iti ) break;
        }
        if ( n==phg2->child_num ) n = -1;  // super-koでありうる。
      }
      if ( n >= 0 ) {
        CHILD *c = &phg2->child[n];
        c->value = (c->games * c->value - win) / (c->games + 1);
        c->games++;    // プレイアウトの初手を更新する
        phg2->games_sum++;  
        // RAVEの更新(彩ではやってない）
//      mc_rave_update(-win,c->it,phg2);
      }
      UnLock(phg2->entry_lock);
    }
    Lock(phg->entry_lock);
  } else {
    if ( fVirtualLoss ) {
      int w = 1 - col;  // 負け、を仮定
      pc->value = (pc->games * pc->value + w) / (pc->games + 1);
      pc->games++;
      phg->games_sum++;
    }

    UnLock(phg->entry_lock);
    win = -search_uct(FLIP(col));
    Lock(phg->entry_lock);

    if ( fVirtualLoss ) {
      int w = 1 - col;
      phg->games_sum--;
      pc->games--;
      if ( pc->games == 0 ) {
        pc->value = 0;
      } else {
        pc->value = ((pc->games+1) * pc->value - w) / pc->games;
      }
    }
  }
  mc_rave_update(win,p_te->iti,phg);  // RAVEの更新

  depth--;
  del_stone(p_te);

  // 勝率を更新
  pc->value = (pc->games * pc->value + win) / (pc->games + 1);
  pc->games++;           // この手を探索した回数
  phg->games_sum++;

  UnLock(phg->entry_lock);
  return win;
}