Go to Qiita Advent Calendar 2024 Top
LoginSignup
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@ysgeso

Pythonで〇×ゲームのAIを一から作成する　その120　draw_subtree メソッドで表示する部分木の動的な作成

Last updated at Posted at 2024-09-29

目次と前回の記事

これまでに作成したモジュール

以下のリンクから、これまでに作成したモジュールを見ることができます。

リンク 説明
marubatsu.py Marubatsu、Marubatsu_GUI クラスの定義
ai.py AI に関する関数
test.py テストに関する関数
util.py ユーティリティ関数の定義。現在は gui_play のみ定義されている
tree.py ゲーム木に関する Node、Mbtree クラスの定義
gui.py GUI に関する処理を行う基底クラスとなる GUI クラスの定義

AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。

Mbtree_GUI の問題点

以前の記事で、必勝の局面で最も早く勝利する着手を選択するような評価値を計算するゲーム木を作成しましたが、現状の Mbtree_GUI は異なる方法で評価値を計算したゲーム木が複数あっても、その中の 1 つのゲーム木しか表示できない という問題があります。そこで、表示するゲーム木のデータを選択できる ように Mbtree_GUI を改良することにします。

ファイルの読み込み時間の問題

上記のような改良を行う際に問題となるのは、ゲーム木のデータをファイルから読み込む時間 です。ゲーム木の 部分木の表示 は、Mbtree クラスの draw_subtree メソッドで行いますが、その際には ゲーム木のデータが必要 になります。

ゲーム木のデータは、Mbtree クラスのインスタンスを作成 するか、下記のプログラムのように、ゲーム木のデータを ファイルから読み込む必要 がありますが、筆者のパソコンではインスタンスを作成する場合は約 1 分、下記のプログラムでファイルからデータを読み込む場合は 10 秒以上の時間がかかりました。

from tree import Mbtree, Mbtree_GUI

mbtree = Mbtree.load("../data/aidata")

そのため、複数の種類のゲーム木を Mbtree_GUI クラスで表示する ためには、ゲーム木のデータを ファイルから読み込む処理 が完了するまでの時間が これまで以上に長くなってしまう という問題が発生します。

そこで、ゲーム木のデータをファイルから読み込まず にゲーム木の 部分木を表示する ことができるようにプログラムを改良することにします。どのような方法で改良できるかについて少し考えてみて下さい。

部分木を表示するために必要なデータの考察

draw_subtree メソッドは、下記のプログラムのように 中心となるノード を表すキーワード引数 centernode と、表示する 部分木の深さの最大値 を表す maxdepth を記述して呼び出すことで部分木を表示します。例えば下記のプログラムでは実行結果のように、中心となるノードをルートノード、深さの最大値を 1 とした部分木が表示されます。

mbtree.draw_subtree(centernode=mbtree.root, maxdepth=1)

実行結果

draw_subtree が行う処理は、ゲーム木の中から 部分木のデータを取り出して表示を行う というものです。そのため、ゲーム木全体のデータが無くても 表示する部分木のノードのデータをその場で作ることができれば 上記のような部分木を表示することが可能です。

従って、draw_subtree の「作成済のゲーム木を使って部分木を表示する」という処理を「表示する部分木のデータをその場で新しく作成して表示する」ように 修正する ことで、ゲーム木のデータをあらかじめ作成したり、ファイルから読み込んでおく必要がなくなります。

動的なデータと静的なデータ

プログラムを実行した後 で必要に応じて その場で作成するデータ の事を 動的なデータ と呼びます。また、動的なデータを作成することを、データを 動的に作成する と表現します。

動的（dynamic）の反対は静的（static）で、ファイルに保存した aidata.mbtree のように、プログラムを実行する前 に あらかじめ計算 しておいたデータは 静的なデータ です。

動的なデータ は、そのデータが必要になるたびに作成するので、過去に作成したデータが再び必要になった場合であっても 必ず毎回作成しなければならない という 欠点 がありますが、データの 作成時間が短い場合 はそのことは 大きな問題にはなりません。

