注意事項
これはプログラミング初心者が四苦八苦して書いたコードです。もしあなたが私のようなニュービーであるならば、他の人の記事も参照しましょう。私は反転処理に関して次の記事を参考にしました。
オセロをビットボードで実装する
また、標準出力の文字色を変える為にこちらの記事にあるコードを使いました。
コンソールに色付きの出力をする方法
はじめに
まずは基本的な考え方から
turnはblackの手番なら0, whiteの手番なら1と定義し、black, whiteそれぞれ自分の石がどこに置いてあるかという情報を64ビットの整数で保持しています。二進数表記した時にビットが立っている（その桁が1となっている）場所に石が置かれているということです。
四隅のどこからどちら方向へビットを数えていくかというのは、シンメトリーなこのゲームにおいて特に意味を持たないので好きに解釈してください。
具体的に言えば、オセロの初期配置はそれぞれ
black = 0x0000001008000000
white = 0x0000000810000000
となっています。0xは16進数表記という意味なので、あえて長ったらしい2進数表記(0b)で書いてやると
black = 0b0000000000000000000000000001000000001000000000000000000000000000
white = 0b0000000000000000000000000000100000010000000000000000000000000000
このように64マス全ての位置について石があるかないかを1と0によって表すことができています。
内部状態なし
ではそろそろコードの方に移っていきましょう。
まずは内部状態を持たない普遍的な関数について定義するクラスを作ります。
class _rev_func:
"""
Class _rev_func.
useful funcion for class rev_core
"""
def swap(self, turn, black, white):
"""Swap (black, white) to (player, opponent)."""
if not turn:
return black, white
else:
return white, black
def swap_turn(self, turn):
"""Swap turn."""
return 1 ^ turn
swapくん必要なのん？と思うかもしれませんが、私には必要でした。
blackの手番でできる行動を全て定義してしまえば、blackとwhiteの盤面の順番とターンを入れ替えるだけでwhiteについても同じ操作が行えます。
swap_turnについては0と１であることを利用してXORで0 -> 1 -> 0 -> 1とturnを切り替えることができます。
(いやそれTrue, Falseでやった方がいいんじゃねとか思ったけど過去の遺物だから許して...)
着手可能位置判定
続いては、次に置くことができる場所を列挙するlegalくんを導入します。legalは置くことができる全ての場所のビットを立てた整数です。
どうしてこんなコードでそんなものが作れるんだと思う方はbitboardでググるとわかりやすい説明がたくさん出てきますので参考にしてください。
def _legal_l(self, player, masked, blank, dir):
"""Direction << dir exploring."""
tmp = masked & (player << dir)
tmp |= masked & (tmp << dir)
tmp |= masked & (tmp << dir)
tmp |= masked & (tmp << dir)
tmp |= masked & (tmp << dir)
tmp |= masked & (tmp << dir)
legal = blank & (tmp << dir)
return legal
def _legal_r(self, player, masked, blank, dir):
"""Direction >> dir exploring."""
tmp = masked & (player >> dir)
tmp |= masked & (tmp >> dir)
tmp |= masked & (tmp >> dir)
tmp |= masked & (tmp >> dir)
tmp |= masked & (tmp >> dir)
tmp |= masked & (tmp >> dir)
legal = blank & (tmp >> dir)
return legal
def legal(self, turn, black, white):
"""Generate legal board."""
player, opponent = self.swap(turn, black, white)
blank = ~(black | white)
h = opponent & 0x7e7e7e7e7e7e7e7e
v = opponent & 0x00ffffffffffff00
a = opponent & 0x007e7e7e7e7e7e00
legal = self._legal_l(player, h, blank, 1)
legal |= self._legal_l(player, v, blank, 8)
legal |= self._legal_l(player, a, blank, 7)
legal |= self._legal_l(player, a, blank, 9)
legal |= self._legal_r(player, h, blank, 1)
legal |= self._legal_r(player, v, blank, 8)
legal |= self._legal_r(player, a, blank, 7)
legal |= self._legal_r(player, a, blank, 9)
return legal
一応私の方でも解説してみます。
見ての通り_legal_lと_legal_rは本質的に同じものなので_legal_lについて書きます。
このlというのはシフト(<<これ)が左方向であることを表していて、dirで指定された数だけシフトさせて判定していきます。
シフトの例
0b0011 << 3 # -> 0b0011000
0b0011 >> 1 # -> 0b001
legalを見れば引数が1, 8, 7, 9となっているのがわかると思います。
これは右下0, 左方向に1, 2と進んで最終的に左上が63となるオセロ盤面で見てみると、それぞれ左、右上、上、左上方向に対応しているわけです。
自分の石の隣に数個連続して存在する相手の石の位置のビットを全て立て、最後にそれが空きスペースと隣り合っているかを評価しています。
1つの方向に,最大８個しか石の入るスペースは存在せず、自分が置く場所を除けば７個なので、7回のシフトで全て評価が可能となっています。`
さて、聡い読者の方々はお気づきかもしれませんが、石の情報は64bitの整数で表されており、このデータ構造においては、右端の石と下の行の左端の石は隣り合っているのです。何の処理もせずに_legal_lを実行したら宇宙オセロになってしまいます（しかも一段ずれてる）。そのため、相手の石の情報にマスクを被せます。
**盤面の端に相手の石があったとしても、そんなものはなかったことにしてしまおう。そうすれば宇宙空間に突入する前に相手の石の連続を切断できるだろう！というわけです。**
そのためのマスクがこいつら
h = opponent & 0x7e7e7e7e7e7e7e7e
v = opponent & 0x00ffffffffffff00
a = opponent & 0x007e7e7e7e7e7e00
実際の盤面に落としてみてみるとわかると思いますが、相手の石のつながりをぶった切りたい端っこのビットだけ0になっています。
こうして加工した盤面情報を_legal_lに渡してあげて、特定方向についての着手可能位置を返してもらい、全ての方向について足し合わせるのがlegalの役目です。
反転位置判定
続いてはreversedくん。(変数の名前のつけ方がなってなくて申し訳ありません)
これもlegalと同様、左右対称な二つの関数を用いています。これは実際に着手される場所を引数にし、裏返る石の場所の情報を返す関数です。もう説明は不要かとは思いますが、裏返る位置のビットが全て立っています。
def _reversed_l(self, player, blank_masked, site, dir):
"""Direction << for self.reversed()."""
rev = 0
tmp = ~(player | blank_masked) & (site << dir)
if tmp:
for i in range(6):
tmp <<= dir
if tmp & blank_masked:
break
elif tmp & player:
rev |= tmp >> dir
break
else:
tmp |= tmp >> dir
return rev
def _reversed_r(self, player, blank_masked, site, dir):
"""Direction >> for self.reversed()."""
rev = 0
tmp = ~(player | blank_masked) & (site >> dir)
if tmp:
for i in range(6):
tmp >>= dir
if tmp & blank_masked:
break
elif tmp & player:
rev |= tmp << dir
break
else:
tmp |= tmp << dir
return rev
def reversed(self, turn, black, white, site):
"""Return reversed site board."""
player, opponent = self.swap(turn, black, white)
blank_h = ~(player | opponent & 0x7e7e7e7e7e7e7e7e)
blank_v = ~(player | opponent & 0x00ffffffffffff00)
blank_a = ~(player | opponent & 0x007e7e7e7e7e7e00)
rev = self._reversed_l(player, blank_h, site, 1)
rev |= self._reversed_l(player, blank_v, site, 8)
rev |= self._reversed_l(player, blank_a, site, 7)
rev |= self._reversed_l(player, blank_a, site, 9)
rev |= self._reversed_r(player, blank_h, site, 1)
rev |= self._reversed_r(player, blank_v, site, 8)
rev |= self._reversed_r(player, blank_a, site, 7)
rev |= self._reversed_r(player, blank_a, site, 9)
return rev
legalとの違いは、 _reversed_lが引数に相手の盤面ではなく石の置かれていない場所をとっていることでしょうか。何でそういう可読性下げる行為をするの？と聞かれたらすみませんとしか答えられませんが、これには浅くはない理由があったのです。(最初マスクなしblankをifで使っていたせいで、終盤で宇宙空間に突入してしまい、気付いた後で絶望とともに修正しました。opponentにばかり気を使っていたせいでちょっと嵌ってしまいました）
気を取り直して本題に戻ります。
このマスクによって、端っこに相手の石があったとしても、そこには何も置かれていないことになっています
あとは置かれる場所から指定方向に一段階ずつ進んで判定していくだけです。
反転
さて、今まで判定ばかりで気が滅入っていたと思いますが、ここからは楽しい時間です。
先ほどまでの判定の部分が最も難解でバグが出やすい部分ですから、もうこの記事は終わりでもいいくらいです。
判定によって得られた情報を用いて実際に盤面を更新するのがreverseです。
def reverse(self, turn, black, white, site, rev):
"""Reverse board."""
if not turn:
return black ^ (rev ^ site), white ^ rev
else:
return black ^ rev, white ^ (rev ^ site)
def count_stone(self, black, white):
"""Count stone."""
nb = 0
nw = 0
while black:
black &= black - 1
nb += 1
while white:
white &= white - 1
nw += 1
return nb, nw
turnが0ならblackの手番。blackには置く場所とひっくり返る場所を足し合わせたものとXORし、whiteはひっくり返る場所とXORします。turnが1なら逆になります。
XORなので、0のところに置けば1、１のところに置けば0になります。
これ結構すごくて、一回置いたあと、もう一度同じ操作をすれば、元の盤面に戻るのです！
待ったを簡単に実装できますね
あとは盤面の石の数を数えるcount_stone。
これは実際に見てみるとわかりやすいでしょう。
a # -> 0b110111000
a - 1 # -> 0b110110111
a&(a-1) # -> 0b110110000
このように、一番右側に立っているビットがどんどん0になっていきます。
よって、この操作が何回行われたかを数えれば、石の数が判明します。
内部状態保持
次は_rev_funcクラスで定義した関数を用いて、ゲームの進行情報をクラス変数として保持するクラスを作っていきます。
初期化
まずは初期配置を定義します。
initは、クラスがインスタンス化される時に最初に呼ばれる関数です。厳密にはnewが最初なのですが、今はメタクラスなどは使わないのでここでは扱いません。
class rev_core(_rev_func):
"""
Class rev_core.
bitboard is used
"""
def __init__(self, turn, black, white):
"""Generate initial board."""
self.turn = turn
self.black = black
self.white = white
self.blank = ~(self.black | self.white)
self.put = []
self.rev = []
_rev_funcクラスを継承しているため、それらの関数を容易に呼び出すことができます。
また石の置かれる場所、裏返る場所を順次リストに格納していくことによって、先述の通り、容易に"待った"が実装できます。
調整
def next_board(self):
"""Reverse self.black and self.white."""
self.black, self.white = self.reverse(
self.turn, self.black, self.white, self.put[-1], self.rev[-1])
def next_turn(self):
"""Swap self.turn."""
self.turn ^= 1
def add_site(self, site):
"""Append self.put and self.rev."""
self.put.append(site)
self.rev.append(
self.reversed(self.turn, self.black, self.white, site))
def insert_judge(self):
"""Inseert legal board to self.judge."""
self.judge = self.legal(self.turn, self.black, self.white)
def undo(self):
"""Undo self.black and self.white."""
self.next_turn()
self.next_board()
self.insert_judge()
self.put, self.rev = self.put[:-1], self.rev[:-1]
def count_board(self):
"""Count stone on self.black and self.white."""
return self.count_stone(self.black, self.white)
あとのものは_rev_funcの関数を内部状態に合わせて定義し直したものです。
注意する点は、legalによって生成された着手可能位置は、judgeという名前で保持されていることです。（わかりづらい実装してすみません。というかinsert_judgeはadd_judgeとかにして名前合わせた方が可読性が...）
undoしたあとは、putとrevの枝の先の情報をスライスによって削除しています。
CUI用
今までのコードによって、オセロの骨格は出来上がりました。
とはいえパス判定や終了判定についてはまだ書いていません。rev_coreに組み込むべきだったのかもしれませんが、こっちに書いて収まりがよかったのでぶっちゃけ言うと手抜き工事です。
実際にプレイするために必要な関数はここで定義していきます。
コード量思ったより多くてファイル分けたくなってしまい、変な感じになってます。
初期化とimport
#!/usr/bin/python
"""UI for Reversi."""
import random
from pyrev.pycolor import pycolor
from pyrev.core import rev_core
class rev_ui(rev_core):
"""Class rev_ui.
Provide User Interface to play the game
"""
def __init__(self):
"""Define the first state."""
super().__init__(0, 0x0000001008000000, 0x0000000810000000)
super()は親クラスを指します。ここではrev_coreを継承しているので、rev_coreのinitが呼ばれています。これは盤面を初期配置にしています。
そしてpycolorはこんな感じ
"""Change color of texts."""
class pycolor:
"""Change the color."""
BLACK = '\033[30m'
RED = '\033[31m'
GREEN = '\033[32m'
YELLOW = '\033[33m'
BLUE = '\033[34m'
PURPLE = '\033[35m'
CYAN = '\033[36m'
WHITE = '\033[37m'
END = '\033[0m'
BOLD = '\033[1m'
UNDERLINE = '\033[4m'
INVISIBLE = '\033[08m'
REVERCE = '\033[07m'
盤面表示
プレイするためには当然、盤面を表示する必要があります。
pycolorは下のコードの通り、文字色を変えたい部分を囲ってあげます。
盤面は縦横0~9の１００マスを表示して、0と9の位置に縦軸横軸の数字を入れてあげます。
これによりプレイヤーが石を置きたい場所を一意に指定することができます。
def show_board(self):
"""Show the board for command line."""
print("—" * 38)
for i in range(10):
for j in range(10):
mask = 2**(63-(j-1)-8*(i-1))
if i == 0 or i == 9:
if j == 0 or j == 9:
print(" ", end=" | ")
else:
print(pycolor.RED + str(j) + pycolor.END, end=" | ")
elif j == 0 or j == 9:
print(pycolor.RED + str(i) + pycolor.END, end=" | ")
elif mask & self.black:
print("🔵", end=" | ")
elif mask & self.white:
print("⚪️", end=" | ")
elif mask & self.judge:
print("x", end=" | ")
else:
print(" ", end=" | ")
print("\n" + "-" * 38)
print(hex(self.black), hex(self.white))
def show_stone(self):
"""Show the number of stones."""
nb, nw = self.count_board()
print("Black:{} vs White:{}".format(nb, nw))
def show_result(self):
"""Show the result."""
nb, nw = self.count_board()
if nb == nw:
print("Game over\tDraw")
else:
winner = "Black" if nb > nw else "White"
print("Game Over\t{} Won".format(winner))
~~当時の私がなぜmaskなんて名前にしたのかさっぱりわかりませんが、~~black, white, judge(着手可能位置)をそれぞれ表示しています。また、盤面をいつでも再現できるように16進数で情報を表示しています。(initに入れれば再現化)
あとは石の数とゲーム終了後の結果を表示する関数を定義しています。
入力処理
次に、プレイヤーからの入力を盤面に落とし込む関数を定義していきます。
def input_player(self):
"""Player input site."""
while True:
raw_site = input('ij:(row, col) = (i, j), 0:undo >>> ')
try:
_site = int(raw_site)
except Exception as e:
print(e)
continue
row, col = (_site // 10), (_site % 10)
if 0 < row < 9 and 0 < col < 9:
site = 2**(63-(col-1)-8*(row-1))
if self.judge & site:
self.add_site(site)
break
elif not _site:
if self.put:
self.undo()
self.show_board()
else:
print("It has already been initialized")
else:
print("You cannot put there")
def input_random(self):
"""Random input site."""
while True:
site = 1 << random.randrange(0, 64)
if self.judge & site:
self.add_site(site)
break
def input(self, black, white):
"""Define input way of each side."""
if not self.turn:
black()
else:
white()
プレイヤーからの入力はi行j列をijとした文字列であることを要求します。
数字でない場合はint関数でブロックされ次のループに向かい、数字の場合もijの値によって場合分けされ、適切な値のみがadd_siteによってputとrevにセットされます。
また、i=0であればjは0から9の任意の値をとってもifの最初の分岐に入らないため、一桁の数字の入力をオプションとして定義でき、色々拡張できます。
ここでは0を入力すれば盤面の状態を一つ前に戻すことができるようになっています。
さて、次のinput_randomですが、これは完全な手抜きです。と言うのも、本当はめっちゃ強いプログラム作ってやろうと意気込んで開発を始めたのですが、これを書いている頃には熱意がほとんど消え失せてしまっていたのです。前述のblankバグと格闘し、一人二役オセロをやっているうちに虚しくなり、もういいやランダムで動かしちゃえと言って1分足らずで書いたものです
また、input関数の挙動は後述します。(名前が紛らわしい)
これ着手可能位置生成するまで終わらないけど大丈夫？と思われるかもしれませんが大丈夫です。ビット演算により処理が高速化されているので、こんなゴミAIを作るのにいちいち思考リソースを割くべきではありません。
終了判定
jud_endは終了判定をしますが、同時にパスの時の挙動も定義されています。
black, white両者でパスを判定して両方パスなら終了、片方パスならパスして継続といったゲーム進行なので、１回目の判定時にターンを入れ替え、着手可能位置も再取得しています。
このような可読性の下がる行為は推奨されません
def jud_end(self):
"""Judge whether end."""
self.insert_judge()
if not self.judge:
self.next_turn()
self.insert_judge()
if not self.judge:
return True
else:
self.caution_pass()
return False
else:
return False
def caution_pass(self):
"""Caution to pass."""
print("turn passed")
caution_passはパスの時に呼びます。
ゲーム進行
先ほどのちょっと不思議な挙動をするjud_endでゲームの流れを記述するとこうなります。
if分岐に入るか入らないかに関わらず、jud_endは実行されます。この分岐に入るのはゲーム終了時のみで、それ以外の時は手番を調整する役目を果たしてくれる便利な子です。
def game_flow(self):
"""Game flow of reversi."""
while True:
if self.jud_end():
# turn has already been changed by self.jud_end()
# legal board has already been generated
self.show_board()
self.show_stone()
self.show_result()
break
self.show_board()
self.show_stone()
self.input(self.input_player, self.input_random)
self.next_board()
self.next_turn()
そしてこのinput。
これはblack, whiteがそれぞれ使う入力関数を入れてあげることで、手番によって適切に振る舞いを変えます。
ここではblackがプレイヤーによる入力、whiteがコンピューターによるランダム入力となります。
pythonでは関数もオブジェクトですから、こんな変態コーディングもできると言うわけです。
def input(self, black, white):
"""Define input way of each side."""
if not self.turn:
black()
else:
white()
完成！
あとはmainにこれを書いてあげれば完成です！
コマンドラインで実行してみましょう。
if __name__ == '__main__':
game = rev_ui()
game.game_flow()
終わりに
もしかしたら、この記事の読者様は「結局相手ランダムとかクッソつまらんな」と思っているんじゃないでしょうか。私もそう思います。
しかし_rev_funcとrev_coreで強いAIを作ってinputの部分に入れるだけでいいわけですから、まあ拡張性はあるんじゃないかなと。AlphaZero強すぎて萎えてしまったので、ちょっと実装する気力ないです。
興味のある方はこの続きを書いて見てはいかがでしょうか。
コードはGitHubに置いてあります。
CUI for Reversi described in Python