三目並べの強解決（後退解析）（完全解析）

この記事では、強解決の手段として後退解析プログラムによって三目並べゲーム内のすべての局面で評価値をつけます。ｃ＋＋を使用して三目並べに対して解析をします。windowsもmacでも可能。

二人零和有限確定完全情報ゲーム
どうぶつしょうぎの完全解析
プログラム

二人零和有限確定完全情報ゲーム

対戦人数が二人で（二人）、対戦者の得点の合計が0（零和）、可能な局面数が有限かつ（有限）、ランダム性がなく（確定）、ゲームの情報が全て公開されている（完全情報）ゲームを 二人零和有限確定完全情報ゲーム と言います。

ゲーム情報学（ゲームの分類）

ゲームとはゲームを情報学的に捉えるために定義を考えます。wikiでは"勝負、または勝敗を決めること。守るべきルールがあり、環境または他人との相互作用を元に行なわれる活動である。"とされます。言葉の意味の中からゲームに

将棋、オセロ、三目並べなどがこのゲームの種類に含まれます。これらのゲームは初期局面を含むすべての局面で勝ち、引き分け、負けの評価をすることができます。

三目並べくらいの総局面数がすくないゲームであれば、後退解析プログラムを使用して全局面の勝敗を求めることができます。

どうぶつしょうぎの完全解析

どうぶつしょうぎは2009年に後手必勝である解析結果が出ています。（田中哲朗）

「どうぶつしょうぎ」の完全解析

このプログラムを利用して後退解析を行います。ｃ＋＋環境が必要なのでwindowsの方はこの記事を参考に環境設定をしてください。

C++ 環境設定 for windows64bit(MinGW-w64)

ｃ＋＋の環境設定を説明します。 windowsに64bit用のc＋＋コンパイラを入れます。 C＋＋の環境の種類とダウンロードコンパイラの種類がいくつかあります。利用目的に応じて、最善なコンパイラのための情報を探しましょう。今回はMinG

プログラム

githubからダウンロードしてください。

GitHub - kowara-gan/tictactoeAnalysis: This is the retrograde analysis program for Tic-tac-toe.

This is the retrograde analysis program for Tic-tac-toe. - GitHub - kowara-gan/tictactoeAnalysis: This is the retrograde analysis program for Tic-tac-toe.

・Makefaile

コンパイルに使用するメイクファイル。コマンドプロントでmakeと打ち込むだけで使用できます。

・tictoctoe.h

メインプログラム、三目並べの盤面情報を扱う。getStateNum()で表示される11桁表記は１～９のマスを一桁づつ表し、0は空白・１は手番の占領・2は相手手番の占領を表現する。また、10・11桁目はそれぞれの占領可能回数（手番・相手手番）を表す。つまり初手は45000000000となり、真ん中に×を描くー＞真ん中に〇がある場合44000020000となる。＊後退解析の都合で常に盤上データは先手番（×番）としているため。

・makeAllState.exe

初期局面から到達可能な局面を作成し、allstates.datファイルに出力します。

・makeWinLose.exe

後退解析によってwinLose.datとwinLoseCount.datファイルに各局面の勝敗と勝敗に要する手数を記録して出力します。

・checkState.exe

3つの出力済みファイルから局面の情報を表示できます。この記事の最後に実行例を載せます。

三目並べプログラム

#ifndef _TICTOCTOE_H

#define _TICTOCTOE_H
#include <cassert>
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <vector>
#include <complex>
#include <deque>
#include <string>
using namespace std;
typedef complex<int> Point;

typedef unsigned long long uint64;
typedef vector<uint64> vUint64;
typedef vector<char> vChar;
typedef unsigned char uchar;
typedef vector<uchar> vuChar;
typedef vector<short> vShort;
typedef vector<int> vInt;
//FIRSTが先手、SECONDが後手
enum Player{
  FIRST=1, SECOND=-1
};
//盤面のマスの状態
struct Ptype{
  enum {
    EMPTY=0,
    X=1,
    O=-1,
  };
};

