00001 #ifndef _NTESUKI_NTESUKI_RECORD_H
00002 #define _NTESUKI_NTESUKI_RECORD_H
00003 #include "osl/ntesuki/ntesukiResult.h"
00004 #include "osl/ntesuki/ntesukiMove.h"
00005 #include "osl/ntesuki/ntesukiMoveList.h"
00006 #include "osl/ntesuki/rzone.h"
00007 #include "osl/ntesuki/ntesukiExceptions.h"
00008 #include "osl/checkmate/checkAssert.h"
00009 #include "osl/misc/carray.h"
00010 #include "osl/state/hashEffectState.h"
00011 #include "osl/container/moveVector.h"
00012 #include "osl/pathEncoding.h"
00013 #include <iosfwd>
00014
00015 namespace osl
00016 {
00017 namespace ntesuki
00018 {
00019 class NtesukiRecord;
00020 class PathEncodingList : public slist<PathEncoding>
00021 {
00022 };
00023
00024 class NtesukiMoveGenerator;
00025 class NtesukiTable;
00026
00032 class NtesukiRecord
00033 {
00034 public:
00035 typedef slist<NtesukiRecord> RecordList;
00036 typedef slist<NtesukiRecord*> RecordPList;
00040 static const unsigned int SIZE = 2;
00041 enum IWScheme { no_iw = 0,
00042 strict_iw = 1,
00043 pn_iw = 2 };
00044
00045 enum PSScheme { no_ps = 0,
00046 pn_ps = 1 };
00047
00048 enum ISScheme { no_is = 0,
00049 tonshi_is = 1,
00050 delay_is = 2,
00051 normal_is = 3 };
00052
00056 static unsigned int fixed_search_depth;
00057 static unsigned int inversion_cost;
00058 static bool use_dominance;
00059 static int pass_count;
00060 static bool max_for_split;
00061 static bool use_rzone_move_generation;
00062 static bool delay_lame_long;
00063 static bool use_9rzone;
00064
00065 static NumEffectState *state;
00066 static NtesukiMoveGenerator *mg;
00067 static NtesukiTable *table;
00068
00069
00070 static unsigned int split_count ,
00071 confluence_count ;
00072
00073
00074 class VisitLock;
00075 class UnVisitLock;
00076
00078 PieceStand black_stand, white_stand;
00079
00081 unsigned short distance;
00082
00084 HashKey key;
00085
00087 RecordList *same_board_list;
00088
00090 RecordPList parents;
00091 int rev_refcount;
00092
00096 NtesukiRecord(signed short distance,
00097 const HashKey& key,
00098 const PieceStand& white_stand,
00099 RecordList* same_board_list);
00100 ~NtesukiRecord()
00101 {
00102 }
00103
00105 Player turn() const
00106 {
00107 return key.turn();
00108 }
00109
00111 bool isBySimulation() const
00112 {
00113 return by_simulation;
00114 }
00115
00120 template<Player P> const PieceStand&
00121 getPieceStand() const
00122 {
00123 return piece_stand<P>();
00124 }
00125
00126 const PieceStand&
00127 getPieceStandSlow(Player P) const
00128 {
00129 if (P == BLACK)
00130 {
00131 return piece_stand<BLACK>();
00132 }
00133 else
00134 {
00135 return piece_stand<WHITE>();
00136 }
00137 }
00138
00143 template <Player A>
00144 PieceStand
00145 calcProofPiecesOr(int pass_left,
00146 const NtesukiMove& m);
00147
00148 template <Player A>
00149 PieceStand
00150 calcProofPiecesAnd(int pass_left);
00151
00156 template <Player A>
00157 void
00158 setProofPieces(int pass_left,
00159 const NtesukiResult& r,
00160 const NtesukiMove& m,
00161 const PieceStand* ps);
00166 template <osl::Player A>
00167 void
00168 setDisproofPieces(int pass_left,
00169 const NtesukiResult& r,
00170 const NtesukiMove& m,
00171 const PieceStand* ps);
00176 template <Player A> void
00177 setResult(int i,
00178 const NtesukiResult& r,
00179 const NtesukiMove& m,
00180 bool bs,
00181 const PieceStand* ps = NULL);
00182
00186 template <Player A> const NtesukiResult getValue(int i) const;
00187 template <Player A> const NtesukiResult getValueWithPath(int i,
00188 const PathEncoding path) const;
00189 template <Player A> const NtesukiResult getValueOr(int i,
00190 const PathEncoding path,
00191 IWScheme iwscheme) const;
00192 template <Player A> const NtesukiResult getValueAnd(int i,
00193 const PathEncoding path,
00194 IWScheme iwscheme, PSScheme psscheme) const;
00195 const NtesukiResult getValueSlow(const Player attacker, int i) const;
00196 const NtesukiResult getValueOfTurn(int i) const;
00197 const NtesukiResult valueBeforeFinal() const;
00198
00199
00200
00201
00202
00203 int isWin(const Player attacker) const
00204 {
00205 int o = 0;
00206 for (; o < (int)SIZE; o++)
00207 {
00208 if (getValueSlow(attacker, o).isCheckmateSuccess())
00209 {
00210 break;
00211 }
00212 }
00213 return o;
00214 }
00215
00216
00220 template <Player A> const NtesukiMove& getBestMove(int i) const;
00221 const NtesukiMove& getBestMoveSlow(Player attacker, int i) const;
00222
00226 bool isVisited() const { return visited; }
00227 bool isFinal() {return final; }
00228
00229 void setVisited()
00230 {
00231 assert (!visited);
00232 visited = true;
00233 }
00234
00235 void resetVisited()
00236 {
00237 assert (visited);
00238 visited = false;
00239 }
00240
00244 template <Player A> bool isByFixed() const;
00245 bool isByFixedSlow(Player attacker) const;
00246
00250 template <Player A> bool isNtesuki(int pass_left) const;
00251 template <Player A> void setNtesuki(int pass_left);
00252
00256 template <Player A> bool hasTriedPropagatedOracle(int pass_left) const;
00257 template <Player A> void triedPropagatedOracle(int pass_left);
00258
00262 template <Player A> PieceStand getPDPieces(int pass_left) const;
00263 PieceStand getPDPiecesSlow(Player attacker, int pass_left) const;
00264 template <Player A> void setPDPieces(int pass_left, const PieceStand p);
00265
00269 bool readInterpose(int pass_left) const
00270 {
00271 return read_interpose[pass_left];
00272 }
00273
00274 void setReadInterpose(int pass_left)
00275 {
00276 read_interpose[pass_left] = true;
00277 }
00278
00282 bool readCheckDefense(int pass_left) const
00283 {
00284 return read_check_defense[pass_left];
00285 }
00286
00287 void setReadCheckDefense(int pass_left)
00288 {
00289 read_check_defense[pass_left] = true;
00290 }
00291
00295 bool readNonAttack(int pass_left) const
00296 {
00297 return read_non_attack[pass_left];
00298 }
00299
00300 void setReadNonAttack(int pass_left)
00301 {
00302 read_non_attack[pass_left] = true;
00303 }
00304
00308 template <Player A> bool
00309 useOld(int pass_left) const;
00310
00311 template <Player A> void
00312 setUseOld(int pass_left,
00313 bool value);
00314
00318 template <Player A> bool
00319 isLoopWithPath(int pass_left,
00320 const PathEncoding& path) const;
00321
00322 template <Player A> void
00323 setLoopWithPath(int pass_left,
00324 const PathEncoding& path);
00325
00326 template <Player A> bool
00327 hasLoop(int pass_left) const
00328 {
00329 return !loop_path_list<A>()[pass_left].empty();
00330 }
00331
00335 template <Player P> bool
00336 setUpNode();
00337
00338
00339 template <Player P> void
00340 setUpAttackNode();
00341
00342
00343 template <Player P> void
00344 setUpDefenseNode();
00345
00346
00347 void
00348 updateWithChild(NtesukiRecord* child,
00349 int pass_left);
00350
00354 template <Player P> void
00355 generateMoves(NtesukiMoveList& moves,
00356 int pass_left,
00357 bool all_moves);
00358
00359
00360 bool operator==(const NtesukiRecord& record)
00361 {
00362 return key == record.key;
00363 }
00364
00365
00366 unsigned int getChildCount() const
00367 {
00368 return child_count;
00369 }
00370
00371 void addChildCount(unsigned int i)
00372 {
00373 child_count += i;
00374 }
00375
00376 unsigned int getReadCount() const
00377 {
00378 return read_count;
00379 }
00380
00381 unsigned int getWrittenCount() const
00382 {
00383 return written_count;
00384 }
00385
00386
00387 private:
00388 bool isNewParent(const NtesukiRecord* p) const
00389 {
00390 for (RecordPList::const_iterator it = parents.begin();
00391 it != parents.end(); ++it)
00392 {
00393 if (*it == p) return false;
00394 }
00395 return true;
00396 }
00397
00398 void find_split(NtesukiRecord *rhs,
00399 RecordPList& lvisited,
00400 RecordPList& rvisited)
00401 {
00402 if (find_split_right(rhs, lvisited, rvisited))
00403 {
00404 return;
00405 }
00406
00407 #if 1
00408 if (parents.empty())
00409 {
00410 return;
00411 }
00412
00413 RecordPList::iterator lp = parents.begin();
00414 if (std::find(lvisited.begin(), lvisited.end(), *lp)
00415 != lvisited.end())
00416 {
00417 return;
00418 }
00419 lvisited.push_front(*lp);
00420 (*lp)->find_split(rhs, lvisited, rvisited);
00421 lvisited.pop_front();
00422 #else
00423 for (RecordPList::iterator lp = parents.begin();
00424 lp != parents.end(); ++lp)
00425 {
00426 if (std::find(lvisited.begin(), lvisited.end(), *lp)
00427 == lvisited.end())
00428 {
00429 lvisited.push_front(*lp);
00430 (*lp)->find_split(rhs, lvisited, rvisited);
00431 lvisited.pop_front();
00432 }
00433 }
00434 #endif
00435 }
00436
00437
00438 bool find_split_right(NtesukiRecord *rhs,
00439 RecordPList& lvisited,
00440 RecordPList& rvisited)
00441 {
00442 if (this == rhs)
00443 {
00444 if (!is_split)
00445 {
00446 ++split_count;
00447 is_split = true;
00448 }
00449 return true;
00450 }
00451
00452 #if 1
00453 if (rhs->parents.empty())
00454 {
00455 return false;
00456 }
00457
00458 RecordPList::iterator rp = rhs->parents.begin();
00459 if (std::find(rvisited.begin(), rvisited.end(), *rp)
00460 != rvisited.end())
00461 {
00462 return false;
00463 }
00464 rvisited.push_front(*rp);
00465 bool result = find_split_right(*rp, lvisited, rvisited);
00466 rvisited.pop_front();
00467 return result;
00468 #else
00469 bool result = false;
00470 for (RecordPList::iterator rp = rhs->parents.begin();
00471 rp != rhs->parents.end(); ++rp)
00472 {
00473 if (std::find(rvisited.begin(), rvisited.end(), *rp)
00474 == rvisited.end())
00475 {
00476 rvisited.push_front(*rp);
00477 result |= find_split_right(*rp, lvisited, rvisited);
00478 rvisited.pop_front();
00479 }
00480 }
00481 return result;
00482 #endif
00483 }
00484
00485 void addNewParent(NtesukiRecord* p)
00486 {
00487 ntesuki_assert(isNewParent(p));
00488 parents.push_front(p);
00489 p->rev_refcount++;
00490 }
00491
00492 public:
00493 void checkNewParent(NtesukiRecord *p)
00494 {
00495 if (parents.empty())
00496 {
00497
00498 addNewParent(p);
00499 }
00500 else if (isNewParent(p))
00501 {
00502 ++confluence_count;
00503 if (max_for_split)
00504 {
00505
00506
00507 RecordPList lvisited, rvisited;
00508 lvisited.push_front(this);
00509 rvisited.push_front(p);
00510 find_split(p, lvisited, rvisited);
00511 }
00512 addNewParent(p);
00513 }
00514 }
00515
00516 private:
00517 typedef CArray<NtesukiResult, SIZE> values_t;
00518 typedef CArray<NtesukiMove, SIZE> moves_t;
00519 typedef CArray<short, SIZE - 1> nodesread_t;
00520 typedef CArray<PieceStand, SIZE> pdpieces_t;
00521 typedef CArray<bool, SIZE> flags_t;
00522 typedef CArray<PathEncodingList, SIZE> pell_t;
00523 typedef CArray<Rzone, SIZE> rzones_t;
00524 values_t values_black, values_white;
00525 moves_t best_move_black, best_move_white;
00526 pdpieces_t pd_pieces_black, pd_pieces_white;
00528 pell_t loop_path_list_black, loop_path_list_white;
00529 mutable unsigned int child_count, read_count, written_count;
00530
00531 NtesukiResult value_before_final;
00533 bool visited;
00534 bool by_simulation;
00535 bool by_fixed_black, by_fixed_white;
00536 bool already_set_up;
00537 bool final;
00538
00539 public:
00540 bool is_split;
00541 bool do_oracle_attack;
00542
00543
00544
00545
00546 bool do_oracle_aunt;
00547
00548
00549 bool rzone_move_generation;
00550
00551 private:
00552 flags_t read_interpose;
00553 flags_t read_check_defense;
00554 flags_t read_non_attack;
00555 flags_t is_ntesuki_black, is_ntesuki_white;
00556 flags_t propagated_oracle_black, propagated_oracle_white;
00557 flags_t use_old_black, use_old_white;
00558 rzones_t rzone_black, rzone_white;
00559
00560 NtesukiRecord();
00561
00562 template <Player P> bool& by_fixed()
00563 {
00564 if (P == BLACK)
00565 return by_fixed_black;
00566 else
00567 return by_fixed_white;
00568 }
00569
00570 template <Player P> const bool& by_fixed() const
00571 {
00572 if (P == BLACK)
00573 return by_fixed_black;
00574 else
00575 return by_fixed_white;
00576 }
00577
00578 template <Player P> PieceStand& piece_stand()
00579 {
00580 if (P == BLACK)
00581 return black_stand;
00582 else
00583 return white_stand;
00584 }
00585
00586 template <Player P> const PieceStand& piece_stand() const
00587 {
00588 if (P == BLACK)
00589 return black_stand;
00590 else
00591 return white_stand;
00592 }
00593
00594 template <Player P> values_t& values()
00595 {
00596 if (P == BLACK)
00597 return values_black;
00598 else
00599 return values_white;
00600 }
00601
00602 template <Player P> const values_t& values() const
00603 {
00604 if (P == BLACK)
00605 return values_black;
00606 else
00607 return values_white;
00608 }
00609
00610 template <Player P> moves_t& best_move()
00611 {
00612 if (P == BLACK)
00613 return best_move_black;
00614 else
00615 return best_move_white;
00616 }
00617
00618 template <Player P> const moves_t& best_move() const
00619 {
00620 if (P == BLACK)
00621 return best_move_black;
00622 else
00623 return best_move_white;
00624 }
00625
00626 template <Player P> pdpieces_t& pdpieces()
00627 {
00628 if (P == BLACK)
00629 return pd_pieces_black;
00630 else
00631 return pd_pieces_white;
00632 }
00633
00634 template <Player P> const pdpieces_t& pdpieces() const
00635 {
00636 if (P == BLACK)
00637 return pd_pieces_black;
00638 else
00639 return pd_pieces_white;
00640 }
00641
00642 template <Player P> flags_t& is_ntesuki()
00643 {
00644 if (P == BLACK)
00645 return is_ntesuki_black;
00646 else
00647 return is_ntesuki_white;
00648 }
00649
00650 template <Player P> const flags_t& is_ntesuki() const
00651 {
00652 if (P == BLACK)
00653 return is_ntesuki_black;
00654 else
00655 return is_ntesuki_white;
00656 }
00657
00658 template <Player P> flags_t& propagated_oracle()
00659 {
00660 if (P == BLACK)
00661 return propagated_oracle_black;
00662 else
00663 return propagated_oracle_white;
00664 }
00665
00666 template <Player P> const flags_t propagated_oracle() const
00667 {
00668 if (P == BLACK)
00669 return propagated_oracle_black;
00670 else
00671 return propagated_oracle_white;
00672 }
00673
00674 template <Player P> flags_t& use_old()
00675 {
00676 if (P == BLACK)
00677 return use_old_black;
00678 else
00679 return use_old_white;
00680 }
00681
00682 template <Player P> const flags_t use_old() const
00683 {
00684 if (P == BLACK)
00685 return use_old_black;
00686 else
00687 return use_old_white;
00688 }
00689
00690 template <Player P> pell_t& loop_path_list()
00691 {
00692 if (P == BLACK)
00693 return loop_path_list_black;
00694 else
00695 return loop_path_list_white;
00696 }
00697
00698 template <Player P> const pell_t& loop_path_list() const
00699 {
00700 if (P == BLACK)
00701 return loop_path_list_black;
00702 else
00703 return loop_path_list_white;
00704 }
00705
00706 public:
00707 template <osl::Player P> rzones_t& rzone()
00708 {
00709 if (P == BLACK)
00710 return rzone_black;
00711 else
00712 return rzone_white;
00713 }
00714 private:
00715 template <Player P> void
00716 setFinal(int i,
00717 const NtesukiResult& r,
00718 const NtesukiMove& m,
00719 const PieceStand* ps);
00720
00724 void lookup_same_board_list();
00725
00726 template <Player P>
00727 void propagate_proof(int pass_left);
00728
00729 template <Player P>
00730 void propagate_disproof(int pass_left);
00731
00732 public:
00733 template <Player P>
00734 bool isDominatedByProofPieces(const NtesukiRecord* record,
00735 int pass_left) const;
00736
00737 template <Player P>
00738 bool isDominatedByDisproofPieces(const NtesukiRecord* record,
00739 int pass_left) const;
00740
00741 template <Player P>
00742 bool isBetterFor(NtesukiRecord* record);
00743 };
00744 std::ostream& operator<<(std::ostream&, const osl::ntesuki::NtesukiRecord&);
00745
00746 std::ostream& operator<<(std::ostream&,
00747 const osl::ntesuki::NtesukiRecord::IWScheme&);
00748 std::istream& operator>>(std::istream&,
00749 osl::ntesuki::NtesukiRecord::IWScheme&);
00750
00751 std::ostream& operator<<(std::ostream&,
00752 const osl::ntesuki::NtesukiRecord::PSScheme&);
00753 std::istream& operator>>(std::istream&,
00754 osl::ntesuki::NtesukiRecord::PSScheme&);
00755
00756 std::ostream& operator<<(std::ostream&,
00757 const osl::ntesuki::NtesukiRecord::ISScheme&);
00758 std::istream& operator>>(std::istream&,
00759 osl::ntesuki::NtesukiRecord::ISScheme&);
00760
00761 class NtesukiRecord::VisitLock
00762 {
00763 NtesukiRecord* record;
00764 public:
00765 VisitLock(NtesukiRecord* record)
00766 : record(record)
00767 {
00768 assert(!record->isVisited());
00769 record->setVisited();
00770 }
00771 ~VisitLock()
00772 {
00773 assert(record->isVisited());
00774 record->resetVisited();
00775 }
00776 };
00777
00778 class NtesukiRecord::UnVisitLock
00779 {
00780 NtesukiRecord* record;
00781 public:
00782 UnVisitLock(NtesukiRecord* record)
00783 : record(record)
00784 {
00785 assert(record->isVisited());
00786 record->resetVisited();
00787 }
00788 ~UnVisitLock()
00789 {
00790 assert(!record->isVisited());
00791 record->setVisited();
00792 }
00793 };
00794 }
00795 }
00796
00797 #endif
00798
00799
00800
00801