/*
 * $Id: pds_nagai.cpp,v 1.22.2.3 2005/04/27 09:15:20 miwa Exp $
 */

#include "stdafx.h"
#ifdef HAVE_CONFIG_H
#include "config.h"
#endif /* HAVE_CONFIG_H */

#include "stdafx.h"

#include "search.h"

#include "pn.h"
#include <iostream>
#include <cmath>

void print_kind(const Shogiban* s); //debug
string movestring(const Move& m); // debug

const bool STORE_SEARCH_HASH = true;

const int TSUMAZU = 255;
const int PN_MAX = 255;
//const int DN_MAX = 255;
const int DN_MAX = 65535;
const int MAX_DEPTH = 100;

static TpTable* _tptable;

//static ShogibanHashKey _key_sequence[MAX_DEPTH+10];  
//static Move _move_sequence[MAX_DEPTH+10];

const static NumInhands INHAND_MIN = NumInhands(0, 0, 0, 0, 0, 0, 0);
const static NumInhands INHAND_MAX = NumInhands(2, 2, 4, 4, 4, 4, 18);

bool is_adjacent(r_coord_t rc);
int remove_senseless_moves(List<Move>& ml, side_t turn);

// 敵玉が自由に動けない升のビットを求める
static unsigned int eking_covered_mask(const Shogiban* ban, side_t turn)
{
  side_t eside = enemy_side(turn);
  const Masu* target = ban->ou_masu(eside);
  unsigned int freesq = 0;
  for (const Kiki* k = target->from_kiki_begin();
       k != target->from_kiki_end();
       k = k->next_kiki_from_same_masu()) {
    const Masu* masu = k->kiki_to_masu();
    if (masu->has_kiki(turn)) continue; // 自分のききがある
    if (masu->stat() != 0 && !masu->can_catch(eside)) continue; // 敵の駒がある
    freesq |= 1 << get_happou_no(times_side(masu - target, turn));
  }
  unsigned int covered = ~freesq;
  return covered;
}

static bool lookup_hash(const int depth, const ShogibanHashKey& key, 
			side_t attack_side,
			int* tsumi_depth, 
			int* dyn_eval_pn, 
			int* dyn_eval_dn, 
			NumInhands* sente_atk_inhands,
			Move* pmove = NULL)
{
  //  *dyn_eval = 1;  return false;
  *dyn_eval_pn = 1;
  *dyn_eval_dn = 1;
  //  return false;

  bool t_hit = _tptable->retrieve_checkmate_info(key, attack_side, dyn_eval_pn,
						 dyn_eval_dn, tsumi_depth, 
						 sente_atk_inhands, pmove);
  if ((*dyn_eval_pn) == 0)  (*tsumi_depth) += depth;

  if (t_hit) return true;

  // ハッシュにない場合
  *dyn_eval_pn = 1;
  *dyn_eval_dn = 1;
  return false;
}

static NumInhands
calc_gote_inhands(const Shogiban* ban, NumInhands sente_inhands, 
		  NumInhands sente_atk_inhands) 
{
  NumInhands gote_inhands(ban->mochigoma_num(GOTE, 1),
			  ban->mochigoma_num(GOTE, 2),
			  ban->mochigoma_num(GOTE, 3),
			  ban->mochigoma_num(GOTE, 4),
			  ban->mochigoma_num(GOTE, 5),
			  ban->mochigoma_num(GOTE, 6),
			  ban->mochigoma_num(GOTE, 7));
  assert(sente_atk_inhands.Eq_or_gt(sente_inhands));
  if (sente_atk_inhands == sente_inhands) 
    return gote_inhands;
  for (int i = 1; i <= 7; i++) {
    int diff = sente_atk_inhands.Num(i) - sente_inhands.Num(i);
    assert(diff >= 0);
    for (int j = 0; j < diff; j++)
      gote_inhands.Decrement(i);
  }
  return gote_inhands;
}


static ShogibanHashKey 
calc_min_inhands(const Shogiban* ban, const ShogibanHashKey & key, 
		 side_t attack_side, NumInhands atk_inhands)
{
  if (atk_inhands == INHAND_MAX) return key;
  NumInhands tmp_inhands = key.inhand();
  if (attack_side == SENTE) {
    if (tmp_inhands.Eq_or_gt(atk_inhands)) {
      tmp_inhands = atk_inhands;
    }
  } else {
    NumInhands gote_inhands(ban->mochigoma_num(GOTE, 1),
			    ban->mochigoma_num(GOTE, 2),
			    ban->mochigoma_num(GOTE, 3),
			    ban->mochigoma_num(GOTE, 4),
			    ban->mochigoma_num(GOTE, 5),
			    ban->mochigoma_num(GOTE, 6),
			    ban->mochigoma_num(GOTE, 7));
    if (gote_inhands != atk_inhands && gote_inhands.Eq_or_gt(atk_inhands) &&
	tmp_inhands != INHAND_MAX) {
      for (int i = 1; i <= 7; i++) {
	int diff = ban->mochigoma_num(GOTE, i) - atk_inhands.Num(i);
	for (int j = 0; j < diff; j++)
	  tmp_inhands.Increment(i);
      }
    }
  }
  return ShogibanHashKey(key.key0(), key.key1(), tmp_inhands);
}