struct State{
    char board[3*3];//局面情報
    int stands[2];//手持ちの情報
    int turn;//手番情報
    State(){
    for(int x=0;x<3;x++)
      for(int y=0;y<3;y++)
      board[x*3+y]=Ptype::EMPTY;
    stands[0]=5;
    stands[1]=4;
    turn=FIRST;
  }
  //９桁表記＋2桁の手持の情報表記
  uint64 getStateNum() const{
    uint64 a=0;
    uint64 h=1;
    for(int x=0;x<3;x++)
      for(int y=0;y<3;y++){
        if(board[x*3+y]!=-1){
          a+=board[x*3+y]*h;
        }else{
          a+=2*h;
        }
        h*=10;
      }
      a+=stands[0]*h;
      a+=stands[1]*h*10;
      return a;
  }
  //getStateNum()で表示された11桁表記からStateを生成
  State(uint64 p,bool test)
  {
    State s;
    uint64 a=p;
    for(int x=0;x<3;x++)
      for(int y=0;y<3;y++){
        char b=a%10;
        if(b==2){s.board[x*3+y]=-1;}else{s.board[x*3+y]=b;}
        a=a/10;
      }
    s.stands[0]=a%10;
    s.stands[1]=a/10%10;
    s.turn=FIRST;
    *this=s;
  }
  //正規化された局面情報からStateを生成
  State(uint64 p,Player pl=FIRST)
  {
    if(pl==FIRST) *this=makeFirstFromUint64(p);
    else *this=makeFirstFromUint64(p).rotateChangeTurn();
  }
  static State makeFirstFromUint64(uint64 p){
    State s;
    int i=0;
    for(int x=0;x<3;x++)
      for(int y=0;y<3;y++){
	char c=(p>>(i*2))&3;
	if((c&2)!=0) c-=4;
	s.board[x*3+y]=c;
	i++;
      }
    s.stands[0]=(p>>(18))&7;
    s.stands[1]=(p>>(18+3))&7;
    s.turn=FIRST;
    return s;
  }
  //手番と局面情報を反転する
  State rotateChangeTurn() const
  {
    State ret;
    for(int x=0;x<3;x++)
      for(int y=0;y<3;y++)
	ret.board[x*3+y]= -board[x*3+y];
    
    ret.stands[0]=stands[1]; 
    ret.stands[1]=stands[0]; 
    ret.turn= -turn;
    return ret;
  }
  //手番を反転する
  void changeTurn()
  {
    turn = -turn;
  }
  //局面を上下反転する
  void flipVertically()
  {
    State ret;
    for(int x=0;x<3;x++)
      for(int y=0;y<3;y++)
	ret.board[x*3+y]= board[(2-x)*3+y];
  ret.stands[0]=stands[0]; 
    ret.stands[1]=stands[1]; 
    *this=ret;
  }
  //局面を斜め反転する
  void flipDiagonally()
  {
    State ret;
    ret.board[0]= board[0];
	  ret.board[1]= board[3];
    ret.board[2]= board[6];
    ret.board[3]= board[1];
    ret.board[4]= board[4];
    ret.board[5]= board[7];
    ret.board[6]= board[2];
    ret.board[7]= board[5];
    ret.board[8]= board[8];
    ret.stands[0]=stands[0]; 
    ret.stands[1]=stands[1]; 
    *this=ret;
  }
  //局面情報を１と０のbit表現で生成
  uint64 packBit() const
  {
    assert(turn==FIRST);
    uint64 ret=0ull;
    int i=0;
    for(int x=0;x<3;x++)
      for(int y=0;y<3;y++){
	ret|=static_cast<uint64>(board[x*3+y]&3)<<(i*2);
	i++;
      }
    for(int j=0;j<2;j++)
      ret|=static_cast<uint64>(stands[j])<<(18+j*3);
    return ret;
  }
  //局面情報から同じとみなせる７つの局面をだして最も小さい数字にして生成
  uint64 normalizeNum() const{
    if(turn==FIRST){
      State a = *this;
      uint64 u1=packBit();
      a.flipVertically();
      u1=std::min(u1,a.packBit());
      a.flipDiagonally();
      u1=std::min(u1,a.packBit());
      a.flipVertically();
      u1=std::min(u1,a.packBit());
      a.flipDiagonally();
      u1=std::min(u1,a.packBit());
      a.flipVertically();
      u1=std::min(u1,a.packBit());
      a.flipDiagonally();
      u1=std::min(u1,a.packBit());
      a.flipVertically();
      u1=std::min(u1,a.packBit());
      return u1;
    }
    else{
      State a=rotateChangeTurnState();
      uint64 u1=a.packBit();
      a.flipVertically();
      u1=std::min(u1,a.packBit());
      a.flipDiagonally();
      u1=std::min(u1,a.packBit());
      a.flipVertically();
      u1=std::min(u1,a.packBit());
      a.flipDiagonally();
      u1=std::min(u1,a.packBit());
      a.flipVertically();
      u1=std::min(u1,a.packBit());
      a.flipDiagonally();
      u1=std::min(u1,a.packBit());
      a.flipVertically();
      u1=std::min(u1,a.packBit());
      return u1;
    }
  }
  //負けているか判定
  bool isLoseFirst() const{
    if(board[0]+board[1]+board[2]==-3||
      board[3]+board[4]+board[5]==-3||
      board[6]+board[7]+board[8]==-3||
      board[0]+board[3]+board[6]==-3||
      board[1]+board[4]+board[7]==-3||
      board[2]+board[5]+board[8]==-3||
      board[0]+board[4]+board[8]==-3||
      board[2]+board[4]+board[6]==-3
      )return true;
      return false;
  }
  //つぎの正規化した局面をすべて生成
  vUint64 nextNStates() const{
    vUint64 ret;
    if(stands[0]==0)return ret;
    for(int x=0;x<3;x++)
      for(int y=0;y<3;y++){
          if(board[x*3+y]==0){
              State s(*this);
              s.board[x*3+y]=Ptype::X;
              s.stands[0]--;
              s.changeTurn();
              ret.push_back(s.normalize());
          }
      }
      return ret;
  }
  //つぎの局面をgetStateNum()で表した情報をすべて生成
  vUint64 nextShowStates() const{
    vUint64 ret;
    if(stands[0]==0)return ret;
    for(int x=0;x<3;x++)
      for(int y=0;y<3;y++){
          if(board[x*3+y]==0){
              State s(*this);
              s.board[x*3+y]=Ptype::X;
              s.stands[0]--;
              s.changeTurn();
              ret.push_back(s.rotateChangeTurn().getStateNum());
          }
      }
      return ret;
  }
  //手持から先手番か後手番かをわりだしてただしく描画する
  void draw() const{
    int p=1;
    if(stands[0]==stands[1])p=-1;
    for(int x=0;x<3;x++){
      std::cerr << "|";
      for(int y=0;y<3;y++){
        if(board[x*3+y]==0){
          std::cerr << " |";
        }else if(board[x*3+y]==p*1){
          std::cerr << "x|";
        }else if(board[x*3+y]==p*-1){
          std::cerr << "o|";
        }
      }
      std::cerr << std::endl;
    }
  }
};
#endif