一方、静的なデータ は同じデータを何度も計算し直さなくても良いという利点がありますが、〇×ゲームのゲーム木のデータのように データサイズが大きい場合 はファイルから読み込むのに時間がかかる、メモリを大量に消費してしまうなどの 欠点があります。また、毎回計算結果が異なる ようなデータや、コンピューターが現実的に 扱うことができないような大きさ のデータ1は静的なデータでは扱えません。

どちらを使うかは状況によってそれぞれの 利点と欠点を考えて選択する必要があります。

部分木の動的な生成に必要な時間の考察

部分木のデータを動的に作成する処理に 長い時間がかかってしまうと意味がない ので、部分木のデータを作成するために 必要な時間を簡単に見積もってみる ことにします。

〇×ゲームのゲーム木の ノードの数 は以前の記事で説明したように 50 万以上 もあるため、ゲーム木の生成には約 1 分ほどの時間 がかかります。ゲーム木はノードを集めたデータで構成される ので、ゲーム木の 作成時間 は、ゲーム木の ノードの数にほぼ比例する と考えられます。そのため、例えばゲーム木の生成に 50 秒かかる場合は、1 つあたりのノードを作成 するために必要な時間は、50 / 50 万 = 約 0.0001 秒 と見積もることができます。

Marubatsu_GUI クラスで表示する 部分木のノードの数 は、多くても数十 しかありません。それより少し多めの 100 個のノード から構成される部分木のデータを作成する時間は、0.0001 × 100 = 約 0.01 秒と見積もることができるので、Marubatsu_GUI クラスで部分木を表示する際に、その 部分木のデータを動的に作成 した場合は その処理にかかる時間はほぼ無視して良い と考えて良いでしょう。

部分木の生成処理の実装

いきなり Marubatsu_GUI で表示するための部分木を作成するのは大変なので、少しずつ実装していくことにします。

__init__ メソッドの修正

これまでは、Mbtree クラスの インスタンスを作成 すると、〇×ゲームのゲーム木全体が作成されましたが、〇×ゲームの 部分木も作成できるように改良する ことにします。

そのために、下記のプログラムのように Mbtree クラスの __init__ メソッドに subtree という 仮引数を追加 し、True が代入 されていた場合は他の仮引数の値をすべて無視して 部分木（subtree）を作成する ように修正します。

なお、部分木を作成する処理を __init__ メソッド内に直接記述するとプログラムがわかりづらくなるので、その処理はこの後で定義する create_subtree という名前のメソッドに記述することにします。

  • 3 行目：デフォルト値を False とする仮引数 subtree を追加する
  • 4 ~ 6 行目：subtree が True の場合に、部分木を作成する処理を行う create_subtree メソッドを呼び出し、8 行目以降の通常のゲーム木を作成する処理を行わないようにするために return 文で __init__ メソッドの処理を終了する。
 1  from tree import Mbtree, Node
 2
 3  def __init__(self, algo="bf", shortest_victory=False, subtree=False):
 4      if subtree:
 5          self.create_subtree()
 6          return
 7    
 8      self.algo = algo
元と同じなので省略
 9    
10  Mbtree.__init__ = __init__
行番号のないプログラム 
from tree import Mbtree, Node

def __init__(self, algo="bf", shortest_victory=False, subtree=False):
    if subtree:
        self.create_subtree()
        return
    
    self.algo = algo
    self.shortest_victory = shortest_victory
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
        self.calc_score_by_bf()
    else:
        self.nodelist = [self.root]
        self.nodelist_by_depth = [[] for _ in range(10)]
        self.nodelist_by_depth[0].append(self.root)
        self.nodenum = 0
        self.create_tree_by_df(self.root)
        self.nodelist_by_score = []
        self.calc_score_by_df(self.root)
    self.nodelist_by_mb = {}
    self.bestmoves_by_mb = {}
    self.calc_bestmoves(self.root)
    
Mbtree.__init__ = __init__
修正箇所 
from tree import Mbtree, Node

-def __init__(self, algo="bf", shortest_victory=False):
+def __init__(self, algo="bf", shortest_victory=False, subtree=False):
+   if subtree:
+       self.create_subtree()
+       return
    
    self.algo = algo
元と同じなので省略
    