static int defense(const l_thread_id tid, 
		   Move _move_sequence[], ShogibanHashKey _key_sequence[],
		   int& countdown, const int depth, 
		   int& pn, int& dn, 
		   const ShogibanHashKey& key, Shogiban* ban, 
		   NumInhands & atk_inhands,
		   List<Move>& best_move_list);

//-----------------------------------------------------------------
// 攻め方
//-----------------------------------------------------------------
static int attack(const l_thread_id tid, 
		  Move _move_sequence[], ShogibanHashKey _key_sequence[],
		  int& countdown, int depth, 
		  int& pn, int& dn, 
		  const ShogibanHashKey& key, Shogiban* ban, 
		  NumInhands & atk_inhands,
		  List<Move>& best_move_list)
{
  //  atk_inhands = INHAND_MAX;

  if (depth >= MAX_DEPTH-2) {
    pn = TSUMAZU;
    dn = 0;
    return -2;
  }

  if (countdown-- < 0 || Searcher::is_search_aborted()) return -1;
  side_t turn = ban->turn();
  side_t attack_side = turn;

  if (ban->ou_masu(enemy_side(turn))->has_kiki(turn)) {
    pn = 0;
    dn = DN_MAX;
    atk_inhands = INHAND_MIN;
    return depth; // 相手の玉を取れる
  }
    
  int dyn_eval, tsumi_depth, dyn_eval_dn;
  Move tmp_move;
  NumInhands a_inhands;
  if (lookup_hash(depth, key, attack_side, &tsumi_depth, &dyn_eval, 
		  &dyn_eval_dn, &a_inhands, &tmp_move)) {
    if (dyn_eval == 0) {
      best_move_list.clear();
      best_move_list.push_back(tmp_move);
      assert(Searcher::is_legal_move(ban, tmp_move));
      assert(tmp_move != Pass);  // note) need to debug
      pn = 0;
      dn = DN_MAX;
      if (attack_side == SENTE) {
	atk_inhands = a_inhands;
      } else {
	atk_inhands = calc_gote_inhands(ban, key.inhand(), a_inhands);
      }
      //      assert(tsumi_depth % 2 == 1);
      return tsumi_depth;
    }
    if (dyn_eval_dn == 0) {
      pn = TSUMAZU;
      dn = 0;
      return -2;
    }
    if (dyn_eval >= pn && dyn_eval_dn >= dn) {
      pn = dyn_eval;
      dn = dyn_eval_dn;
      return -1;
    }
  } else {
    if (Searcher::check_immediate_tsumi(tid, ban, best_move_list)) {
      pn = 0;
      dn = DN_MAX;
      Move best_move = best_move_list.front();
      atk_inhands = INHAND_MIN;
      if (best_move.is_uchi()) atk_inhands.Increment(best_move.kind()/2);
      ShogibanHashKey tmp_key = 
	calc_min_inhands(ban, key, attack_side, atk_inhands);
      //      tmp_key = ShogibanHashKey(key.key0(), key.key1(), INHAND_MAX);
      /*
      if (key != tmp_key) {
	print_kind(ban);
	cout << "best_move = " << movestring(best_move) << " ";
	cout << "tmp_inhands = ";
	for (int i = 1; i <= 7; i++) cout << tmp_key.inhand().Num(i) << " ";
	cout << endl;
      }
      */
      //_tptable->store_checkmate_info(key, attack_side, 0, DN_MAX, 
      _tptable->store_checkmate_info(tmp_key, attack_side, 0, DN_MAX, 
				     1, best_move);
      if (STORE_SEARCH_HASH)
      	_tptable->store_search_info(key, 9999, 100000-(depth+1), 
				    SearchInfo::EXACT, best_move);
      return depth + 1;
    }
  }

  // 循環を避けるため
  _tptable->store_checkmate_info(key, attack_side, pn, dn, 0, Pass);

  _key_sequence[depth] = key;

  //  List<Move> ml;
  LL(Move, ml, tid);
  const Masu* enemy_ou_masu = ban->ou_masu(enemy_side(turn));
  int nmoves = Searcher::generate_effect_to(ban, ml, ban->ou_masu(enemy_side(turn))->pos(), 0xffff, false);

  LL(Move_and_Info, mil, tid);
  for (List<Move>::const_iterator i = ml.begin(); i != ml.end(); i++) {
    ShogibanHashKey key1 = key;
    key1.update(ban, *i);
    Move_and_Info mi(*i, key1);
    /*
    const Masu* tmasu = ban->masu(i->to());
    int my_kiki_num = tmasu->total_kiki_num(turn);
    int e_kiki_num = tmasu->total_kiki_num(enemy_side(turn));
    if (i->is_sashi()) my_kiki_num--;
    //    if (i->is_uchi() && e_kiki_num > my_kiki_num) {
    if (e_kiki_num > my_kiki_num+1) {
      //      cout << movestring(*i) << " ";
      mi.is_mudaai = true;
    }
    */
    /*
    if (i->is_uchi()) {
      if (i->kind() == 2 || i->kind() == 4 || i->kind() == 12) {
	int ex = enemy_ou_masu->retsu();
	int ey = enemy_ou_masu->gyou();
	const Masu* tmasu = ban->masu(i->to());
	int tx = tmasu->retsu();
	int ty = tmasu->gyou();
	int distance = max(abs(ex - tx), abs(ey - ty));
	if (distance >= 3) {
	  //	  print_kind(ban);
	  //	  cout << movestring(*i) << endl;
	  mi.is_mudaai = true;
	}
      }
    }
    */
    mil.push_back(mi);
  }

  while(1) {
    // 反証数の sum, 証明数の min を計算
    List<Move_and_Info>::iterator best = mil.begin();
    int dyn_dn_sum = 0;
    for (List<Move_and_Info>::iterator i = mil.begin(); i != mil.end(); i++) {
      bool hit = false;
      if (i->pn == -1) {
	NumInhands a_inhands;
	hit = lookup_hash(depth+1, i->key, attack_side, &(i->tsumi_depth), 
			  &(i->pn), &(i->dn), &a_inhands);
	if (i->pn == 0) {
	  if (attack_side == SENTE) {
	    i->atk_inhands = a_inhands;
	  } else {
	    ban->s_move(i->move); // 後手の持ち駒が変わる可能性があるので
	    i->atk_inhands = calc_gote_inhands(ban, i->key.inhand(),a_inhands);
	    ban->s_reverse(); // ほんとは move しないで計算可能
	  }
	}
      }
      dyn_dn_sum += i->dn;
      if (!hit && dyn_dn_sum > 1 && i->is_mudaai) dyn_dn_sum--;
      if (i->pn < best->pn)
	best = i;
      if (best->pn == 0) {
	atk_inhands = best->atk_inhands;
	if (best->move.is_uchi()) {
	  if (atk_inhands != INHAND_MAX)
	    atk_inhands.Increment(best->move.kind() / 2);
	} else {
	  const Masu* masu = ban->masu(best->move.to());
	  if (masu->stat() != 0) {
	    int kind2 = masu->placed_koma()->kind() / 2;
	    if (atk_inhands.Num(kind2) > 0)
	      atk_inhands.Decrement(kind2);
	  }
	}
	/*
	print_kind(ban);
	cout << "tsumi_move = " << movestring(best->move) << endl;
	cout << "inhands   = ";
	for (int i = 1; i <= 7; i++) cout << key.inhand().Num(i) << " ";
	cout << endl;
	cout << "a_inhands = ";
	for (int i = 1; i <= 7; i++) cout << atk_inhands.Num(i) << " ";
	cout << endl;
	*/
	break;
      }
    }
    if (dyn_dn_sum > DN_MAX) dyn_dn_sum = DN_MAX;

    // 王手がない
    if (best == mil.end() || dyn_dn_sum == 0) {
      pn = TSUMAZU;
      dn = 0;
      _tptable->store_checkmate_info(key, attack_side, pn, dn, 0, Pass);
      return -2;
    }

    // 詰み or Terminate
    if (best->pn == 0 ||
	(dn <= dyn_dn_sum && pn <= best->pn)) {
      pn = best->pn;
      dn = dyn_dn_sum;
      if (pn == 0) {
	ShogibanHashKey 
	  tmp_key = calc_min_inhands(ban, key, attack_side, atk_inhands);
	/*
	if (key != tmp_key) {
	  print_kind(ban);
	  cout << "tmp_inhands = ";
	  for (int i = 1; i <= 7; i++) cout << tmp_key.inhand().Num(i) << " ";
	  cout << endl;
	}
	*/
	//_tptable->store_checkmate_info(key, attack_side, 0, DN_MAX, best->tsumi_depth - depth, best->move);
	_tptable->store_checkmate_info(tmp_key, attack_side, 0, DN_MAX, best->tsumi_depth - depth, best->move);
	if (STORE_SEARCH_HASH)
	  _tptable->store_search_info(key, 9999, 100000-best->tsumi_depth, SearchInfo::EXACT, best->move);
	assert(best->tsumi_depth >= 0);
	if (best_move_list.empty())
	  best_move_list.push_back(best->move);
	//	assert(best->tsumi_depth % 2 == 1);
	return best->tsumi_depth;
      }
      _tptable->store_checkmate_info(key, attack_side, pn, dn, 0, Pass);
      return -1;
    }

    dyn_eval = max(dyn_eval, best->pn);

    // select_child
    //   証明数が最小のノードを選ぶ
    //   ただし、このノードの証明数より小さいものは同一視
    List<Move_and_Info>::iterator child = mil.begin();
    for (List<Move_and_Info>::iterator i = mil.begin(); i != mil.end(); i++) {
      int cpn = i->pn;
      assert(cpn != 0);
      cpn = max(dyn_eval, cpn);
      if (cpn <= child->pn) {
	if (cpn < child->pn)
	  child = i;
	else {
	  int cdn = i->dn;
	  if (cdn < child->dn)
	    child = i;
	}
      }
    }

    int cpn = child->pn;
    int cdn = child->dn;

    if (dn > dyn_dn_sum &&
	(cdn <= cpn || pn <= best->pn)) {
      cdn++;
    } else {
      cpn++;
    }

    const Move& move = child->move;
    _move_sequence[depth] = move;
    ban->s_move(move);
    LL(Move, enemy_bestml, tid);
    NumInhands a_inhands(INHAND_MAX);
    int tsumi_depth = defense(tid, _move_sequence, _key_sequence, countdown,
			      depth+1, cpn, cdn, child->key, ban, 
			      a_inhands, enemy_bestml);

    //    if (depth == 0) {
    //      cout << movestring(move) << " cpn = " << cpn << " cdn = " << cdn << endl;
    ban->s_reverse();
    if (tsumi_depth >= 0) {
      // 詰みが見つかった場合は、mil の先頭に持ってきたほうが速くなりそう（反証明でも同じ）
      best_move_list = enemy_bestml;
      best_move_list.push_front(move);
      assert(tsumi_depth <= 255);
      child->tsumi_depth = tsumi_depth;
      child->atk_inhands = a_inhands;
    }

    child->pn = cpn;
    child->dn = cdn;
    if (countdown < 0 || Searcher::is_search_aborted()) return -1;
  }
}

