PSM

プログラミング 初心者の メモ書き です

Pythonでオセロをつくってみる

天啓により,Pythonでオセロを作ることを思い立ちました.
まずは簡単なボードの実装から始めて,候補手(合法手)を出してくれる機能を追加したり,UIをちゃんと(クリックで駒が置けるなど)していきたいと考えています.
将来的には,自分で学習させたComとの対戦なども……

ちなみにプログラミングもアルゴリズムもかなりの初心者のため,間違っているところやかなり危ないところ,多々あるかと思います.ご指摘いただけると幸いです.

早速ですが,以下コンテンツ.
逐次追加予定です.かなり長くなる予定です.

はじめに

動機

Pythonの勉強として競技プログラミングも始めたのですが,そろそろプロダクトを作ってみたくなったためオセロに挑戦することにしました.
あとは簡単な機械学習を試してみたいという欲望もあります.

縛り

Pythonそのものについてググってもよいとする.
・勉強にならないので,オセロの実装についてはあまりググらないこととする.


ボードの実装

オセロボードをどう表現するか

まず駒をどう表現するか考えました.
オセロに登場する駒は○と●の2つです.
また1つのマスに注目すると, 駒が何も置かれていない/○が置かれている/●が置かれているの3通りあることがわかります.盤面の出力の都合上,何も置かれていない状態をとりあえず〼で表すことにします.
これらをそれぞれ数字の1,2,3で表すことにしました.つまり,対応関係は{〼(何も置かれていない):0, ○:1, ●:2}となります.

次に,ボード全体をどう表現するか考えました.
オセロは8×8のボードゲームです.よって最初はそのまま8×8の2次元配列を用いようと思っていました.
が,ここで1つ疑問が発生.オセロなので,駒を置いたときに周りの駒をひっくり返せるか探索する必要があります.このときボードの端が絡んでくると,少し判定が面倒になることが予想されます.(具体的には,端より向こう側は0/1/2によって表現されていないので,探索の中に端を探索しているという条件を書かなくてはいけなくなる)
そこで,10×10の2次元配列を用い,外周1マス分はボードのエッジとして■で表現することにしました.この数字には9を用いることにします.
よって,現在の対応関係は{0:"〼", 1:"○", 2:"●", 9:"■"}となります.
オセロボードのイメージはこんな感じ
f:id:muromura:20170724233300p:plain

あとは,これらをどう実装するかです.
これからどう進むか全くわかりませんが,とりあえず練習ついでに,クラスとしてオセロボードを実装することにしました.
新規ゲームのたびに,オセロボードクラスからインスタンスをつくるイメージです.
あとは,オセロの盤面を出力するための関数を別に定義しておきます.
これはとりあえず,2次元リストを1行ずつ出力するだけのものです.

ここまでのコードは以下です.

def otlprint(board):  #盤面を出力する関数
    for i in range(10):
            print(board[i])    

#Othello Class
class OthelloBoard:
    def __init__(self):
        self.board = [[0 if 0<i<9 else 9 for i in range(10)] if 0<j<9 else [9 for i in range(10)] for j in range(10)]  #ボード準備
        self.board[4][4], self.board[4][5], self.board[5][4], self.board[5][5] = [1,2,2,1]  #初期配置
        print("初期配置")
        otlprint(self.board)

出力部分の工夫

どうせなら出力するときには0/1/2/9のわかりにくい表示から,〼/○/●/■のわかりやすい,それっぽい表示にしたいところです.
これは出力関数をちょっといじることで簡単に実装できました.

def otlprint(board):  #数字で表現された盤面を●や◯に変換する関数
    convert_dict={0:"〼", 1:"○", 2:"●", 9:"■"}
    converted_list = [[convert_dict[board[j][i]] for i in range(10)] for j in range(10)]
    for i in range(10):
            print("".join(converted_list[i]) )   

わーい それっぽーい
f:id:muromura:20170724234334p:plain

ひっくり返す機能の実装

次に,オセロボードクラスのメソッドとして,1.指し手の入力を受け付けて盤面を変化させる(オセロのルールに則って駒をひっくり返す)機能と,2.現在の盤面を出力する機能をつくります.

オセロはタテ・ヨコ・ナナメにひっくり返すことができるので,近傍8マスの延長線上を探索していけばいいということになります.
ひっくり返せるかどうかの判定は,以下のアルゴリズムに従えばできそうです.

for 探索方向 ∈ 8近傍 do
    探索方向に1マス進む
        if 相手の色以外 then
            その方向の探索終了
        else:
            while 現在のマスに相手の色の駒が置かれている
                現在のマス目を記憶する
                探索方向に1マス進む
                    if 現在のマスに自分の色の駒が置かれている:
                    for マス目 ∈ 履歴 do
                        マス目の駒を自分の色に変える

このアルゴリズムの場合,ボードの端を9として表現しておいたおかげで,端に到達したらwhile文を自動的に終了させることができます.良い方法なのかどうかはわかりませんが,動くことには動きます.

あとは数点考えておきたいポイントがありました.
探索方向については8通りしかないので,インスタンス変数かクラス変数で定義しておくと良さそうです.
また将来,対局を振り返る機能をつくりたいので,一手ごとに盤面を逐次格納するためのインスタンス変数も確保しておきたいところです.

これらを用いてアップデートしたオセロボードクラスは以下のようになりました.

#オセロ(othello)を組んでみる
def otlprint(board):  #数字で表現された盤面を●や◯に変換する関数
    convert_dict={0:"〼", 1:"○", 2:"●", 9:"■"}
    converted_list = [[convert_dict[board[j][i]] for i in range(10)] for j in range(10)]
    for i in range(10):
            print("".join(converted_list[i]) )                
                
    
            
#Othello Class
class OthelloBoard:
    def __init__(self):
        self.board = [[0 if 0<i<9 else 9 for i in range(10)] if 0<j<9 else [9 for i in range(10)] for j in range(10)]  #ボード準備
        self.board[4][4], self.board[4][5], self.board[5][4], self.board[5][5] = [1,2,2,1]  #初期配置
        self.direction = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]]  #周辺8マスへの方向
        self.hist = []  #履歴メモ用
        print("初期配置")  #インスタンス呼び出し時に初期配置を出力
        otlprint(self.board)
        
    def put(self, teban, pos):  #打ち手を入力して盤面を更新する
        self.board[pos[0]][pos[1]] = teban
        for dx,dy in self.direction:  #8近傍から伸びる直線のうち,どれを探索しているか
            x = pos[0]+dx
            y = pos[1]+dy
            if( self.board[x][y]!=3-teban ): #相手の色以外ならその方向の探索終了
                continue
            else:
                tmp=[] #探索したマスのメモ
                while ( self.board[x][y]==3-teban ): #相手の色である限り探索方向に進む
                    tmp.append([x,y])
                    x+=dx
                    y+=dy
                if ( self.board[x][y]==teban ):  #挟まれていたら,手番の色にひっくり返す
                    for x,y in tmp:
                        self.board[x][y]=teban
        self.hist.append(self.board)
        
    def out(self): #現在の局面を表示する
        print("\n",len(self.hist),"手目")
        otlprint(self.board)


動作チェックは以下.

board = OthelloBoard()

board.put(1,[5,3])
board.out()
board.put(2,[6,3])
board.out()
board.put(1,[6,4])
board.out()
board.put(2,[6,5])
board.out()

f:id:muromura:20170724230918p:plain
いまのところちゃんと動いているようです!