Mbtree.__init__ = __init__

ルートノードから深さ 1 までの部分木の生成

まず、先程 mbtree.draw_subtree(centernode=mbtree.root, maxdepth=1) というプログラムで表示した、ルートノードから深さ 1 までの部分木を生成 する処理を実装することにします。そのような部分木は下記の手順で実装できます。

  1. ゲーム開始時の局面を表すノードをルートノードとして作成する
  2. ゲーム開始時の局面のそれぞれの合法手を着手した局面を表すノードを作成し、ルートノードの子ノードにする

create_subtree メソッドの定義

上記の 手順 2 は、Node クラスの calc_children メソッドで行うことができるので、上記の処理は下記のプログラムで行うことができます。

なお、create_tree_by_bf などの関数でゲーム木を作成する際に計算していた nodelist などの属性は、draw_subtree で 部分木を表示する際に必要がない ので、下記のプログラムでは 計算していません2。

  • 3 ~ 5 行目：create_subtree を定義する
  • 4 行目：ゲーム開始時の局面を表すルートノードを作成し、root 属性に代入する
  • 5 行目：calc_children メソッドで、ルートノードの子ノードを作成する
1  from marubatsu import Marubatsu
2
3  def create_subtree(self):
4      self.root = Node(Marubatsu())
5      self.root.calc_children()
6
7  Mbtree.create_subtree = create_subtree
行番号のないプログラム 
from marubatsu import Marubatsu

def create_subtree(self):
    self.root = Node(Marubatsu())
    self.root.calc_children()

Mbtree.create_subtree = create_subtree

上記を実行後に、下記のプログラムのようにキーワード引数 subtree=True を記述して部分木を作成し、draw_subtree で ルートノードから深さ 1 までの部分木を表示 すると、実行結果の左図が表示されます。subtree は、下記の 2 行目で 表示するノードのデータを全て含んでいる のでこのプログラムで正しい部分木が表示されます。

右図は先ほどのプログラムで ゲーム木を全体を表す mbtree に対して 同じ範囲の部分木を表示 した場合の図を再掲したものです。同じ部分木が表示される ことを確認して下さい。

subtree = Mbtree(subtree=True)
subtree.draw_subtree(centernode=subtree.root, maxdepth=1)

実行結果

　　　　　

なお、create_subtree では、ノードの評価値の計算を行っていない ので 評価値は表示されず、ゲーム盤の色は常に白色で表示 されます。また、深さ 1 のノードの子ノードを計算していない ので、左図ではその右に 子ノードが存在することを表す線は表示されません。それらの表示ついては後で実装します。

部分木の深さの最大値の指定

次に、作成する 部分木の深さの最大値 を指定できるようにします。そのための方法の一つに、下記のプログラムのように __init__ メソッドに部分木の深さの最大値を表す仮引数を maxdepth を追加するという方法が考えられます。

def __init__(self, algo="bf", shortest_victory=False, subtree=False, maxdepth=1):
略

しかし、この方法では部分木を作成する際に必要となるデータを代入する 仮引数を今後増やした場合 に、以下のような問題が発生 します。

  • そのような仮引数を追加するたびに __init__ メソッドを修正 する必要がある
  • 通常のゲーム木を作成するための仮引数と、部分木を作成するための仮引数 の 区別がわかりづらくなる

そこで、本記事では 部分木を作成する場合 は、仮引数 subtree に代入する部分木の作成に必要なデータを dict の形式で例えば { "maxdepth": 2 } のように記述する ことにします。また、部分木を作成しない場合 は仮引数 subtree に None を代入する ことにします。

__init__ メソッドの修正

仮引数 subtree の データ構造を変更 したので、__init__ メソッドを下記のプログラムのように修正する必要があります。

  • 1 行目：仮引数 subtree のデフォルト値を None に修正する
  • 2 行目：条件式を None でないことを判定するように修正する
  • 3 行目：仮引数 subtree を同名の属性に代入する