//-----------------------------------------------------------------
// 玉方
//-----------------------------------------------------------------
static int defense(const l_thread_id tid, 
		   Move _move_sequence[], ShogibanHashKey _key_sequence[],
		   int& countdown, const int depth, 
  		   int& pn, int& dn, 
  		   const ShogibanHashKey& key, Shogiban* ban, 
		   NumInhands & atk_inhands,
  		   List<Move>& best_move_list)
{
  atk_inhands = INHAND_MAX;

  if (depth >= MAX_DEPTH-2) {
    pn = TSUMAZU;
    dn = 0;
    return -2;
  }

  if (countdown-- < 0 || Searcher::is_search_aborted()) return -1;

  side_t turn = ban->turn();
  side_t attack_side = enemy_side(turn);

  bool cap_ou = false;
  const Masu* atk_ou_masu = ban->ou_masu(attack_side);
  if (atk_ou_masu != (Masu*)-1) {
    if (atk_ou_masu->has_kiki(turn))  // 相手の玉を取れる
      cap_ou = true; 
  }
  if (!ban->ou_masu(turn)->has_kiki(attack_side) || // 王手がかかっていない
      cap_ou) {  // 相手の玉を取れる
    pn = TSUMAZU;
    dn = 0;
    _tptable->store_checkmate_info(key, attack_side, pn, dn, 0, Pass);
    return -2; // 絶対不詰
  }

  int dyn_eval, tsumi_depth, dyn_eval_dn;
  Move tmp_move;
  NumInhands a_inhands;
  if (lookup_hash(depth, key, attack_side, &tsumi_depth, &dyn_eval, 
		  &dyn_eval_dn, &a_inhands, &tmp_move)) {
    if (dyn_eval == 0) {
      pn = 0;
      dn = DN_MAX;
      if (attack_side == SENTE) {
	atk_inhands = a_inhands;
      } else {
	atk_inhands = calc_gote_inhands(ban, key.inhand(), a_inhands);
      }
      return tsumi_depth;
    }
    if (dyn_eval_dn == 0) {
      pn = TSUMAZU;
      dn = 0;
      return -2;
    }
    if (dyn_eval >= pn && dyn_eval_dn >= dn) {
      pn = dyn_eval;
      dn = dyn_eval_dn;
      return -1;
    }
  }

  // 循環を避けるため
  _tptable->store_checkmate_info(key, attack_side, pn, dn, 0, Pass);

  _key_sequence[depth] = key;

  // 王手を防ぐ手の生成
  //  List<Move> ml;
  LL(Move, ml, tid);
  int nmoves = Searcher::generate_king_defense_moves(ban, ml);

  // Move_and_Info のリストを作成 （何度も使うから）
  LL(Move_and_Info, mil, tid);
  LL(Move_and_Info, mil_muda, tid);
  for (List<Move>::const_iterator i = ml.begin(); i != ml.end(); i++) {
    ShogibanHashKey key1 = key;
    key1.update(ban, *i);
    // 無駄合いかどうか？
    Move_and_Info mi(*i, key1);

    if (i->is_uchi()) {
      int kiki_num = 
	ban->masu(i->to())->total_kiki_num(turn)
	- ban->masu(i->to())->total_kiki_num(enemy_side(turn));
      if (kiki_num < 0) {
	mi.is_mudaai = true;
      }
    }

    mil.push_back(mi);
  }

  int max_tsumi_depth = -1;
  while(1) {
    // 証明数の sum, 反証数の min を計算
    List<Move_and_Info>::iterator best = mil.begin();
    int dyn_pn_sum = 0;
    atk_inhands = INHAND_MIN;
    for (List<Move_and_Info>::iterator i = mil.begin(); i != mil.end(); i++) {
      bool hit = false;
      if (i->pn == -1) {
	NumInhands a_inhands;
	hit = lookup_hash(depth+1, i->key, attack_side, &(i->tsumi_depth), 
			  &(i->pn), &(i->dn), &a_inhands);
	if (i->pn == 0) {
	  if (attack_side == SENTE) {
	    i->atk_inhands = a_inhands;
	  } else {
	    i->atk_inhands = calc_gote_inhands(ban, i->key.inhand(),a_inhands);
	  }
	}
      }
      dyn_pn_sum += i->pn;
      if (!hit && dyn_pn_sum > 1 && i->is_mudaai) dyn_pn_sum--;
      if (i->dn < best->dn)
	best = i;
      if (i->pn == 0) {
	//	atk_inhands = atk_inhands.Or(i->atk_inhands);  // max??
	if (i->atk_inhands.Eq_or_gt(atk_inhands))
	  atk_inhands = i->atk_inhands;
	// 一番長い詰み
	if (i->tsumi_depth > max_tsumi_depth) {
	  max_tsumi_depth = i->tsumi_depth;

	  if (best_move_list.front() != i->move) {
	    best_move_list.clear();
	    best_move_list.push_back(i->move);
	  }

	}
      }
      if (best->dn == 0) break;
    }
    if (dyn_pn_sum > TSUMAZU) dyn_pn_sum = TSUMAZU;

    // 詰み
    if (best == mil.end() || dyn_pn_sum == 0) {
      const Move& last_move = _move_sequence[depth-1];
      if (last_move.is_uchi() && last_move.kind() == 14) {
	if (max_tsumi_depth <= depth+1) {
	  //	  print_kind(ban);
	  // 打歩詰め
	  pn = TSUMAZU;
	  dn = 0;
	  _tptable->store_checkmate_info(key, attack_side, pn, dn, 0, Pass);
	  return -2;
	}
      }
      pn = 0;
      dn = DN_MAX;
      int tsumi_depth;
      if (best == mil.end()) tsumi_depth = depth;
      else                   tsumi_depth = max_tsumi_depth; 

      // 違法手の場合（ピンされてる駒が動いて防ぐ手など）
      if (tsumi_depth == depth+1) {
	best_move_list.clear();
	tsumi_depth = depth;
      }

      if (tsumi_depth == depth) {
	// この局面で詰んでいる場合
	atk_inhands = INHAND_MIN;
	// ここでもハッシュに最小持駒で登録
      } else {
	if (ban->ou_masu(turn)->long_dir_kiki_num(enemy_side(turn)) > 0) {
	  // 遠距離王手は合い駒ができるので
	  // ほんとうはもっと効率化可能
	  if (turn == GOTE) atk_inhands = key.inhand();
	  else atk_inhands = calc_gote_inhands(ban, key.inhand(), key.inhand());
	}
      }


      ShogibanHashKey 
	tmp_key = calc_min_inhands(ban, key, attack_side, atk_inhands);
      /*
      if (key != tmp_key) {
	print_kind(ban);
	cout << "tmp_inhands = ";
	for (int i = 1; i <= 7; i++) cout << tmp_key.inhand().Num(i) << " ";
	cout << endl;
      }
      */
      Move mv = Pass;
      if (!best_move_list.empty()) mv = best_move_list.front();
      _tptable->store_checkmate_info(tmp_key, attack_side, pn, dn, tsumi_depth - depth, mv);
      //      _tptable->store_checkmate_info(key, attack_side, pn, dn, tsumi_depth - depth, mv);
      if (STORE_SEARCH_HASH)
	_tptable->store_search_info(key, 9999, -(100000-tsumi_depth), SearchInfo::EXACT, mv);
      assert(tsumi_depth >= 0);
      //      assert(tsumi_depth % 2 == 1);
      //      cout << "#";
      //      for (int i = 1; i <= 7; i++) cout << atk_inhands.Num(i) << " ";
      //      cout <<endl;
      return tsumi_depth;
    }

    // 不詰 or Terminate
    if (best->dn == 0 ||
	(pn <= dyn_pn_sum && dn <= best->dn)) {
      pn = dyn_pn_sum;
      dn = best->dn;
      _tptable->store_checkmate_info(key, attack_side, pn, dn, 0, Pass);
      if (dn == 0) { assert(pn == TSUMAZU); return -2; }
      return -1;
    }

    dyn_eval_dn = max(dyn_eval_dn, best->dn);

    // select_child
    List<Move_and_Info>::iterator child = mil.begin();
    for (List<Move_and_Info>::iterator i = mil.begin(); i != mil.end(); i++) {
      int cdn = i->dn;
      assert(cdn != 0);
      cdn = max(dyn_eval_dn, cdn);
      if (cdn <= child->dn) {
	if (cdn < child->dn)
	  child = i;
	else {
	  int cpn = i->pn;
	  if (cpn < child->pn)
	    child = i;
	}
      }
    }

    int cpn = child->pn;
    int cdn = child->dn;

    if (pn > dyn_pn_sum &&
	(cpn <= cdn || dn <= best->dn)) {
      cpn++;
    } else {
      cdn++;
    }

    // 無駄合い
    //   ... その場所に相手の駒を移動させて詰むかどうかを調べる
    //       取った駒をすぐに玉方に返すのといっしょ
    if (child->is_mudaai) {
      int tsumi_depth = -1;

      const Move& move = child->move;
      //      print_kind(ban);
      //      cout << movestring(move) << endl;
      _move_sequence[depth] = Pass;
      ShogibanHashKey key1 = key;
      key1.update(ban, Pass);
      ban->s_move(Pass); // 攻め方の手番に
      _key_sequence[depth+1] = key1;
      LL(Move, ml, tid);
      Searcher::generate_moves_to(ban, ml, move.to());
      LL(Move, dummy, tid);
      for (List<Move>::const_iterator i = ml.begin(); i != ml.end(); i++) {

	r_coord_t kdir = get_step(i->to() - i->from());
	r_coord_t odir = get_step(ban->ou_masu(turn)->pos() - i->from());
	if (kdir != odir) continue;

	ShogibanHashKey key2 = key1;
	key2.update(ban, *i);
	_move_sequence[depth+1] = *i;
	ban->s_move(*i); // 無駄合いの場所に移動
	_key_sequence[depth+2] = key2;
	dummy.clear();
	int _pn = pn;
	int _dn = dn;
	NumInhands a_inhands(INHAND_MAX);
	tsumi_depth = defense(tid, _move_sequence, _key_sequence, countdown,
			      depth+2, _pn, _dn, key2, ban, a_inhands, dummy);
	ban->s_reverse();
	if (tsumi_depth >= 0) break;
	//	if (tsumi_depth < 0)
	//	  child->is_mudaai = false;
	//	else {
	//	  break; // 一つでも詰めばよい
	//	}
      }
      ban->s_reverse();
      if (tsumi_depth < 0) 
	child->is_mudaai = false; // どれでも詰まなかった
      else {
	/*
	  // これはだめ、無駄合いをとった後の手順だから、とった駒の位置がちがう
	if (tsumi_depth-2 > max_tsumi_depth) {
	  max_tsumi_depth = tsumi_depth;
	  best_move_list = dummy;
	}
	*/
	mil.erase(child);
	continue;
      }
    }

    const Move& move = child->move;
    _move_sequence[depth] = move;
    ban->s_move(move);
    LL(Move, enemy_bestml, tid);
    NumInhands a_inhands(3, 3, 3, 3, 3, 3, 3);
    int tsumi_depth = attack(tid, _move_sequence, _key_sequence, countdown, 
			     depth+1, cpn, cdn, child->key, ban, 
			     a_inhands, enemy_bestml);
    //    assert(attack_side == GOTE || 
    //	   (attack_side == SENTE && key.inhand().Eq_or_gt(a_inhands)));
    if (tsumi_depth >= 0) {
      child->tsumi_depth = tsumi_depth;
      if (tsumi_depth > max_tsumi_depth) {
	max_tsumi_depth = tsumi_depth;
	best_move_list = enemy_bestml;
	best_move_list.push_front(move);
      }
      child->atk_inhands = a_inhands;
      /*
	print_kind(ban);
	cout << "inhands     = ";
	for (int i = 1; i <= 7; i++) cout << child->key.inhand().Num(i) << " ";
	cout << endl;
	cout << "atk_inhands = ";
	for (int i = 1; i <= 7; i++) cout << atk_inhands.Num(i) << " ";
	cout << endl;
      */
    }
    ban->s_reverse();
    child->pn = cpn;
    child->dn = cdn;

    if (countdown < 0 || Searcher::is_search_aborted()) return -1;
  }
}  