次盤面を出す際に局面を反転してすべて先手番（つまり ×と〇を入れ替えてつねに×番としている）としています。そのため正規化して出てくる盤面はすべて先手番です（後退解析中の手番情報削除のため）。

9マスの局面は次のように他の７つの局面で対称性があります。上下反転と斜め反転を繰り返すことで正位置からすべてをだせます。

対称性を考慮すると対局中に存在できる三目並べの局面は合計765パターン局面が存在しており、勝敗を無視すると850パターンです。

アルゴリズム三目並べの譜面全パターン分析

#include "tictoctoe.h"

#include <unordered_set>
typedef deque<uint64> dUint64;
struct hashUint64{//unordered_set用hash関数
  int operator()(uint64 const& v) const{
    return (v>>32)^(v&0xffffffffull);
  }
};
typedef unordered_set<uint64,hashUint64> hUint64;

int main()
{
  vUint64 allIS;
  dUint64 q;
  hUint64 v;
  q.push_back(State().normalize());//初期局面をキューに入れる
  while(!q.empty()){
    uint64 is=q.front();
    q.pop_front();//キューから先頭を取り出す
    hUint64::const_iterator it=v.find(is);
    if(it==v.end()){//ｖに保存されていない初めて認識したの局面の場合
      State s(is,FIRST);
      allIS.push_back(is);
      v.insert(is);//ｖに保存
      if(!s.isLoseFirst()){//詰み局面でない場合
        //if(true){
	    vUint64 ns=s.nextStates();//次の局面をすべて出す
	    for(size_t i=0;i<ns.size();i++)
        q.push_back(ns[i]);//次の局面を全てキューに入れる
      }
    }
  }
  cout << v.size() << endl;
  sort(allIS.begin(),allIS.end());
  ofstream ofs("allstates.dat");
  ofs.write((char *)&allIS[0],allIS.size()*sizeof(uint64));
}

キューに局面を書き出して新しい局面なら保存する方法ですべての局面を出します。26行目と27行目のコメントアウトを入れ替えると総局面数が変化します。

