Python｜UnionFind（DSU）クラスの実装と利用方法
Aru
Aru's テクログ（Aruaru0）
コンピュータと対戦できる！３目並べ（tic-toc-toe）をPythonで実装してみよう
Aru
３目並べ（俗にいう○×ゲーム）はシンプルながらもロジックを学ぶのに最適な題材だと思います。この記事では、プログラミングの教材として３目並べと取り上げ、Pythonでの実装を試みました。具体的には、まず盤面や勝ち負けの判定を作り、その後コンピュータの思考処理を実装していきます。順を追って実装していくことで、プログラミング初心者から中級者まで幅広く対応できる教材になるかと思います。
この記事では、Pythonを使って３目並べ（tic-toc-toe）を作成する手順をStep-by-Stepで解説します。最終的には、コンピュータと対戦するための思考ルーチンも作成したいと思います。ぜひ挑戦してみてください。
Contents
３目並べとは
英語ではtic-tac-toeと呼ばれるゲームです。日本では○×ゲームといった方がわかりやすいかもしれません。
ルールは、2人のプレイヤーが3×3のマス目に交互にマーク（○または×）をつけていくというシンプルなものです。最初のプレイヤーは○か×を選び、次のプレイヤーは残ったマークを使います。プレイヤーは自分の番が来たら、グリッドの空いているマスに自分のマークをつけていきます。
勝利条件は簡単です。先に縦、横、または斜めのいずれかに自分のマークを3つ並べたプレイヤーが勝ちとなります。もし、全てのマスが埋まってもどちらも3つ並べることができなかった場合、そのゲームは引き分けとなります。
このゲームの魅力は、そのシンプルさにあります。子供でもすぐに理解できるルールでありながら、戦略を考える余地が十分にあるためコンピュータの思考ルーチンを考えるプログラミグ教材としても利用できます。
この記事では、プログラミング言語としてPythonを使って３目並べを作っていきたいと思います。
Go言語で３目並べを作る記事は以下になります。別言語の実装を学びたい方は参考にしてください
コンピュータと対戦できる！３目並べ（tic-toc-toe）をGo言語で実装してみよう
ステップ１：ボードの表示
ステップ１で行うのは、ボードを画面に表示することです。
ボード内容は、[[0,0,0],[1,0,0],[-1,0,0]]のような形で３×３のリストに保存されている前提となります。それぞれの数値の意味は以下の表のようになります。
| 値 | 値の意味 |
| 0 | 空白 |
| 1 | ×が書かれている |
| -1 | ○が書かれている |
print_boardは、３×３のリスト内容を上記のルールに従って盤面として表示させるものになります。
print_board()は、引数として３×３のリストboardを受け取ります。この情報を基に盤面を表示させます。プログラムは、例えば、以下のようになります。
# ボードを表示する
def print_board(board):
print("-"*20)
print(" a b c")
for i, row in enumerate(board):
print(i+1, end=" ")
for col in row:
if col == 0:
print('.', end=' ')
if col == 1:
print('X', end=' ')
if col == -1:
print('O', end=' ')
print()
board = [[0,0,0] for _ in range(3)]
print_board(board)プログラム中のprint("-"*20)は、-を20個表示し、ステップ毎の区切りを見やすくするための境界線を表示するものです。
盤面の描画はfor i...以下の部分となります。3×3の盤面を作成するので、ここは２重ループとなります。
このプログラムを実行すると以下のような３目並べのマス目を表示します。
上部のa,b,cと左部の1,2,3は、場所を指定するための記号です。
次に作成するキー入力処理では、例えば1aといった感じでどこに○または×を書くか指定します。
--------------------
a b c
1 . . .
2 . . .
3 . . . ステップ２：キー入力処理の作成
ボートの状態を表示する処理が作成できたので、次はキー入力を受け付ける部分を作成します。
キーボード入力を受け取る
今回は、マス目を1a, 2a, 2b,...といった形式で指定することにします。
キー入力はpythonでは、input()という関数を使って取ることができます。
以下は、input()でキーボードの入力を受け取ってマスの(x,y)を返すget_input関数のプログラムリストです。
def get_input() :
s = input()
print(s)
if '0' <= s[0] and s[0] <= '9' :
y = int(s[0])-1
x = ord(s[1]) - ord('a')
else :
y = int(s[1])-1
x = ord(s[0]) - ord('a')
return x, yなお、今回のプログラムでは、1aと入力してもa1と入力してもOKなようにしています。
具体的な処理の流れは以下のようになります。
- 一文字目が
0〜9の範囲（数字）であった場合には、一文字目を行、二文字目を列番号として変換する - そうでない場合は、一文字目を列、二文字目を行として変換する
数値の場合はint(s[0])といった記述で、文字から整数型に変換できます。a,b,cといった文字の場合はord()を使って整数に変換します。ordは文字のコードを数値に変換する処理になります。文字コードはa,b,c…とアルファベット順に1ずつ大きくなるように並んでいるので、この性質を利用して0,1,2という列番号に変換します。
具体的には、ord('a')-ord('a')=0, ord('b')-ord('a')=1になるので、ord('a')を引くことでa,b,cは0,1,2に変換することができます。
以下のコードは、get_input()を呼び出してキー入力を受け付け、指定された場所に○または×を書き込んで、更新されたボードを再表示するものです。マス目は３ｘ３＝９マスなので、ループは９回で終了となります。
for i in range(9) :
print_board(board)
print("Enter position(ex. 1a):", end="")
x, y = get_input()
if i%2 == 0 :
board[y][x] = -1
else :
board[y][x] = 1なお、i%2は、iを2で割ったあまりを計算するもので、0,1,0,1,0,..と01を繰り返します。これを使って先手と後手を判定し、-1または１をキー入力で指定されたマスに代入しています。
ここまでのコード
以下が、ここまでのコードです（このコードは実行できます）。
# 入力を受け付ける
def print_board(board):
print("-"*20)
print(" a b c")
for i, row in enumerate(board):
print(i+1, end=" ")
for col in row:
if col == 0:
print('.', end=' ')
if col == 1:
print('X', end=' ')
if col == -1:
print('O', end=' ')
print()
def get_input() :
s = input()
print(s)
if '0' <= s[0] and s[0] <= '9' :
y = int(s[0])-1
x = ord(s[1]) - ord('a')
else :
y = int(s[1])-1
x = ord(s[0]) - ord('a')
return x, y
board = [[0,0,0] for _ in range(3)]
for i in range(9) :
print_board(board)
print("Enter position(ex. 1a):", end="")
x, y = get_input()
if i%2 == 0 :
board[y][x] = -1
else :
board[y][x] = 1
実行すると、例えば以下のようになります（赤文字は入力です）
--------------------
a b c
1 . . .
2 . . .
3 . . .
Enter position(ex. 1a):2b
2b
--------------------
a b c
1 . . .
2 . O .
3 . . .
Enter position(ex. 1a):1a
1a
--------------------
a b c
1 X . .
2 . O .
3 . . .
Enter position(ex. 1a):2c
2c
--------------------
a b c
1 X . .
2 . O O
3 . . .
Enter position(ex. 1a):置けない場所の判定
これまでのコードで、盤面を表示し、キー入力を受け付けて盤面を更新する機能が実装できました。気づいた方も多いかとおもますが、実はこのコードには問題点があります。
問題点は、既に○や×が書かれてもマス目として指定できることです。つまり、既に○や×が書かれているマスに上書きできてしまいます。
これを防ぐには、マス目が空白かどうかをチェックする必要があります。
具体的には、入力されたマス目が０かどうかをチェックして、０でない場合は入力を繰り返すコードを追加します。
while(1) :
x, y = get_input()
if board[y][x] != 0 :
print("already occupied. try again.")
else:
breakここまでのコード
以下が、ここまでのコードです（このコードは実行できます）。
# 置けない場合は入力を繰り返す
def print_board(board):
print("-"*20)
print(" a b c")
for i, row in enumerate(board):
print(i+1, end=" ")
for col in row:
if col == 0:
print('.', end=' ')
if col == 1:
print('X', end=' ')
if col == -1:
print('O', end=' ')
print()
def get_input() :
s = input()
print(s)
if '0' <= s[0] and s[0] <= '9' :
y = int(s[0])-1
x = ord(s[1]) - ord('a')
else :
y = int(s[1])-1
x = ord(s[0]) - ord('a')
return x, y
board = [[0,0,0] for _ in range(3)]
for i in range(9) :
print_board(board)
print("Enter position(ex. 1a):", end="")
while(1) :
x, y = get_input()
if board[y][x] != 0 :
print("already occupied. try again.")
else:
break
if i%2 == 0 :
board[y][x] = -1
else :
board[y][x] = 1このコードでは、既に書き込んだマスに○や×が書き込めないので、ルールに沿った３目並べを遊ぶことができます。
一応、ここまでのプログラムで人対人の対戦が行えます。
ステップ３：勝敗判定を作成
ここまで説明したプログラムで、対戦は可能ですが勝敗の判定は人が見て確認する必要がありました。
せっかく、コンピュータ上で動かすので、勝ち負けの判定もコンピュータにやらせたいと思います。ということで、ここでは勝敗を判定する関数を作成したいと思います。
３×３マスしかないので、判定も簡単です。判定アルゴリズムは以下のようになります。
- 縦、横に３つ揃っている判定
- 斜め（(0,0)〜(2,2)）に３つ揃っているか判定
- 斜め（(0,2)〜(2,0)）に３つ揃っているか判定
- ①〜③に該当しない場合は揃っていない
例えば、横に並んでいるかどうかは以下の条件で判定できます。
board[i][0] == board[i][1] == board[i][2]
これを、全ての方向に行います。
３×３と狭いので、全パターン書いてもそれほどキツくないです
戻り値ですが、一致していた場合には、boardの値を返せばそれが勝者になります。
ただ、0（空白）が３つ並んでいる場合もあるので、board[i][0] != 0といった判定で、空白が３つ並んでいる場合を除外しています。
以下が、勝敗をチェックするcheck_win関数になります。
def check_win(board) :
for i in range(3) :
if board[i][0] != 0 and board[i][0] == board[i][1] == board[i][2] :
return board[i][0]
if board[0][i] != 0 and board[0][i] == board[1][i] == board[2][i] :
return board[0][i]
if board[0][0] != 0 and board[0][0] == board[1][1] == board[2][2] :
return board[0][0]
if board[0][2] != 0 and board[0][2] == board[1][1] == board[2][0] :
return board[0][2]
return 0ここまでのコード
以下が、ここまでのコードです（このコードは実行できます）。このコードで、人対人の対戦と、終了判定が完了です。
def print_board(board):
print("-"*20)
print(" a b c")
for i, row in enumerate(board):
print(i+1, end=" ")
for col in row:
if col == 0:
print('.', end=' ')
if col == 1:
print('X', end=' ')
if col == -1:
print('O', end=' ')
print()
def get_input() :
s = input()
if '0' <= s[0] and s[0] <= '9' :
y = int(s[0])-1
x = ord(s[1]) - ord('a')
else :
y = int(s[1])-1
x = ord(s[0]) - ord('a')
return x, y
def check_win(board) :
for i in range(3) :
if board[i][0] != 0 and board[i][0] == board[i][1] == board[i][2] :
return board[i][0]
if board[0][i] != 0 and board[0][i] == board[1][i] == board[2][i] :
return board[0][i]
if board[0][0] != 0 and board[0][0] == board[1][1] == board[2][2] :
return board[0][0]
if board[0][2] != 0 and board[0][2] == board[1][1] == board[2][0] :
return board[0][2]
return 0
board = [[0,0,0] for _ in range(3)]
for i in range(9) :
print_board(board)
stat = check_win(board)
if stat == -1 :
print("-"*20)
print("Winner is player1")
print("-"*20)
exit(0)
if stat == 1 :
print("-"*20)
print("Winner is player2")
print("-"*20)
exit(0)
print("Enter position(ex. 1a):", end="")
while(1) :
x, y = get_input()
if board[y][x] != 0 :
print("already occupied. try again.")
else:
break
if i%2 == 0 :
board[y][x] = -1
else :
board[y][x] = 1
print_board(board)
print("-"*20)
print("Draw")
print("-"*20)ステップ４：コンピュータ対戦の実現
ここから、難しくなります。初心者の方はここまで理解できれば十分かと思います。ここからは中級者向けだと思って読んでください。
ここで行うのは、コンピュータの思考ルーチンの作成です。
コンピュータの思考ルーチンの考え方
ソースコードの変更
先ほどの人対人のコードを書き換えて、コンピュータ対戦のコードの雛形を作成します。
ハイライトしている部分が変更部分になります。
import random
def print_board(board):
print("-"*20)
print(" a b c")
for i, row in enumerate(board):
print(i+1, end=" ")
for col in row:
if col == 0:
print('.', end=' ')
if col == 1:
print('X', end=' ')
if col == -1:
print('O', end=' ')
print()
def get_input() :
s = input()
if '0' <= s[0] and s[0] <= '9' :
y = int(s[0])-1
x = ord(s[1]) - ord('a')
else :
y = int(s[1])-1
x = ord(s[0]) - ord('a')
return x, y
def check_win(board) :
for i in range(3) :
if board[i][0] != 0 and board[i][0] == board[i][1] == board[i][2] :
return board[i][0]
if board[0][i] != 0 and board[0][i] == board[1][i] == board[2][i] :
return board[0][i]
if board[0][0] != 0 and board[0][0] == board[1][1] == board[2][2] :
return board[0][0]
if board[0][2] != 0 and board[0][2] == board[1][1] == board[2][0] :
return board[0][2]
return 0
board = [[0,0,0] for _ in range(3)]
for i in range(9) :
print_board(board)
stat = check_win(board)
if stat == -1 :
print("-"*20)
print("Winner is player1")
print("-"*20)
exit(0)
if stat == 1 :
print("-"*20)
print("Winner is player2")
print("-"*20)
exit(0)
if i%2 == 0:
print("Enter position(ex. 1a):", end="")
while(1) :
x, y = get_input()
if board[y][x] != 0 :
print("already occupied. try again.")
else:
break
else:
# ここにコンピュータの処理を追加する
# x, y, _ = think(board, 1)
if i%2 == 0 :
board[y][x] = -1
else :
board[y][x] = 1
print_board(board)
print("-"*20)
print("Draw")
print("-"*20)人が先行（Player1）で、Player2の時はコンピュータの思考処理を呼び出します。思考処理では、置く場所(x,y)を返します。
以下、３つの戦略を紹介します。ここで紹介する３つの戦略までは、理解するのは難しくないかと思います。
戦略１：置ける場所を見つけたらそこに置く
一番簡単な戦略は、「とにかく置ける場所を見つけて、そこに置く」というものです。
この処理では、上から順番に調べていき、空白があればそこを返します。
なお、置けない場合に呼び出されることはないので、見つからない場合はダミー(0,0)を返しています。
# 最初に見つけた場所に置く
def think_seq(board) :
pos = []
for i in range(3):
for j in range(3) :
if board[i][j] == 0 : return (j, i)
return (0,0)これで、一応コンピュータが自動で場所を選んでくれます。
戦略２：ランダムに配置する
次に思いつく戦略は、「置ける場所から置く場所をランダムに選ぶ」という戦略かと思います。プログラムを、ランダムに選ぶように変更してみます。
この処理では、置ける場所を全てリストに記憶しておき、その中から１つランダムに選んで返します。
# ランダムに置く場所を決める
def think_random(board) :
pos = []
for i in range(3):
for j in range(3) :
if board[i][j] == 0 : pos.append((j, i))
sel = random.randint(0, len(pos)-1)
return pos[sel]戦略３：負けないようにする
上記の２つの戦略では、相手の手に関係なく適当に置く場所を選んでいました。ここでは、「相手の３マス並びの邪魔をする」ようにプログラムしたいと思います。
具体的には、次のターンで相手が勝つ配置がある場合は、そこを潰す様にします。
処理としては、一旦相手のターンで置いた場合の盤面を作成し、check_winで相手が勝つかどうか判定します。
次の手で相手が勝つ場所がある場合はそこを優先します。
なお、一旦相手のコマを置いた状態を作っているので、board[i][j] = 0で仮で置いた場所を元に戻しておきます。
なお、相手が勝つパターンがない場合は、ランダムに置ける場所におきます。
# 負けない様ににする
def think_stop2(board, turn) :
pos = []
for i in range(3):
for j in range(3) :
if board[i][j] != 0 : continue
board[i][j] = -turn
if check_win(board) == -turn :
board[i][j] = 0
return (j, i)
board[i][j] = 0
pos.append((j, i))
sel = random.randint(0, len(pos)-1)
return pos[sel]これで、相手が２マスならびを作った場合に負けを回避できるようになります。
このコンピュータの処理だけで、リーチ（２マスが繋がって次で３マスになる部分）を２箇所同時に作らないとコンピュータに勝つことができなくなります。
戦略？：その他改良案
思考ルーチンを作るのは結構楽しいです（個人的には）。色々考えてチャレンジするのも良いと思います。
例えば、積極的にリーチを作っていくように変更するなど、いろいろ検討することができると思います。
本格的な思考ルーチン（深さ優先探索）：上級者向け？
最後に、本格的な思考ルーチンを作成してみます。ここは結構難しいので分からなくても大丈夫です。
実は、３目並べの場合、９マスとマス数が少ないので全てのパターンを読み切ることが可能です。
全ての手を読み切れば、負けは無くなります。自分が打った手→相手が打った手→…を探索する方法としては、深さ優先探索（DFS）などがあります。
深さ優先探索について理解したければこちら
Pythonで深さ優先探索（DFS）,幅優先探索（BFS）,ダイクストラ法を実装する
ここでは、深さ優先探索（DFS）で次の手を探索します。以下のプログラムは深さ優先探索で次の手を求めるthink関数の例です。
# 深さ優先探索で、最終的な勝者を返す
def think(board, turn) :
# 9マス全てが埋まっているかどうか確認
cnt = 0
for i in range(3):
for j in range(3):
if board[i][j] == 0 : cnt += 1
if cnt == 0 :
return -1, -1, 0 # 全て埋まっていればDRAW
x, y = 0,0
win = False
res = -turn
for i in range(3) :
for j in range(3) :
if board[i][j] != 0 : continue # 既に置かれている場合はスキップ
board[i][j] = turn
winner = check_win(board)
if winner == turn :
board[i][j] = 0
return j, i, turn # 置いて勝てば勝者はturnの人
# 次の手を考える
_, _, r = think(board, -turn)
board[i][j] = 0
if r == turn: # 自分が勝つ場合は、その手を覚える
win = True
x, y = j, i
res = turn
if win == False: # 自分の価値が決定してない場合
if r == 0 : # 引き分けの場合は、手を覚える
x, y = j, i
res = 0
if r == -turn and res == -turn: # 現在まだ引き分け以上の手が見つかっていなければ、場所を記録
x, y = j, i
return x, y, res処理としては、min-max法と呼ばれる手法を簡単化（スコアを計算せず、勝ち・負け・引き分けだけ）したものになります。
この関数の処理については詳しく説明しませんが、自分のターン、相手のターン…と再帰的に探索していきます。
「自分の勝ちは相手の負け」になるということを注意して実装すればそこまで難しくはありません。
このコードをコンピュータ側に設定すると、基本負けはなくなります（必ず引き分け以上になる）。
深さ優先探索については以下の記事を参考にしてください。
あわせて読みたい
Pythonで深さ優先探索（DFS）,幅優先探索（BFS）,ダイクストラ法を実装する
まとめ
３目並べを例題として、ステップを踏みながらプログラミングしていきました。プログラミングの学習としては、「人対人までは初心者でも作れる」ことと、「コンピュータの思考部分は中級者くらいまでがいろいろ工夫しながら作れる」という点で結構面白い題材だと思いますがどうでしょうか？
付録（コード全体）
以下、３目並べの全コードです。
import random
def print_board(board):
print("-"*20)
print(" a b c")
for i, row in enumerate(board):
print(i+1, end=" ")
for col in row:
if col == 0:
print('.', end=' ')
if col == 1:
print('X', end=' ')
if col == -1:
print('O', end=' ')
print()
def get_input() :
s = input()
if '0' <= s[0] and s[0] <= '9' :
y = int(s[0])-1
x = ord(s[1]) - ord('a')
else :
y = int(s[1])-1
x = ord(s[0]) - ord('a')
return x, y
def check_win(board) :
for i in range(3) :
if board[i][0] != 0 and board[i][0] == board[i][1] == board[i][2] :
return board[i][0]
if board[0][i] != 0 and board[0][i] == board[1][i] == board[2][i] :
return board[0][i]
if board[0][0] != 0 and board[0][0] == board[1][1] == board[2][2] :
return board[0][0]
if board[0][2] != 0 and board[0][2] == board[1][1] == board[2][0] :
return board[0][2]
return 0
# 最初に見つけた場所に置く
def think_seq(board) :
pos = []
for i in range(3):
for j in range(3) :
if board[i][j] == 0 : return (j, i)
return (0,0)
# ランダムに置く場所を決める
def think_random(board) :
pos = []
for i in range(3):
for j in range(3) :
if board[i][j] == 0 : pos.append((j, i))
sel = random.randint(0, len(pos)-1)
return pos[sel]
# 負けない様ににする
def think_stop2(board, turn) :
pos = []
for i in range(3):
for j in range(3) :
if board[i][j] != 0 : continue
board[i][j] = -turn
if check_win(board) == -turn :
board[i][j] = 0
return (j, i)
board[i][j] = 0
pos.append((j, i))
sel = random.randint(0, len(pos)-1)
return pos[sel]
# 深さ優先探索で、最終的な勝者を返す
def think(board, turn) :
# 9マス全てが埋まっているかどうか確認
cnt = 0
for i in range(3):
for j in range(3):
if board[i][j] == 0 : cnt += 1
if cnt == 0 :
return -1, -1, 0 # 全て埋まっていればDRAW
x, y = 0,0
win = False
res = -turn
for i in range(3) :
for j in range(3) :
if board[i][j] != 0 : continue # 既に置かれている場合はスキップ
board[i][j] = turn
winner = check_win(board)
if winner == turn :
board[i][j] = 0
return j, i, turn # 置いて勝てば勝者はturnの人
# 次の手を考える
_, _, r = think(board, -turn)
board[i][j] = 0
if r == turn: # 自分が勝つ場合は、その手を覚える
win = True
x, y = j, i
res = turn
if win == False: # 自分の価値が決定してない場合
if r == 0 : # 引き分けの場合は、手を覚える
x, y = j, i
res = 0
if r == -turn and res == -turn: # 現在まだ引き分け以上の手が見つかっていなければ、場所を記録
x, y = j, i
return x, y, res
board = [[0,0,0] for _ in range(3)]
for i in range(9) :
print_board(board)
stat = check_win(board)
if stat == -1 :
print("-"*20)
print("Winner is player1")
print("-"*20)
exit(0)
if stat == 1 :
print("-"*20)
print("Winner is player2")
print("-"*20)
exit(0)
if i%2 == 0:
print("Enter position(ex. 1a):", end="")
while(1) :
x, y = get_input()
if board[y][x] != 0 :
print("already occupied. try again.")
else:
break
else:
# x, y = think_seq(board)
# x, y = think_random(board)
# x, y = think_stop2(board, 1)
x, y, _ = think(board, 1)
if i%2 == 0 :
board[y][x] = -1
else :
board[y][x] = 1
print_board(board)
print("-"*20)
print("Draw")
print("-"*20)ABOUT ME
専門分野は並列処理・画像処理・機械学習・ディープラーニング。プログラミング言語はC, C++, Go, Pythonを中心として色々利用。現在は、Kaggle, 競プロなどをしながら悠々自適に活動中