//-----------------------------------------------------------------------
// tsume 入口（完全な詰み手順を返す）
//
//-----------------------------------------------------------------------

// 攻め方
static int id_attack(const l_thread_id tid, int max_nodes, 
		     Shogiban* ban, ShogibanHashKey key,
		     List<Move>& best_move_list)
{
  assert(max_nodes > 0);
  assert(key == ShogibanHashKey(ban));

  ShogibanHashKey _key_sequence[MAX_DEPTH+10];  
  Move _move_sequence[MAX_DEPTH+10];

  // 多重反復深化
  int tsumi_depth;
  int pn = 1;
  int dn = 1;
  while(1) {
    int last_pn = pn;
    int last_dn = dn;
    NumInhands a_inhands(2, 2, 4, 4, 4, 4, 18); // max
    tsumi_depth = attack(tid, _move_sequence, _key_sequence, max_nodes, 0, 
			 pn, dn,
			 key, ban, a_inhands, best_move_list);
    if (pn == 0 || dn == 0 || max_nodes < 0 || Searcher::is_search_aborted()) {
      pn = last_pn;
      dn = last_dn;
      break;
    }

    if (pn <= dn) pn++;
    else          dn++;
  }

  return tsumi_depth;
}

// 玉め方
static int id_defense(const l_thread_id tid, int max_nodes, 
		     Shogiban* ban, ShogibanHashKey key,
		     List<Move>& best_move_list)
{
  assert(max_nodes > 0);
  assert(key == ShogibanHashKey(ban));

  ShogibanHashKey _key_sequence[MAX_DEPTH+10];  
  Move _move_sequence[MAX_DEPTH+10];

  // 多重反復深化
  int tsumi_depth;
  int pn = 1;
  int dn = 1;
  while(1) {
    int last_pn = pn;
    int last_dn = dn;
    NumInhands a_inhands(2, 2, 4, 4, 4, 4, 18); // max
    tsumi_depth = defense(tid, _move_sequence, _key_sequence, max_nodes, 0, 
			  pn, dn,
			  key, ban, a_inhands, best_move_list);
    if (pn == 0 || dn == 0 || max_nodes < 0 || Searcher::is_search_aborted()) {
      pn = last_pn;
      dn = last_dn;
      break;
    }

    if (pn <= dn) pn++;
    else          dn++;
  }

  return tsumi_depth;
}