1  def __init__(self, algo="bf", shortest_victory=False, subtree=None):
2      if subtree is not None:
3          self.subtree = subtree
4          self.create_subtree()
5          return
6      
7      self.algo = algo
元と同じなので省略
8    
9  Mbtree.__init__ = __init__
行番号のないプログラム 
def __init__(self, algo="bf", shortest_victory=False, subtree=None):
    if subtree is not None:
        self.subtree = subtree
        self.create_subtree()
        return
    
    self.algo = algo
    self.shortest_victory = shortest_victory
    Node.count = 0
    self.root = Node(Marubatsu())
    if self.algo == "bf":  
        self.create_tree_by_bf()
        self.calc_score_by_bf()
    else:
        self.nodelist = [self.root]
        self.nodelist_by_depth = [[] for _ in range(10)]
        self.nodelist_by_depth[0].append(self.root)
        self.nodenum = 0
        self.create_tree_by_df(self.root)
        self.nodelist_by_score = []
        self.calc_score_by_df(self.root)
    self.nodelist_by_mb = {}
    self.bestmoves_by_mb = {}
    self.calc_bestmoves(self.root)
    
Mbtree.__init__ = __init__
修正箇所 
-def __init__(self, algo="bf", shortest_victory=False, subtree=False):
+def __init__(self, algo="bf", shortest_victory=False, subtree=None):
-   if subtree:
+   if subtree is not None:
+       self.subtree = subtree
        self.create_subtree()
        return
    
    self.algo = algo
元と同じなので省略
    
Mbtree.__init__ = __init__

create_subtree の修正

次に、subtree 属性の maxdepth のキーの値の深さまで部分木を作成する ように、create_subtree を修正する必要があります。その処理は幅優先アルゴリズムと深さ優先アルゴリズムのどちらを使っても実装できますが、今回の記事では幅優先アルゴリズムで実装することにします。深さ優先アルゴリズムで実装したい方はチャレンジしてみて下さい。

下記は create_subtree を修正したプログラムです。行う処理は幅優先アルゴリズムでゲーム木全体を作成する create_tree_by_bf と下記の点を除いて ほぼ同じ なので比較してみて下さい。なお、元の create_subtree から大きく修正したので、修正箇所は省略しました。

  • nodelist_by_depth 属性など、draw_subtree で部分木を表示する際に必要がない属性を計算しない
  • 計算する部分木の深さを maxdepth までとする
  • 途中経過や結果を print で表示しない

下記は、create_tree_by_bf と異なる部分の説明です。

  • 6 行目：部分木の深さの最大値を表すデータを subtree 属性から取り出して maxdepth に代入する
  • 7 ~ 13 行目：処理を行う深さが depth のノードが存在し、なおかつ 深さが maxdepth 未満の間 繰り返し処理を行う。この繰り返し処理で 作成されるのは depth + 1 の深さのノード なので、7 行目の条件式は、maxdepth 以下ではなく、maxdepth 未満であることを判定する必要がある 点に注意する事
 1  def create_subtree(self):
 2      self.root = Node(Marubatsu())
 3   
 4      depth = 0
 5      nodelist = [self.root]
 6      maxdepth = self.subtree["maxdepth"]
 7      while len(nodelist) > 0 and depth < maxdepth:
 8          childnodelist = []
 9          for node in nodelist:
10              node.calc_children()
11              childnodelist += node.children
12          nodelist = childnodelist
13          depth += 1
14
15  Mbtree.create_subtree = create_subtree
行番号のないプログラム 
def create_subtree(self):
    self.root = Node(Marubatsu())
    
    depth = 0
    nodelist = [self.root]
    maxdepth = self.subtree["maxdepth"]
    while len(nodelist) > 0 and depth < maxdepth:
        childnodelist = []
        for node in nodelist:
            node.calc_children()
            childnodelist += node.children
        nodelist = childnodelist
        depth += 1

Mbtree.create_subtree = create_subtree

実行結果は同じなので省略しますが、上記の修正後に下記のプログラムを実行すると、先程と同じルートノードから深さ 1 までの部分木が表示されます。

subtree = Mbtree(subtree={"maxdepth": 1})
subtree.draw_subtree(centernode=subtree.root, maxdepth=1)

また、図がかなり大きいので実行結果は省略しますが、下記のプログラムを実行すると、深さ 2 までの部分木が表示されます。

