<jupyter_start><jupyter_text>Pythonでごぶの探索設計図: https://docs.google.com/presentation/d/1wmV3fb-fx1qQahOk2ZkiEcQjAm2EgGZrNFMwcBmwSnc/edit?usp=sharing  Stateに必要な関数群  stateの引数  id<jupyter_code>from typing import List
import itertools

# idは134bitの文字列
# stateの引数からidを作成
def create_id(is_first: bool, is_choise: bool ,choise_board: List[List[bool]],
              choise_hand: List[bool] ,board: List[List[bool]], hand: List[bool]):
  big_list = [int(is_first)] + [int(is_choise)] \
          + list(itertools.chain.from_iterable(choise_board)) + choise_hand \
          + list(itertools.chain.from_iterable(board)) + hand;
  id = "".join(map(str, big_list))
  return id;

# idからstateの引数を作成
def id2is_first(id: str):
  return id[0];
def id2is_choise(id: str):
  return id[1];
def id2choise_board(id: str):
  choise_board = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                  [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
  for i, str_bit in enumerate(id[2:2+54]):
      choise_board[i//9][i%9] = int(str_bit)
  return choise_board;
def id2choise_hand(id: str):
  choise_hand = [0,0,0,0,0,0,0,0,0,0,0,0]
  for i, str_bit in enumerate(id[56:56+12]):
      choise_hand[i] = int(str_bit)
  return choise_hand;
def id2board(id: str):
  board = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
           [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
  for i, str_bit in enumerate(id[68:68+54]):
      board[i//9][i%9] = int(str_bit)
  return board;
def id2hand(id: str):
  hand = [0,0,0,0,0,0,0,0,0,0,0,0]
  for i, str_bit in enumerate(id[122:122+12]):
      hand[i] = int(str_bit)
  return hand;<jupyter_output><empty_output><jupyter_text>正規化<jupyter_code># 正規化
def create_normalization_board(board):
  board = board # 候補
  # 変換表を一つずつためし、cand_boardと比較して小さい方を残す
  convert_tables = [[6,3,0,7,4,1,8,5,2],[8,7,6,5,4,3,2,1,0],[2,5,8,1,4,7,0,3,6],
  [2,1,0,5,4,3,8,7,6],[6,7,8,3,4,5,0,1,2],[0,3,6,1,4,7,2,5,8],[8,5,2,7,4,1,6,3,0]]
  for convert_table in convert_tables:
    cand_board = [
                  [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                  [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]];
    for i in range(6):
      for j, num in enumerate(convert_table):
        cand_board[i][j] = board[i][num]
    # cand_pieces と temp_cand_pieces を比較
    if board > cand_board:
      board = cand_board
  return board
def create_normalization_hand(hand):
  hand = hand # 候補
  # "1,0" を "0,1"にするだけ。
  for i in range(6):
    if hand[2*i] == 1 and hand[2*i+1] == 0:
      hand[2*i] = 0
      hand[2*i+1] = 1
  return hand<jupyter_output><empty_output><jupyter_text>合法手<jupyter_code># 合法手の作成
import copy

def create_legal_actions(is_first, is_choise, choise_board, choise_hand, board, hand):
  if is_choise == True: # stateはchoise、ここではchoiseした駒を置く行動を絞り込む
    # 1. 一旦すべての行動を禁止する。
    actions = [
               [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]],
               [0,0,0,0,0,0,0,0,0,0,0,0]]
    choise_piece_size = 0 # 0~5
    # 2. choiseした駒が手駒なら、
    if choise_hand != [0,0,0,0,0,0,0,0,0,0,0,0]:
      # 2-1. 選択した駒と同じtypeすべての盤面の行動を許可する
      for i, piece in enumerate(choise_hand):
        if piece == 1:
          choise_piece_size = i//2 # 0~11 -> 0~5
          actions[0][choise_piece_size] = [1,1,1,1,1,1,1,1,1]
        break;
    # 3. choiseした駒が盤面の駒なら、
    else:
      # 3-1. 選択した駒と同じtypeすべての盤面の行動を許可する
      for i in range(6):
        if choise_board[i] != [0,0,0,0,0,0,0,0,0]:
          choise_piece_size = i
          actions[0][choise_piece_size] = [1,1,1,1,1,1,1,1,1]
          break;
      # 3-2. 選択した駒がもとあった位置の盤面の行動を禁止する
      for place, is_exist in enumerate(choise_board[choise_piece_size]):
        if is_exist == 1: 
          actions[0][choise_piece_size][place] = 0
          break;
	    # 3-3. 選択した駒と同じ大きさ以上の駒が盤面にあるなら、
      # if board[選択した駒と同じ大きさ以上のtype][place] == 1:

        #   actions[0][type][place] = 0
      check_piece_sizes = [[0,3], [0,1,3,4], [0,1,2,3,4,5]]
      for check_piece_size in check_piece_sizes[(choise_piece_size) % 3]:
        for place, is_exist in enumerate(board[check_piece_size]): 
          if is_exist == 1: 
            #   3-3-1.その場所にはおけない
            actions[0][choise_piece_size][place] = 0

  else: # is_choise == False: # stateはput、ここではchoiseする駒を選べる行動を絞り込む
    # 1. 配置されている駒はすべて許可する
    actions = [copy.deepcopy(board), copy.deepcopy(hand)]
    # 2. 現在の手番プレイヤーの駒の行動を禁止する(手番が交代するから)
    if is_first == 1: # 先手の駒を行動不可にする
      for i in [0,1,2]:
        actions[0][i] = [0,0,0,0,0,0,0,0,0] # 	2-1. ボードの行動の禁止
      for i in [0,1,2,3,4,5]: # 	2-2. 手駒の行動の禁止
        actions[1][i] = 0
    else: # 後手の駒を行動不可にする
      for i in [3,4,5]:
        actions[0][i] = [0,0,0,0,0,0,0,0,0] # 	2-1. ボードの行動の禁止
      for i in [6,7,8,9,10,11]: # 	2-2. 手駒の行動の禁止
        actions[1][i] = 0
    # 3. ボード上の駒を調べ、LがあるplaceのM,Sを行動不可, MがあるplaceのSを行動不可にする。
    piece_sizes = {"M, S": [1,2,4,5],"S": [2,5]}
    for place in range(9):
      # 3-1. ボードにL駒が配置されているなら
      if board[0][place] == 1 or board[3][place] == 1:
        # 3-1-1. 同じ場所のM,Sの行動を禁止する
        for piece_size in piece_sizes["M, S"]:
          actions[0][piece_size][place] = 0
      # 3.2 ボードにM駒が配置されているなら
      elif board[1][place] == 1 or board[4][place] == 1:
        # 3-2-1. 同じ場所のSの行動を禁止する
        for piece_size in piece_sizes["S"]:
          actions[0][piece_size][place] = 0
  return actions<jupyter_output><empty_output><jupyter_text>次の状態<jupyter_code># 次の状態の作成
def create_next_states(is_first, is_choise, choise_board, choise_hand, board, hand, actions):
  next_states = []
  next_is_choise = int(not is_choise)
  next_is_first = int(not is_first) if next_is_choise == 1 else is_first # 次がchoiseなら反転
  # 現在is_choise== 1 なら、actionにはchoiseした駒をおける場所が入っている。
  # action[1]にビットが立っていることはない.
  # action[0][type][place]== 1のとき、 board[type][place] = 1にする。
  if is_choise == 1: # 手番を継続, 次はセット, actionをboard, handに反映する

    # print("create_next_states : setなステートを作成する")

    next_choise_board = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                          [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]];
    next_choise_hand = [0,0,0,0,0,0,0,0,0,0,0,0]
    for piece_type_num, piece_type in enumerate(actions[0]):
      for place_num, place in enumerate(piece_type):
        # print("place_num = {}, place = {}".format(place_num, place))
        if place == 1: # 行動可能ならその箇所を1にする
          next_board = copy.deepcopy(board)
          next_board[piece_type_num][place_num] = 1
          state = State(next_is_first, next_is_choise,
                  next_choise_board, next_choise_hand,
                  next_board, copy.deepcopy(hand))
          next_states.append(state)
  # 現在is_choise== 0 なら、actionにはchoiseできる駒の位置が入っている。
  # action[0][place]== 1のとき、 hand[place] = 0、choise_hand[place] = 1にする。
  # action[0][type][place]== 1のとき、 board[type][place] = 0、choise_board[place] = 1にする。
  else: # is_choise == 0: # 手番を交代、次はチョイス, actionをchise_board, chise_handに反映する

    print("create_next_states : choiseなステートを作成する")
    
    # 盤面からchoiseする
    for piece_type_num, piece_type in enumerate(actions[0]):
      for place_num, place in enumerate(piece_type):
        if place == 1: # 行動可能ならその箇所のchoise_boardを1にして、その箇所のboardを0にする
          next_choise_board = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                                [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]];
          next_board = copy.deepcopy(board)
          next_choise_board[piece_type_num][place_num] = 1
          next_board[piece_type_num][place_num] = 0
          state = State(next_is_first, next_is_choise,
                  next_choise_board, [0,0,0,0,0,0,0,0,0,0,0,0],
                  next_board, hand)
          next_states.append(state)
    # ハンドからchoiseする
    for place_num, place in enumerate(actions[1]):
      if place == 1: # 行動可能ならその箇所のchoise_handを1にして、その箇所のhandを0にする
        next_choise_hand = [0,0,0,0,0,0,0,0,0,0,0,0]
        next_hand = copy.deepcopy(hand)
        next_choise_hand[place_num] = 1
        next_hand[place_num] = 0
        state = State(next_is_first, next_is_choise,
                [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                  [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]],
                next_choise_hand, board, next_hand)
        next_states.append(state)    
  return next_states<jupyter_output><empty_output><jupyter_text>結果<jupyter_code># 勝敗の有無
def is_win(single_surface):
  s = single_surface
  # 横, 縦, 左斜め, 右斜めのラインを調べる
  check_lines = [[0,1,2], [3,4,5], [6,7,8], [0,3,6], [1,4,7], [2,5,8], [0,4,8], [2,4,6]]
  for check_line in check_lines:
    if s[check_line[0]] and s[check_line[1]] and s[check_line[2]]:
      return True;
  return False;
# 表面の駒だけbitが立つboardを作成する
def create_surface(board):
  board_surface = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                   [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]];
  # S駒を反映させる
  board_surface[2] = board[2]
  board_surface[5] = board[5]
  # このとき、おいた場所により小さい駒があったら、その駒を0にする
  # １マスずつ見ていく
  for place in range(9):
    # M駒を反映させる
    if board[1][place] == 1 or board[4][place] == 1:
      if board[1][place] == 1:
        board_surface[1][place] = 1
      if board[4][place] == 1:
        board_surface[4][place] = 1
      board_surface[2][place] = 0 # S駒を0にする
      board_surface[5][place] = 0
    # L駒を反映させる
    if board[0][place] == 1 or board[3][place] == 1:
      if board[0][place] == 1:
        board_surface[0][place] = 1
      if board[3][place] == 1:
        board_surface[3][place] = 1
      board_surface[1][place] = 0 # M駒を0にする
      board_surface[4][place] = 0	
      board_surface[2][place] = 0 # S駒を0にする
      board_surface[5][place] = 0
  return board_surface

#勝敗の有無、勝者を確認する
def check_result(board):
  board_surface = create_surface(board)
  is_done = 0 # 決着がついているなら1を返す
  winner = 0 # 先手は0, 後手は1
  # 内部でboard_surface[0,1,2]とboard_surface[3,4,5]を合成
  single_surfaces = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]];
  for i in range(9):
    if board_surface[0][i] == 1 or board_surface[1][i] == 1 or board_surface[2][i] == 1:
      single_surfaces[0][i] = 1
    elif board_surface[3][i] == 1 or board_surface[4][i] == 1 or board_surface[5][i] == 1:
      single_surfaces[1][i] = 1
  is_done = is_win(single_surfaces[0]) == 1 or is_win(single_surfaces[1]) == 1
  winner = 1 if is_win(single_surfaces[1]) == 1 else 0
  return [is_done, winner]<jupyter_output><empty_output><jupyter_text>Stateクラス<jupyter_code># stateクラス