//----------------------------------------------------
// 手順をハッシュから取り出す
//----------------------------------------------------
void
Searcher::retrieve_checkmate_sequence(Shogiban* ban, 
				      ShogibanHashKey key, 
				      side_t attack_side, List<Move>& best_ml,
				      bool depth_mode)
{
  Move t_move;
  int dyn_eval, tsumi_depth, dyn_eval_dn;
  Move tmp_move;
  //  if (!lookup_hash(0, key, attack_side, &tsumi_depth, &dyn_eval, &dyn_eval_dn, &tmp_move)) return;
  if (depth_mode) {
    if (!tptable->retrieve_cm_depth(key, attack_side, 999, &tsumi_depth, &tmp_move)) return;
    if (tsumi_depth < 0) return;
  } else {
    NumInhands dummy;
    if (!tptable->retrieve_checkmate_info(key, attack_side, &dyn_eval, &dyn_eval_dn, &tsumi_depth, &dummy, &tmp_move)) return;
  }
  if (!is_legal_move(ban, tmp_move)) return;
  if (tmp_move == Pass) return;
  best_ml.push_back(tmp_move);

  key.update(ban, tmp_move);
  ban->s_move(tmp_move);
  retrieve_checkmate_sequence(ban, key, attack_side, best_ml, depth_mode);
  ban->s_reverse();
  
  return;
}