subtree = Mbtree(subtree={"maxdepth": 2})
subtree.draw_subtree(centernode=subtree.root, maxdepth=2)

中心となるノードの指定

次に、中心となるノードを指定した部分木 を作成できるようにします。その際に、中心となるノードを指定する方法を決める 必要がありますが、本記事では中心となるノードを表す 局面のデータ を、仮引数 subtree に代入する dict の centermb というキーに代入する ことにします。具体的には、(1, 1) に〇を着手した局面を表すノードを中心とする深さ 2 までの部分木を、下記のプログラムのように記述して作成します。

mb = Marubatsu()
mb.move(1, 1)
subtree = Mbtree(subtree={"centermb": mb, "maxdepth": 2})

draw_subtree メソッドと同様に、centernode というキーに中心となるノードのデータを代入すれば良いと思った人がいるかもしれませんが、これから作成する部分木の中心となるノードを、部分木を作成する前に指定することは不可能 なので、ノードのデータではなく、ノードが表す局面のデータを代入する必要があります。

作成する部分木の検証

次に、どのように部分木を作成するかを考える必要があります。draw_subtree でゲーム木の 部分木をどのように表示するか について忘れた方は以前の記事を復習して下さい。また、どうしてもイメージがわかない人は、下記のプログラムのように実際に draw_subtree で部分木を表示してみると良いでしょう。下記は、深さが 2 のノードを中心とする深さ 3 までの部分木を表示するプログラムです。なお、中心となるノードがどれであるかがわかるように、赤い枠が表示される選択されたノードを中心となるノードと同じにしました。

centernode = mbtree.nodelist_by_depth[2][0]
maxdepth = 3
mbtree.draw_subtree(centernode=centernode, selectednode=centernode, maxdepth=maxdepth)

実行結果

draw_subtree で表示する部分木は、中心となるノードの深さを d、部分木の 深さの最大値を maxdepth とすると、以下のようなノードを持つ部分木です。

  • 深さが 0 ~ d - 1 のノードは、中心となるノードの 先祖ノード である
  • 深さが d のノードは、中心となるノードとその兄弟ノード（中心となるノードの親ノードの子ノード）である
  • 深さが d + 1 ~ maxdepth のノードは、中心となるノードのすべての 子孫ノード である

このような部分木を作成するためには、calc_subtree メソッド内で 子ノードを作成する処理を行う際 に、ノードの深さによって 下記のような 異なる処理を行う必要 があります。

深さ 行う処理
0 ~ d - 2 その局面から、中心となるノードに至るために行う必要がある着手 を行った子ノードを作成する
d - 1 その局面のすべての合法手に対応する子ノードを作成する
ただし、次の深さの子ノードの一覧には、中心となるノードのみを登録する
d ~ maxdepth - 1 その局面のすべての合法手に対応する子ノードを作成する

深さ 0 ~ d - 2 では、その局面から 中心となるノードに至るための着手 を行う必要がありますが、その着手は、中心となるノードの局面を表す Marubatsu クラスのインスタンスの、棋譜を表す records 属性に代入されています。

draw_subtree の修正

下記は、上記の方針に従って、calc_subtree を修正したプログラムです。

  • 8 行目：中心となるノードを表す局面を centermb に代入する
  • 9 行目：中心となるノードの深さは、局面の手数を表す move_count 属性に代入されているので、それを centerdepth に代入する
  • 10 行目：中心となるノードの局面に至るまでの棋譜が代入されている records 属性を records に代入する
  • 15 ~ 28 行目：深さ depth のそれぞれのノードの子ノードを作成する処理を、ノードの深さに応じた処理を行うように修正する
  • 15 ~ 21 行目：深さが centerdepth - 2 以下の場合の処理を行う
  • 16 行目：ノードの局面を表すデータを deepcopy でコピーする
  • 17 行目：そのノードから中心となるノードに至るための着手を records から取り出す。深さが depth の局面に対して行われた着手は、records の depth + 1 番の要素に代入されている点に注意すること
  • 18 ~ 20 行目：着手を行った局面を表す子ノードを作成し、ノードの子ノードに挿入する
  • 21 行目：部分木の次の深さのノードの一覧に上記で作成した子ノードを追加する
  • 23 行目：深さが centerdepth - 2 より大きい場合は、その局面の全ての合法手に対応する子ノードを作成する点は共通するのでその処理を行う
  • 24 ~ 26 行目：深さが centerdepth - 1 の場合は、次の深さのノードの一覧には、中心となるノードのみを追加する必要がある。その子ノードは records の depth + 1 番の要素に代入されている着手を行った場合のノードなので、Node の children_by_move 属性を利用して中心となるノードを計算することができる。中心となるノードを centernode 属性に代入し、26 行目でその子ノードのみを次の深さのノードの一覧に追加する
  • 27、28 行目：深さが centerdepth 以上の場合は、作成した全ての子ノードを、次の深さのノードの一覧に追加する

