[どうぶつしょうぎ] 完全解析ツールを引き分け局面の追跡に対応させてみる

田中先生のどうぶつしょうぎ完全解析ツールの checkState コマンドは、開始局面が引き分け局面だとその時点で手順の追跡を打ち切ってしまい、引き分けに至る手順は出力されない。
そこで、引き分け局面でも手順が出力されるように checkState コマンドを改造してみた。

• 引き分け局面を発見したら探索を終了するロジックを除去
• 引き分け局面の追跡では、通過した局面を覚えておいて通過済み局面に到達したら追跡終了

という作戦で行く。
ざっと読んでみた感じだと、winLoseTable.cc （と winLoseTable.h ） に手を入れれば何とかなりそう。

---

WinLoseTable::showSequence

解析結果の出力は、winLoseTable.cc 内に定義されている、WinLoseTable::showSequence で行っている。

与えられた現局面と可能な次手を出力し、最善手を選択してその手を適用した新局面で再帰的に WinLoseTable::showSequence を実行する。
WinLoseTable::showSequence の冒頭で局面の勝ち負け判定を行い、最終局面および引き分け局面であれば終了するようになっているので、引き分け局面で終了しないようにする。

次に、勝ち局面、負け局面それぞれで最善手選択、showSequence 再帰呼び出しを行っているので、ここに引き分け局面用の手順を追加する。通過局面記憶用の set を作成して、引き分け専用に新設したshowDrawSequence 呼び出しをする。

---

WinLoseTable::showDrawSequence

新設した showDrawSequence では、最初に与えられた局面が通過局面か否かを判定し、新局面であれば通過局面リストに追加したのち、局面と次手の出力、最善手の選択、適用後の新局面での showDrawSequence 再起呼び出しを行う。

引き分け局面では双方が最善を尽くしていれば勝ちになる手は出現しないので、次手は「引き分け」か「負け」になる手なので、「引き分け」になる手を双方選択し続けることになる。

---

結果

期待通りに引き分け局面でも再度同じ局面が登場するまで追跡するようになった。

が、解析結果テーブルでは、引き分け局面は終局までの手数が常に「０」扱いになるため、引き分けになる手が複数あった場合に、「最短でループする手」を選択することができず、最初に見つかった「引き分けになる手」を選択することになる。

そのため、出力結果がややｇｄｇｄになる傾向があるが、多少なりとも役には立つと思う。

---

パッチ

winLoseTable.h：

$ diff -u dobutsu-org/winLoseTable.h dobutsu
--- dobutsu-org/winLoseTable.h 2009-06-29 20:28:40.000000000 +0900
+++ dobutsu/winLoseTable.h 2013-06-30 13:39:11.387990571 +0900
@@ -2,6 +2,7 @@
 #define _WIN_LOSE_TABLE_H
 #include "dobutsu.h"
 #include "allStateTable.h"
+#include <set>
 
 class WinLoseTable {
   AllStateTable const& allS;
@@ -37,5 +38,6 @@
   int getWinLose(State const& s, int& wlc) const;
   int getWinLose(State const& s, Move const& m,int& wlc) const;
   void showSequence(State const& s) const;
+  void showDrawSequence(State const& s, set<int>& pastSeq) const;
 };
 #endif

winLoseTable.cc：

$ diff -u dobutsu-org/winLoseTable.cc dobutsu
--- dobutsu-org/winLoseTable.cc 2009-06-29 20:28:40.000000000 +0900
+++ dobutsu/winLoseTable.cc 2013-06-30 13:47:28.079978110 +0900
@@ -90,22 +90,10 @@
   std::cerr << s << std::endl;
   std::cerr << (int)(s.turn==BLACK ? getWinLose(index) : -getWinLose(index)) <<
     "(" << (int)getWinLoseCount(index) << ")" << std::endl;
-  if(getWinLoseCount(index)==0){
-    if(getWinLose(index)==0){
-      vMove moves=s.nextMoves();
-      for(size_t i=0;i<moves.size();i++){
- int wl,wlc;
- wl=getWinLose(s,moves[i],wlc);
- std::cerr << i << " : " << moves[i] << " " << wl << "(" << wlc << ")" << std::endl;
-      }
-    }
+
+  if(getWinLoseCount(index)==0 && getWinLose(index)!=0){
     return;
   }
-  if(getWinLose(index)==0){
-    std::cerr << s << std::endl;
-    std::cerr << "winLose=0" << std::endl;
-    throw InconsistentException();
-  }
   vMove moves=s.nextMoves();
   for(size_t i=0;i<moves.size();i++){
     int wl,wlc;
@@ -130,8 +118,7 @@
  throw InconsistentException();
       }
     }
-    else{
-      assert(getWinLose(index)==1);
+    else if(getWinLose(index)==1){
       if(wl==-1){
  if(getWinLoseCount(index)-1==wlc){
    std::cerr << "Move : " << moves[i] << " " << wl << "(" << wlc << ")" << std::endl;
@@ -144,6 +131,58 @@
    throw InconsistentException();
  }
       }
+    } else {
+      assert(getWinLose(index)==0);
+      if(wl==0){
+ std::cerr << "Move : " << moves[i] << " " << wl << "(" << wlc << ")" << std::endl;
+ State news(s);
+ news.applyMove(moves[i]);
+        set<int> pastSeq;
+ showDrawSequence(news, pastSeq);
+ break;
+      }
+
+    }
+
+  }
+}
+
+void WinLoseTable::showDrawSequence(State const& s, set<int>& pastSeq) const
+{
+  if(!s.isConsistent()) throw InconsistentException();
+  uint64 v=s.normalize();
+  int index=allS.find(v);
+  assert(getWinLose(index)==0);
+  if (pastSeq.find(index) != pastSeq.end()) {
+    std::cerr << std::endl;
+    std::cerr << "--- " << pastSeq.size() << std::endl;    
+    return;
+  }
+  pastSeq.insert(index);
+
+  std::cerr << "------------------" << std::endl;
+  std::cerr << s << std::endl;
+  std::cerr << (int)(s.turn==BLACK ? getWinLose(index) : -getWinLose(index)) <<
+    "(" << (int)getWinLoseCount(index) << ")" << std::endl;
+
+  vMove moves=s.nextMoves();
+  for(size_t i=0;i<moves.size();i++){
+    int wl,wlc;
+    wl=getWinLose(s,moves[i],wlc);
+    std::cerr << i << " : " << moves[i] << " " << wl << "(" << wlc << ")" << std::endl;
+  }
+  for(size_t i=0;i<moves.size();i++){
+    int wl,wlc;
+    wl=getWinLose(s,moves[i],wlc);
+    if(wl==-1){
+      throw InconsistentException();
+    }
+    if(wl==0){
+      std::cerr << "Move : " << moves[i] << " " << wl << "(" << wlc << ")" << std::endl;
+      State news(s);
+      news.applyMove(moves[i]);
+      showDrawSequence(news, pastSeq);
+      break;
     }
   }
 }