int Searcher::pds_nagai_complete(const l_thread_id tid, int max_nodes, 
				 Shogiban* ban, ShogibanHashKey key,
				 side_t attack_side,
				 List<Move>& best_move_list)
{
  int turn = ban->turn();
  _tptable = tptable;

  if (attack_side != turn) {
    key.update(ban, Pass);
    ban->s_move(Pass); // パスして攻め方の手番にする
  }

  int n = 0;
  int depth;
  bool start = true;
  while(1) {
    LL(Move, best_ml, O_THREAD_ID);
    if (!start) {
      _tptable->clear();
    }
    start = false;
    if (ban->turn() == attack_side) 
      depth = id_attack(tid, max_nodes, ban, key, best_ml);
    else 
      depth = id_defense(tid, max_nodes, ban, key, best_ml);

    if (best_ml.size() < depth) {
      LL(Move, ml, O_THREAD_ID);
      retrieve_checkmate_sequence(ban, ban->key(), attack_side, ml);
      if (ml.size() > best_ml.size())
	best_ml = ml;
    }

    // 詰まない
    if (max_nodes < 0) break;
    if (depth < 0) break;

    // 詰み手順の終わりの局面まで進める
    for (List<Move>::const_iterator i = best_ml.begin(); 
	 i != best_ml.end(); i++) {
      //      cout << movestring(*i) << endl;
      assert(is_legal_move(ban, *i));
      best_move_list.push_back(*i);
      key.update(ban, *i);
      ban->s_move(*i);
      n++;
    }
    if (best_ml.size() == depth) break;
    //    cout << "depth == " << depth << " best_ml.size() = " << best_ml.size() << endl;
  }

  for (int i = 0; i < n; i++)
    ban->s_reverse();

  if (attack_side != turn) ban->s_reverse();

  if (depth < 0) return depth;

  //  cout << n << "手詰み" << endl;

  return n;
}