なお、25 行目で、中心となるノードを centernode 属性に代入した理由については、このすぐ後で説明します。

 1  from copy import deepcopy
 2
 3  def create_subtree(self):
 4      self.root = Node(Marubatsu())
 5   
 6      depth = 0
 7      nodelist = [self.root]
 8      centermb = self.subtree["centermb"]
 9      centerdepth = centermb.move_count
10      records = centermb.records
11      maxdepth = self.subtree["maxdepth"]
12      while len(nodelist) > 0 and depth < maxdepth:
13          childnodelist = []
14          for node in nodelist:
15              if depth <= centerdepth - 2:
16                  childmb = deepcopy(node.mb)
17                  x, y = records[depth + 1]
18                  childmb.move(x, y)
19                  childnode = Node(childmb, parent=node, depth=depth+1)   
20                  node.insert(childnode)
21                  childnodelist.append(childnode)
22              else:
23                  node.calc_children()
24                  if depth == centerdepth - 1:
25                      self.centernode = node.children_by_move[records[depth + 1]]
26                      childnodelist.append(self.centernode)
27                  else:
28                      childnodelist += node.children
29          nodelist = childnodelist
30          depth += 1
31
32  Mbtree.create_subtree = create_subtree
行番号のないプログラム 
from copy import deepcopy

def create_subtree(self):
    self.root = Node(Marubatsu())
    
    depth = 0
    nodelist = [self.root]
    centermb = self.subtree["centermb"]
    centerdepth = centermb.move_count
    records = centermb.records
    maxdepth = self.subtree["maxdepth"]
    while len(nodelist) > 0 and depth < maxdepth:
        childnodelist = []
        for node in nodelist:
            if depth <= centerdepth - 2:
                childmb = deepcopy(node.mb)
                x, y = records[depth + 1]
                childmb.move(x, y)
                childnode = Node(childmb, parent=node, depth=depth+1)   
                node.insert(childnode)
                childnodelist.append(childnode)
            else:
                node.calc_children()
                if depth == centerdepth - 1:
                    self.centernode = node.children_by_move[records[depth + 1]]
                    childnodelist.append(self.centernode)
                else:
                    childnodelist += node.children
        nodelist = childnodelist
        depth += 1

Mbtree.create_subtree = create_subtree
修正箇所 
from copy import deepcopy

def create_subtree(self):
    self.root = Node(Marubatsu())
    
    depth = 0
    nodelist = [self.root]
+   centermb = self.subtree["centermb"]
+   centerdepth = centermb.move_count
+   records = centermb.records
    maxdepth = self.subtree["maxdepth"]
    while len(nodelist) > 0 and depth < maxdepth:
        childnodelist = []
        for node in nodelist:
-           node.calc_children()
-           childnodelist += node.children
+           if depth <= centerdepth - 2:
+               childmb = deepcopy(node.mb)
+               x, y = records[depth + 1]
+               childmb.move(x, y)
+               childnode = Node(childmb, parent=node, depth=depth+1)   
+               node.insert(childnode)
+               childnodelist.append(childnode)
+           else:
+               node.calc_children()
+               if depth == centerdepth - 1:
+                   self.centernode = node.children_by_move[records[depth + 1]]
+                   childnodelist.append(self.centernode)
+               else:
+                   childnodelist += node.children
        nodelist = childnodelist
        depth += 1