class State():
  def __init__(self, is_first, is_choise, choise_board, choise_hand, board, hand):
    self.is_first = is_first
    self.is_choise = is_choise
    self.choise_board = choise_board
    self.choise_hand = choise_hand
    self.board = board
    self.hand = hand
    self.id = create_id(self.is_first, self.is_choise, self.choise_board,
        self.choise_hand, self.board, self.hand)
    self.normalized_id = create_id(
        self.is_first, self.is_choise,
        create_normalization_board(self.choise_board), create_normalization_hand(self.choise_hand),
        create_normalization_board(self.board), create_normalization_hand(self.hand))
    self.legal_actions = create_legal_actions(
        self.is_first, self.is_choise, self.choise_board,
        self.choise_hand, self.board, self.hand)
    self.is_done, self.winner = check_result(self.board)
  # 次の状態の作成
  def next_states(self):
    states = create_next_states(
        self.is_first, self.is_choise, self.choise_board,
        self.choise_hand, self.board, self.hand, self.legal_actions)
    return states<jupyter_output><empty_output><jupyter_text>Stateクラスのテスト<jupyter_code># テスト

# 初期(setステート)
is_first = False
is_choise = False
choise_board = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                                 [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
choise_hand = [0,0,0,0,0,0,0,0,0,0,0,0]
board = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                          [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
hand = [1,1,1,1,1,1,1,1,1,1,1,1]
legal_actions = [
  [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
  [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]],
  [1,1,1,1,1,1,0,0,0,0,0,0]]

# # 1手目代表(choiseステート)
# is_first = True
# is_choise = True
# choise_board = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
#                                  [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
# choise_hand = [1,0,0,0,0,0,0,0,0,0,0,0]
# board = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
#                           [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
# hand = [0,1,1,1,1,1,1,1,1,1,1,1]
# legal_actions = [
#   [[1,1,1,1,1,1,1,1,1],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
#   [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]],
#   [0,0,0,0,0,0,0,0,0,0,0,0]]

# # 1手目代表(setステート)
# is_first = True
# is_choise = False
# choise_board = [[1,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
#                                  [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
# choise_hand = [0,0,0,0,0,0,0,0,0,0,0,0]
# board = [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
#                           [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
# hand = [0,1,1,1,1,1,1,1,1,1,1,1]
# legal_actions = [
#   [[1,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
#   [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]],
#   [0,1,1,1,1,1,1,1,1,1,1,1]]

id = create_id(is_first, is_choise,choise_board,choise_hand,board,hand)
state = State(is_first, is_choise,choise_board,choise_hand,board,hand)
# # idのテスト　
# print("id = {}".format(id))
# print("is_first = {}".format(id2is_first(id)))
# print("is_choise = {}".format(id2is_choise(id)))
# print("choise_board = {}".format(id2choise_board(id)))
# print("choise_hand = {}".format(id2choise_hand(id)))
# print("board = {}".format(id2board(id)))
# print("hand = {}".format(id2hand(id)))

# stateのテスト　
print("state = {}".format(state))
print("is_first = {}".format(state.is_first))
print("is_choise = {}".format(state.is_choise))
print("choise_board = {}".format(state.choise_board))
print("choise_hand = {}".format(state.choise_hand))
print("board = {}".format(state.board))
print("hand = {}".format(state.hand))
print("legal_actions = {}".format(state.legal_actions))
print("next_statesの数 = {}".format(len(state.next_states())))

# 正規化テスト
# hand: List[bool] = [1,0,1,0,1,1,0,1,0,1,0,1]
# print("hand = {}".format(hand))
# print("nrm_hand = {}".format(create_normalization_hand(hand)))

# board = [
#          [1,0,1,0,1,0,1,0,1],[1,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
#          [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]];
# print("board = {}".format(board))
# print("nrm_board = {}".format(create_normalization_board(board)))
# 初期(setステート)
is_first: bool = False
is_choise: bool = False
choise_board: List[List[bool]] =[[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                                 [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
choise_hand: List[bool] = [0,0,0,0,0,0,0,0,0,0,0,0]
board: List[List[bool]] =[[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                          [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
hand: List[bool] = [1,1,1,1,1,1,1,1,1,1,1,1]
# 回答
# legal_actions: List[List]= [
#   [[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
#   [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]],
#   [1,1,1,1,1,1,0,0,0,0,0,0]]

id = create_id(is_first, is_choise,choise_board,choise_hand,board,hand)
state = State(is_first, is_choise,choise_board,choise_hand,board,hand)

# stateのテスト
print("id = {}".format(id))
print("type(id) = {}".format(type(id)))
print("state = {}".format(state))
print("state.is_first = {}".format(state.is_first))
print("state.is_choise = {}".format(state.is_choise))
print("state.choise_board = {}".format(state.choise_board))
print("state.choise_hand = {}".format(state.choise_hand))
print("state.board = {}".format(state.board))
print("state.hand = {}".format(state.hand))
print("state.legal_actions = {}".format(state.legal_actions))
print("state.next_states = {}".format(state.next_states()))
print("self.is_done = {}".format(state.is_done))
print("self.winner = {}".format(state.winner))<jupyter_output>id = 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000111111111111
type(id) = <class 'str'>
state = <__main__.State object at 0x7f99320395c0>
state.is_first = False
state.is_choise = False
state.choise_board = [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]]
state.choise_hand = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
state.board = [[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]]
state.hand = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
state.legal_actions = [[[0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0]], [1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0]]
create_ne[...]<jupyter_text>実装<jupyter_code>import networkx as nx
from google.colab import files

# csvの読み込むためのモジュール
import pandas as pd
from pandas import DataFrame
import numpy as np
from tabulate import tabulate # pandasのdfをきれいに出力するためのモジュール

# uploaded = files.upload()
# for fn in uploaded.keys():
#   print("hogehoge")
#   G = nx.readwrite.gml.read_gml(fn)
#   nx.draw_spring(G, node_size=200, node_color="red", with_labels=True)
### BFSでゲーム木を作成するプログラム ### 

### 設定ここから ###
printFlag = False

### 設定ここまで ###

###mainここから

# unsolvedDf, solvedDfの初期化
if printFlag:
  print("===")
  print("プログラム開始")
  print("===")
  print()
  print("データを初期化します")
cols = ["PREVIOUS_STATES", "STATE", "NEXT_STATES", "RESULT"] #[前の状態list， 状態, 次の状態list]
df = pd.DataFrame(index=[], columns=cols)
df.set_index("STATE")
unsolvedDf = df
solvedDf = df
if printFlag:
  print("データを初期化しました")
  print()

# 初期状態"※1"をunsolvedに追加する。unsolvedに積まれているノードは未訪問.
if printFlag:
  print("===")
  print("BFSの準備")
  print("===")
  print()
  print("初期状態をセットします")
# 初期(setステート)
is_first: bool = False
is_choise: bool = False
choise_board: List[List[bool]] =[[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                                 [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
choise_hand: List[bool] = [0,0,0,0,0,0,0,0,0,0,0,0]
board: List[List[bool]] =[[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],
                          [0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0]]
hand: List[bool] = [1,1,1,1,1,1,1,1,1,1,1,1]
state = State(is_first, is_choise,choise_board,choise_hand,board,hand)
init_state = state.normalized_id
previous_state = ""
unsolvedDf = unsolvedDf.append(pd.Series([[previous_state], init_state, "unsolved", ""], index=df.columns, name=init_state))
if printFlag:
  print("初期状態をセットしました") # 確認
  print("確認[UNSOLVED_DF]:") # 確認
  print(unsolvedDf) # 確認
  print() # 確認

# unsolvedが空になるまで以下を行う. BFS開始
if printFlag:
  print("===")
  print("BFSを開始します")
  print("===")
  print()
for _ in range(10): # while len(unsolvedDf) > 0: # 開発のためにfor文にしている。
  # unsolvedDfから先頭のノードをpopする。
  if len(unsolvedDf) <= 0:
    break;
  current_node = unsolvedDf.iloc[0]  # 先頭のノード(current_node)を抽出。
  unsolvedDf.drop(unsolvedDf.index[0], inplace=True)  # 抽出したノードをunsolvedから削除。
  # stateの作成
  id = current_node.STATE
  state = State(id2is_first(id), id2is_choise(id),id2choise_board(id),
                id2choise_hand(id),id2board(id),id2hand(id))
  # 勝敗の確認
  result = state.winner
  # 勝敗確定盤面なら
  if state.is_done:
    current_node.RESULT = state.winner
    current_node.NEXT_STATES = []
  else:  # 勝敗確定盤面でないなら
    # 先頭のノード(current_node)から次のノード(next_nodes)を探索する。
    next_states = state.next_states() # 次のノードの探索結果
    next_state_ids = []
    for next_state in next_states:
      next_state_ids.append(next_state.normalized_id)
    current_node.NEXT_STATES = next_state_ids # current_nodeのNEXT_STATESに探索結果を反映
    # 探索した全ての状態について、以下を行う。
    if printFlag:
      print("unsolvedDfからpopされたノード'{}'の探索を行います".format(current_node.STATE))
    if len(next_state_ids) <= 0:
      if printFlag:
        print("    探索結果: このノードは末端です")
    for next_state in next_state_ids:
      # もし、next_nodeが未発見ならば # unsolved, solvedのいずれにもnext_nodeが存在しない
      if (next_state not in unsolvedDf.STATE.values) and (next_state not in solvedDf.STATE.values):
        if next_state == current_node.STATE: # 次のノードが自身と同一
          if printFlag:
            print("探索結果: 自身のノード'{}'と同一です".format(next_state))
          continue;
        else:
          if printFlag:
            print("    探索結果: 未発見のノード'{}'です".format(next_state))
          # T)そのノードを未訪問にする。 # unsolvedに追加
          previous_state = [current_node.STATE]
          next_node = pd.Series([previous_state, next_state, "unsolved", ""], index=df.columns, name=next_state) # next_nodeの作成
          unsolvedDf = unsolvedDf.append(next_node)
      else:  # F)そうではなく、発見済みならば
        if printFlag:
          print("    探索結果: 発見済みのノード'{}'です".format(next_state))
        #これを既に登録されていたノードのprevious_stateに追加する。
        previous_state = [current_node.STATE] 
        if next_state in unsolvedDf.STATE.values: # unsolvedDfに存在
          if printFlag:
            print("        これはunsolvedに存在しています")
          # unsolvedDf[unsolvedDf.STATE.values == next_state])にprevious_stateを追加する
          tmp = unsolvedDf.loc[next_state, "PREVIOUS_STATES"]
          tmp.append(previous_state[0])       
          unsolvedDf.loc[next_state, "PREVIOUS_STATES"] = tmp
        elif next_state in solvedDf.STATE.values:# solveDfに存在
          if printFlag:
            print("        これはsolvedに存在しています")
          # solvedDf[solvedDf.STATE.values == next_state])にprevious_stateを追加する
          tmp = solvedDf.loc[next_state, "PREVIOUS_STATES"]
          tmp.append(previous_state[0])       
          solvedDf.loc[next_state, "PREVIOUS_STATES"] = tmp
        else: # 何らかの理由で漏れた状態
          print("        エラー")
  # 現在のノード（current_node）をsolvedDfに追加する。solvedDfのノードは既訪問。 
  solvedDf = solvedDf.append(current_node)

if printFlag:
  print()
  print("BFSが終了しました")
  print()

# 結果確認
print("===")
print("結果確認")
print("===")
print()
print("確認[unsolvedDf]:")
print()
print(tabulate(unsolvedDf, unsolvedDf.columns,tablefmt='github', showindex=True))
print()
print("確認[solvedDf]:")
print()
print(tabulate(solvedDf, solvedDf.columns,tablefmt='github', showindex=True))
print()


### mainここまで<jupyter_output>create_next_states : choiseなステートを作成する
create_next_states : choiseなステートを作成する
create_next_states : choiseなステートを作成する
create_next_states : choiseなステートを作成する
create_next_states : choiseなステートを作成する
create_next_states : choiseなステートを作成する
create_next_states : choiseなステートを作成する
create_next_states : choiseなステートを作成する
create_next_states : choiseなステートを作成する
create_next_states : choiseなステートを作成する
===
結果確認
===

確認[unsolvedDf]:

|                                                                                                                                        | PREVIOUS_STATES                                                                                                                                                                                                                                                                                                                                                                                                                                                   [...]<jupyter_text>出力<jupyter_code># ドライブのマウント
from google.colab import drive
drive.mount('/content/drive')
# 出力
# solvedDfをox_outputという名前で書き出し
solvedDf.to_csv('/content/drive/My Drive/ox/workspace/ox_output.csv')
# ox_outputの確認
solvedDf = pd.read_csv(
    "/content/drive/My Drive/ox/workspace/ox_output.csv",
    index_col=0, # 最初の１行はデータ名。
    encoding="cp932" # windowsの追加文字に対応。おまじないだと思えば良い。
    )
print(solvedDf)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.19804530956080804, 'fraction_numerical': 0.09507647010713993, 'mean_word_length': 3.7320046439628483, 'pattern_counts': {'":': 2, '<': 39, '<?xml version=': 0, '>': 40, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 32, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '9', 'dir': 'jupyter-structured-clean-dedup', 'id': '424990', 'license': 'MIT', 'n_tokens_mistral': 12794, 'n_tokens_neox': 12145, 'n_words': 1490, 'path': 'gobgob_ipynb_v0_3.ipynb', 'repo_name': 'kentokura/gob', 'size': '24454'}