//-----------------------------------------------------------------------
// tsume 入口
//
//-----------------------------------------------------------------------
int Searcher::pds_nagai(const l_thread_id tid, int max_nodes, 
			Shogiban* ban, ShogibanHashKey key,
			side_t attack_side,
			List<Move>& best_move_list)
{
  /*
  for (int i = 0; i < 100; i++) {
    NumInhands a(rand() % 3, rand() % 3, rand() % 5, rand() % 5, rand() % 5, rand() % 5, rand() % 19);
    NumInhands b(rand() % 3, rand() % 3, rand() % 5, rand() % 5, rand() % 5, rand() % 5, rand() % 19);
    NumInhands c = a.Or(b);
    for (int i = 1; i <= 7; i++) cout << a.Num(i) << " ";
    cout << endl;
    for (int i = 1; i <= 7; i++) cout << b.Num(i) << " ";
    cout << endl;
    for (int i = 1; i <= 7; i++) cout << c.Num(i) << " ";
    cout << endl;
    cout << endl;
  }
  exit(0);
  */

  assert(max_nodes > 0);
  int turn = ban->turn();

  //  _tptable = this->tptable;
  _tptable = tptable;
  //  _tptable->clear();
  
  if (attack_side != turn) {
    key.update(ban, Pass);
    ban->s_move(Pass); // パスして攻め方の手番にする
  }
  if(_use_svm){
    max_nodes = (int)(1.3 * max_nodes / (1. + exp(-_svm->predict_ban(ban))));
  }
  
//  ShogibanHashKey key(ban);
  assert(key == ShogibanHashKey(ban));

  int countdown = max_nodes;

  ShogibanHashKey _key_sequence[MAX_DEPTH+10];  
  Move _move_sequence[MAX_DEPTH+10];

  // 多重反復深化
  int tsumi_depth;
  //  int max_pn = 250;
  //  int max_dn = 250;
  int pn = 1;
  int dn = 1;
  NumInhands a_inhands;
  while(1) {
    int last_pn = pn;
    int last_dn = dn;
    tsumi_depth = attack(tid, _move_sequence, _key_sequence, countdown, 0, 
			 pn, dn,
			 key, ban, a_inhands, best_move_list);
    //    cerr << pn << " " << dn << endl;
    if (pn == 0 || dn == 0 || countdown < 0) {
      pn = last_pn;
      dn = last_dn;
      break;
    }

    if (pn <= dn) pn++;
    else          dn++;
    
    if (pn >= PN_MAX || dn >= DN_MAX) break;
  }

  /*
  Move dummy;
  int re = reconfirm_tsumi(ban, key, key, dummy);
  print_kind(ban);
  cout << "tsumi_depth = " << tsumi_depth << endl;
  cout << "reconfirm   = " << re << endl;
  */

  if (attack_side != turn) ban->s_reverse();
  /*
  if (tsumi_depth >= 0) {
    cout << "O";
  }
  else if (tsumi_depth == -2) {
    cout << "z";
  } else {
    cout << ".";
  }
  */

  /*
  if (tsumi_depth >= 0) {
    cout << "pn = " << pn << " dn = " << dn << " で、";
    cout << tsumi_depth << "手詰み" << endl;
    cout << "証明駒 ";
    for (int i = 1; i <= 7; i++) cout << a_inhands.Num(i) << " ";
    cout << endl;
  }
  else if (tsumi_depth == -2) {
    cout << "pn = " << pn << " dn = " << dn << " で、";
    cout << "絶対不詰" << endl;
  } else {
    cout << "pn = " << pn << " dn = " << dn << " で、";
    cout << "不明" << endl;
  }
  cout << "ノード数: " << max_nodes - countdown << endl;
  */

  //    LL(Move, ml, O_THREAD_ID);
  //    retrieve_checkmate_sequence(ban, ban->key(), attack_side, ml);
  //    best_move_list = ml;

  return tsumi_depth;
}