Mbtree.create_subtree = create_subtree

上記の修正後に、下記のプログラムで (0, 0)、(1, 1) の順で着手を行った局面を中心とする深さが 3 の部分木を表示すると、実行結果の左のように部分木が正しく表示されるようになることが確認できます。先ほどのゲーム木全体のデータを使って同じ部分木を表示した結果を表す右図と比較して下さい。

なお、calc_subtree の 25 行目で 中心となるノードを centernode 属性に代入した理由 は、draw_subtree メソッドのキーワード引数 centernode に中心となるノードを記述する必要がある からです。25 行目の処理を行わない場合は、部分木を作成した後で、作成した部分木のノードの中から 中心となるノードを探す処理を記述する必要 がある点が面倒です。

mb = Marubatsu()
mb.move(0, 0)
mb.move(1, 0)
maxdepth = 3
subtree = Mbtree(subtree={"centermb": mb, "maxdepth": maxdepth})
centernode = subtree.centernode
subtree.draw_subtree(centernode=centernode, selectednode=centernode, maxdepth=maxdepth)

実行結果

　　　　　

兄弟ノードの子ノードを表す線の表示

上記の図を見比べるとわかると思いますが、左図では中心となるノードの 兄弟ノード に、子ノードが存在することを表す線が表示されない という問題があります。これは、現状では 兄弟ノードの子ノードを計算していないことが原因 なので、兄弟ノードに合法手が存在する場合は子ノードを計算するようにプログラムを修正することで、右図のような表示が行われるようになります。

なお、右上に並んでいる、中心となるノードの子ノードも同様に、子ノードが存在することを表す線が存在しませんが、そちらに関しては次回の記事で修正します。

子ノードが存在することを表す線が表示される条件の検証

上記では、兄弟ノードの子ノードを計算するという方法を説明しましたが、実際にはもっと簡単な方法でこの問題を解決することができます。子ノードが存在することを表す線 は Node クラスの draw_node メソッドで表示されますが、その処理は下記のプログラムのコメントが示すように、子ノードを表す children 属性に要素が 1 つ以上存在する場合 に表示するようになっています。

def draw_node(略):
略
        # 子ノードが存在する場合に、エッジの線と子ノードを描画する
        if len(self.children) > 0:
略

そのため、兄弟ノードの右に線を表示するために、兄弟ノードの 子ノードを実際に計算する必要はなく、何らかの要素を持つ list を children 属性に代入する だけでかまいません。

下記のプログラムはそのように calc_subtree を修正したプログラムです。この処理は見た目の意味がわかりづらい処理なので、コメントを詳しく記しました。

  • 2 ~ 13 行目：中心となるノードの親ノードに対するの処理を記述する
  • 3 行目：中心となるノードの親ノードの children_by_move 属性を利用して、中心となるノードとその兄弟ノードに対する繰り返し処理を行う。なお、children_by_move に代入された dict のキーは行った着手を、キーの値はその着手を行った子ノードを表す
  • 4 行目：childnode が中心となるノードであるかを、children_by_move から取り出したキーと、中心となるノードの局面が depth 手目に行った着手を表す records[depth + 1] が一致するかどうかで判定する
  • 5、6 行目：childnode が中心となるノードであると判定された場合は、centernode 属性に代入し、childnodelist に追加する（元のプログラムと同じ処理を行う）
  • 7 ~ 13 行目：childnode が兄弟ノードであると判定された場合は、合法手が存在するかどうかをゲーム中であるかどうかで判定し、合法手が存在する場合は children 属性に要素を追加する。ここでは None を追加しているが、どのような値を追加してもかまわない
 1  def create_subtree(self):
元と同じなので省略      
 2              if depth == centerdepth - 1:
 3                  for move, childnode in node.children_by_move.items():
 4                      if move == records[depth + 1]:
 5                          self.centernode = childnode
 6                          childnodelist.append(self.centernode)
 7                      else:
 8                          if childnode.mb.status == Marubatsu.PLAYING:
 9                              # draw_subtree でこの部分木を表示する際に、中心となるノードの