#include "tictoctoe.h"
#include "allStateTable.h"
//局面ｖを評価する
int newWinLoss(AllStateTable const& allIS,vChar const& winLoss,uint64 v){
  State s(v);
  vUint64 ns=s.nextStates();//次の局面を全て出す
  if(ns.size()==0)return 0;//次の局面がない場合引き分け局面とする
  bool alllose=true;
  for(size_t j=0;j<ns.size();j++){
    int i1=allIS.find(ns[j]);
    assert(0<=i1 && i1<allIS.size());
    if(winLoss[i1]== -1) return 1;//次の局面に一つでも勝ち局面がある場合勝ち局面とする
    if(winLoss[i1]==0) alllose=false;
  }
  if(alllose) return -1;//次の局面全てが負け局面である場合負け局面とする
  else return 0;//その他の場合引き分け局面とする
}
//解析に使用する
int main()
{
  AllStateTable allIS("allstates.dat",false);//すべての局面データ読み込み 
  int dSize=allIS.size();//局面データサイズ
  vChar winLoss(dSize,0);
  vChar winLossCount(dSize,0);
  vInt count(3);
  for(size_t i=0;i<dSize;i++){//すべての局面で繰り返し
    State s(allIS[i]);
    if(s.isLoseFirst()){//局面が詰み局面の場合
      winLoss[i]=-1;
      count[0]++;//負け局面としてカウント
    }
    else count[1]++;//引き分け局面としてカウント
  }
  for(int c=1;;c++){//カウントに変化がなくなるまで繰り返し
    vChar winLossNew(winLoss);
    std::cout << "iteration " << c << std::endl;
    for(int j=0;j<3;j++){//負け引き分け勝ち局面のカウントを表示
      std::cout << (j-1) << " : " << count[j] << std::endl;
    }
    bool changed=false;
    for(size_t i=0;i<dSize;i++){//すべての局面で繰り返し
      if(winLoss[i]==0){//局面が引き分けの場合
        int nv=newWinLoss(allIS,winLoss,allIS[i]);
        if(nv!=0){//局面の評価に変更があった場合
          winLossNew[i]=nv;//評価の更新
          winLossCount[i]=c;//カウントの更新
          count[nv+1]++; count[1]--;
          changed=true;//変化あり
        }
      }
    }
    winLoss.swap(winLossNew);//評価を更新した配列と交換して更新
    if(changed==false) break;
  }
  {
    ofstream ofs("winLoss.dat");
    ofs.write((char *)&winLoss[0],winLoss.size());//評価値保存
  }
  {
    ofstream ofs("winLossCount.dat");
    ofs.write((char *)&winLossCount[0],winLossCount.size());//詰み手数保存
  }
}

後退解析のメインプログラムです。以下の手順を繰り返して解析を進めています。

局面の次の局面を全て確認する。
次の局面がない場合引き分け局面とする。
つぎの局面に一つでも（調べている局面の相手の）負け局面がある場合、勝ち局面とする。
つぎの局面の全てが（調べている局面の相手の）勝ち局面である場合、負け局面とする。
その他の場合引き分けとする。

以上を局面の評価値に変化がなくなるまで繰り返すことで後退解析を行うことができます。

iteration 1
-1 : 135
0 : 630
1 : 0
iteration 2
-1 : 135
0 : 309
1 : 321
iteration 3
-1 : 207
0 : 237
1 : 321
iteration 4
-1 : 207
0 : 186
1 : 372
iteration 5
-1 : 224
0 : 169
1 : 372
iteration 6
-1 : 224
0 : 151
1 : 390

結果は先手の負け局面224、引き分け局面151、勝ち局面390です。

checkState.exeをコマンドプロントから起動すると下記のようになります。

macの場合
./checkState
windowsの場合
./checkState.exe
------------------
45000000000
TURNofX 0(0)
1 : 44000000002 0(0)
|x| | |
| | | |
| | | |
2 : 44000000020 0(0)
| |x| |
| | | |
| | | |
3 : 44000000200 0(0)
| | |x|
| | | |
| | | |
4 : 44000002000 0(0)
| | | |
|x| | |
| | | |
5 : 44000020000 0(0)
| | | |
| |x| |
| | | |
6 : 44000200000 0(0)
| | | |
| | |x|
| | | |
7 : 44002000000 0(0)
| | | |
| | | |
|x| | |
8 : 44020000000 0(0)
| | | |
| | | |
| |x| |
9 : 44200000000 0(0)
| | | |
| | | |
| | |x|
44000020000
------------------
44000020000
TURNofO 0(0)
1 : 34000010002 0(0)
|o| | |
| |x| |
| | | |
2 : 34000010020 -1(5)
| |o| |
| |x| |
| | | |
3 : 34000010200 0(0)
| | |o|
| |x| |
| | | |
4 : 34000012000 -1(5)
| | | |
|o|x| |
| | | |
5 : 34000210000 -1(5)
| | | |
| |x|o|
| | | |
6 : 34002010000 0(0)
| | | |
| |x| |
|o| | |
7 : 34020010000 -1(5)
| | | |
| |x| |
| |o| |
8 : 34200010000 0(0)
| | | |
| |x| |
| | |o|

初期局面である45000000000は引き分け（0）であることがわかります。44行目のように真ん中に〇を描いた局面44000020000を打ち込んで、次の局面の情報をだせます。

真ん中に〇を描いた局面でも引き分けであることがわかります。また次の×を角に描いた状態では引き分けですが、辺の真ん中に描いた局面では負け（-1）であることがわかります。