/*
 * $Log: pds_nagai.cpp,v $
 * Revision 1.22.2.3  2005/04/27 09:15:20  miwa
 * change svm parameter
 *
 * Revision 1.22.2.2  2005/04/25 18:51:57  yokoyama
 * merged from trunk (from 2004-09-XX to revision merge_to_classifier_20050426)
 *
 * Revision 1.24  2004/11/15 17:39:04  tsuruoka
 * shomeigoma bugfix
 *
 * Revision 1.23  2004/10/02 05:48:39  tsuruoka
 * make some modifications for the windows version
 *
 * Revision 1.22.2.1  2004/08/19 08:47:48  miwa
 * *** empty log message ***
 *
 * Revision 1.22  2004/05/15 16:01:38  yokoyama
 * マルチスレッド版を本流に
 *
 * Revision 1.21.2.1  2004/05/07 13:54:39  tsuruoka
 * fixes in wcsc14
 *
 * Revision 1.21  2004/04/07 13:43:41  tsuruoka
 * shomei-goma (atk_inhands)
 *
 * Revision 1.20  2003/10/10 07:31:10  tsuruoka
 * 初めて訪れる局面で check_immediate_tsumi()
 *
 * Revision 1.19  2002/11/28 16:35:35  tsuruoka
 * 証明数、反証数が上限を超えないように修正
 *
 * Revision 1.18  2002/09/29 14:25:04  tsuruoka
 * 詰みチェックを中止してもすぐに返ってこない問題を修正
 *
 * Revision 1.17  2002/06/21 10:46:29  yokoyama
 * autoconf対応
 *
 * Revision 1.16  2002/03/26 12:39:07  tsuruoka
 * bugfix
 *
 * Revision 1.15  2001/12/17 14:42:21  tsuruoka
 * cm_depth() でハッシュから手順をとってくるように
 *
 * Revision 1.14  2001/12/07 03:26:52  tsuruoka
 * windowsとの互換性向上
 *
 * Revision 1.13  2001/12/06 13:36:13  tsuruoka
 * pds_nagai_complete() を追加。（完全な手順を返す）
 *
 * Revision 1.12  2001/11/13 09:54:00  tsuruoka
 * 攻め方の玉がいなくてもいいように
 *
 * Revision 1.11  2001/09/25 04:17:32  tsuruoka
 * 無駄合いbugfix
 *
 * Revision 1.10  2001/09/25 04:09:09  tsuruoka
 * 無駄合いの処理をちょっと修正
 *
 * Revision 1.9  2001/03/06 11:55:30  tsuruoka
 * searcher のほとんどを static 化
 *
 * Revision 1.8  2001/03/01 13:03:32  tsuruoka
 * _move_sequence[] と _key_sequence[] を stack に
 *
 * Revision 1.7  2001/03/01 08:53:46  tsuruoka
 * 時間打ち切り対応
 *
 * Revision 1.6  2001/03/01 06:51:09  tsuruoka
 * pds_nagai() も thread id もちまわり
 *
 * Revision 1.5  2001/02/28 10:58:55  tsuruoka
 * 詰みの局面を search_hash に store
 *
 * Revision 1.4  2001/02/28 10:15:18  tsuruoka
 * 無駄合の処理を追加
 *
 * Revision 1.3  2001/02/28 09:13:31  tsuruoka
 * 反証数の上限を 65535 に
 *
 * Revision 1.2  2001/02/28 08:33:51  tsuruoka
 * select_child で 証明数が同じときは反証数が小さいのを選ぶ
 *
 * Revision 1.1  2001/02/27 10:58:45  tsuruoka
 * pds 長井詰め追加
 *
 */