10                              # 兄弟ノードの右に子ノードが存在することを表す線を描画したい
11                              # その線は Node クラスの draw_node で children 属性に 1 つ以上の
12                              # 要素が存在する場合に描画されるので None を要素として追加する
13                              childnode.children.append(None)
元と同じなので省略

Mbtree.create_subtree = create_subtree
行番号のないプログラム 
def create_subtree(self):
    self.root = Node(Marubatsu())
    
    depth = 0
    nodelist = [self.root]
    centermb = self.subtree["centermb"]
    centerdepth = centermb.move_count
    records = centermb.records
    maxdepth = self.subtree["maxdepth"]
    while len(nodelist) > 0 and depth < maxdepth:
        childnodelist = []
        for node in nodelist:
            if depth < centerdepth - 1:
                childmb = deepcopy(node.mb)
                x, y = records[depth + 1]
                childmb.move(x, y)
                childnode = Node(childmb, parent=node, depth=depth+1)   
                node.insert(childnode)
                childnodelist.append(childnode)
            else:
                node.calc_children()                   
                if depth == centerdepth - 1:
                    for move, childnode in node.children_by_move.items():
                        if move == records[depth + 1]:
                            self.centernode = childnode
                            childnodelist.append(self.centernode)
                        else:
                            if childnode.mb.status == Marubatsu.PLAYING:
                                # draw_subtree でこの部分木を表示する際に、中心となるノードの
                                # 兄弟ノードの右に子ノードが存在することを表す線を描画したい
                                # その線は Node クラスの draw_node で children 属性に 1 つ以上の
                                # 要素が存在する場合に描画されるので None を要素として追加する
                                childnode.children.append(None)
                else:
                    childnodelist += node.children
        nodelist = childnodelist
        depth += 1

Mbtree.create_subtree = create_subtree
修正箇所 
def create_subtree(self):
元と同じなので省略      
                if depth == centerdepth - 1:
-                   self.centernode = node.children_by_move[records[depth + 1]]
-                   childnodelist.append(self.centernode)
+                   for move, childnode in node.children_by_move.items():
+                       if move == records[depth + 1]:
+                           self.centernode = childnode
+                           childnodelist.append(self.centernode)
+                       else:
+                           if childnode.mb.status == Marubatsu.PLAYING:
                                # draw_subtree でこの部分木を表示する際に、中心となるノードの
                                # 兄弟ノードの右に子ノードが存在することを表す線を描画したい
                                # その線は Node クラスの draw_node で children 属性に 1 つ以上の
                                # 要素が存在する場合に描画されるので None を要素として追加する
+                               childnode.children.append(None)
元と同じなので省略

Mbtree.create_subtree = create_subtree

上記の修正後に下記のプログラムを実行すると、実行結果の左のように、兄弟ノードの右に子ノードが存在することを表す線が表示されるようになったことが確認できます。修正前の右図と比較して下さい。

mb = Marubatsu()
mb.move(0, 0)
mb.move(1, 0)
maxdepth = 3
subtree = Mbtree(subtree={"centermb": mb, "maxdepth": 3})
centernode = subtree.centernode
subtree.draw_subtree(centernode=centernode, selectednode=centernode, maxdepth=maxdepth)

実行結果

　　　　　

今回の記事はいつもより少し短いですがここまでにします。しばらくの間は筆者の都合により記事が短くなると思いますが、引き続き連載は続けていく予定です。

今回の記事のまとめ

今回の記事では draw_subtree で部分木を表示する際に、あらかじめゲーム木全体を作成しておくのではなく、必要な 部分木を動的に作成 して表示するという修正を始めました。

まだ修正は完了していないので、修正の続きは次回の記事で行います。

本記事で入力したプログラム

リンク 説明
marubatsu.ipynb 本記事で入力して実行した JupyterLab のファイル
tree_new.py 今回の記事で更新した tree.py

次回の記事

  1. 例えば、将棋や囲碁のゲーム木はノードの数が多すぎるため、静的なデータとしてあらかじめ計算しておくことは不可能です ↩

  2. draw_subtree で表示する以外の目的で部分木を作成する場合は、必要に応じてそれらの属性を計算する必要があります ↩

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?