気が付いたらオセロAIを書くことになっていた話

言い出しっぺが責任を持ちます

たぶん去年、授業でPythonを扱うことになり、そのうちにグループで何かしらを作って発表することになったことがありました。軽率に「オセロでもやらね？」って言ったら本当にオセロをやることになり、言い出しっぺである僕がAIを書くことになりました。最初は「まあちょろいだろ」って思ってたけど、軽く調べたら不安になるくらい難しいことばかり書いてありました。もうどうでもよくなったので（よくない）、とりあえず思い付きのコードで実装してみた。そしたらなんかそれなりに上手いこと動いたのでよかった（ほんまか？）。丸一日かけて書いたからしんどかった記憶がある。
自分の担当はAIだけだったので、手順決めや表示等はほかの人がやっています。他人のコードを晒すわけにはいかないので、自分が書いたAIとオセロのシステムのコードだけ公開します。ソースコードは以下２つ。

・example.py：使用例
・Reversi.py ：システムとAI本体

ソースコード

example.py

import Reversi

#インスタンス生成
a = Reversi.reversi(30,8,'black')

while(1):
    #盤面表示
    a.ShowBoardPic(a.table)

    #プレイヤーの手番
    a.PlayerTurn()

    #ゲーム終了かどうか確認
    if a.EndGameCheck():break
    #AIの手番
    a.AITurn()
    #ゲーム終了かどうか確認
    if a.EndGameCheck():break

Reversi.py

import sys
import copy
import random
from PIL import Image,ImageDraw
import re


#角の追加点
edge_additional = 10

#敵の角の減点
enemy_edge_additional = -10

#辺の追加点
side_additional = 1

#角のL字の追加点
edgel_additional = 3

#外より位置マス内側の減点
outline_additional = -3

#未使用
sideenemy_additional = -3

class reversi:
    lv = 1
    table = [[]]
    n = 8
    side = 0
    
    isVisiblePoint = False


    def __init__(self,level:int,size:int,AIside:str):
        #引数エラー処理群
        if(level <= 1):
            print("Error:Make sure the level is 1 or higher.")
            sys.exit()
        if(size % 2 == 1):
            print("Error:Make sure size is even number.")
            sys.exit()
        if(4 > size):
            print("Error:Make sure minimum size is 6.")
            sys.exit()
        isTrueSide = False
        if(AIside == 'black'):isTrueSide = True
        if(AIside =='white'):isTrueSide = True
        if isTrueSide == False:
            print("Error:Make sure AI side is \"black\" or \"white\".")
        
        #各情報出力
        print("AI level is",level,"\nsize is",size,"×",size)
        
        #各値代入
        self.n = size
        self.lv = level
        if(AIside=='white'):self.side = 1
        if(AIside=='black'):self.side = -1
        self.table = [[0] * size for i in range(size)]
        
        #テーブル初期化 白1 黒-1
        for i in range(self.n):
            for j in range(self.n):
                if (i == size / 2 - 1)&(j == size / 2 - 1):
                    self.table[i][j] = 1
                    self.table[i][j+1] = -1
                    self.table[i+1][j] = -1
                    self.table[i+1][j+1] = 1


    def VisiblePoint(self,a:bool):self.isVisiblePoint = a

    #盤面の様子をjpg出力
    def GenerateBoardPic(self,name:str,board:list):
        im = Image.new('RGB', (self.n * 100, self.n * 100), (0, 128, 0))
        draw = ImageDraw.Draw(im)
        
        for i in range(self.n - 1):
            draw.line(((i + 1) * 100,0,(i + 1) * 100,self.n * 100),width = 3,fill=(0,0,0))
        
        for i in range(self.n - 1):
            draw.line((0,(i + 1) * 100,self.n * 100,(i + 1) * 100),width = 3,fill=(0,0,0))
        
        for i in range(self.n):
            for j in range(self.n):
                if(board[i][j]==1):
                    draw.ellipse((i * 100 + 5,j * 100 + 5,i * 100 + 95,j * 100 + 95),width = 3,fill=(255,255,255),outline=(0,0,0))
                if(board[i][j]==-1):
                    draw.ellipse((i * 100 + 5,j * 100 + 5,i * 100 + 95,j * 100 + 95),width = 3,fill=(0,0,0),outline=(0,0,0))
        
        for i in range(0,self.n):
            for j in range(0,self.n):
                draw.text((i * 100 + 40,j * 100 + 40),str((i,j)),fill=(128,0,0))
        
        im.save(name)

    #盤面の様子を標準機能で表示
    def ShowBoardPic(self):
        board = self.table
        im = Image.new('RGB', (self.n * 100, self.n * 100), (0, 128, 0))
        draw = ImageDraw.Draw(im)
        
        for i in range(self.n - 1):
            draw.line(((i + 1) * 100,0,(i + 1) * 100,self.n * 100),width = 3,fill=(0,0,0))
        
        for i in range(self.n - 1):
            draw.line((0,(i + 1) * 100,self.n * 100,(i + 1) * 100),width = 3,fill=(0,0,0))
        
        for i in range(self.n):
            for j in range(self.n):
                if(board[i][j]==1):
                    draw.ellipse((i * 100 + 5,j * 100 + 5,i * 100 + 95,j * 100 + 95),width = 3,fill=(255,255,255),outline=(0,0,0))
                if(board[i][j]==-1):
                    draw.ellipse((i * 100 + 5,j * 100 + 5,i * 100 + 95,j * 100 + 95),width = 3,fill=(0,0,0),outline=(0,0,0))
        
        for i in range(0,self.n):
            for j in range(0,self.n):
                draw.text((i * 100 + 40,j * 100 + 40),str((i,j)),fill=(128,0,0))
        
        im.show()


    def OneLinerFromAdditionalPoint(self,s:int,line:list):
        isToSearch = True
        if len(line) < 3:isToSearch = False
        if(len(line)!=1):
            if line[1] != s * (-1):isToSearch = False
        
        ans = 0
        if isToSearch:
            #指定色基準に反転
            for i in range(0,len(line)):
                line[i] *= s
        
            #追加点の計算
            for i in range(1,len(line) - 1):
                #0以外,0の並びが見つかったら追加点0にしてやめる
                if (line[i]!=0)&(line[i + 1] == 0):
                    ans = 0
                    break
                    
                #-1,1の並びを探す
                ans += 1
                if(line[i]==-1)&(line[i + 1] == 1): break
                #最後まで移動したら追加点0
                if i==len(line) - 2:
                    ans = 0
                    break
        return ans

    #配置可能な場所か確認(0)　返り値:(追加取得マス数,[方向])
    def isTruePos(self,x:int,y:int,board:list,col:str):
        #引数確認
        if(x > self.n - 1):return [0,None]
        if(y > self.n - 1):return [0,None]
        
        
        s = 0
        if(col == 'white'):s = 1
        if(col == 'black'):s = -1
        if(s==0):return [0,None]
        
        #既におかれているなら0
        if(board[x][y] != 0) : return [0,None]
        
        #総計用
        AddPoint = 0
        
        #方向
        direction = []
        
        #右方向
        line = []
        for i in range(x,self.n):
            line.append(board[i][y])
        tmp = self.OneLinerFromAdditionalPoint(s,line)
        AddPoint += tmp
        if tmp !=0:direction.append('right')
        
        #左方向
        line = []
        for i in range(0,x + 1):
            line.append(board[x-i][y])
        tmp = self.OneLinerFromAdditionalPoint(s,line)
        AddPoint += tmp
        if tmp !=0:direction.append('left')
        
        #上方向
        line = []
        for i in range(0,y + 1):
            line.append(board[x][y-i])
        tmp = self.OneLinerFromAdditionalPoint(s,line)
        AddPoint += tmp
        if tmp !=0:direction.append('upper')
        
        #下方向
        line = []
        for i in range(y,self.n):
            line.append(board[x][i])
        tmp = self.OneLinerFromAdditionalPoint(s,line)
        AddPoint += tmp
        if tmp !=0:direction.append('downer')
        
        #右斜め上方向
        line = []
        for i in range(0,self.n):
            if((x + i > self.n - 1)|(y - i < 0)):break
            line.append(board[x + i][y - i])
        tmp = self.OneLinerFromAdditionalPoint(s,line)
        AddPoint += tmp
        if tmp !=0:direction.append('right_upper')
        
        #右斜め下方向
        line = []
        for i in range(0,self.n):
            if((x + i > self.n - 1)|(y + i > self.n - 1)):break
            line.append(board[x + i][y + i])
        tmp = self.OneLinerFromAdditionalPoint(s,line)
        AddPoint += tmp
        if tmp !=0:direction.append('right_downer')
        
        #左斜め上方向
        line = []
        for i in range(0,self.n):
            if((x - i < 0)|(y - i < 0)):break
            line.append(board[x - i][y - i])
        tmp = self.OneLinerFromAdditionalPoint(s,line)
        AddPoint += tmp
        if tmp !=0:direction.append('left_upper')
        
        #左斜め下方向
        line = []
        for i in range(0,self.n):
            if((x - i < 0)|(y + i > self.n - 1)):break
            line.append(board[x - i][y + i])
        tmp = self.OneLinerFromAdditionalPoint(s,line)
        AddPoint += tmp
        if tmp !=0:direction.append('left_downer')
        
        return [AddPoint,direction]


    def TablePoint(self,x:int,y:int,board:list,col:str):
        t = 0
        myside = 1 if col == 'white' else -1
        enemyside = -myside
        
        #数
        for i in range(0,self.n):
            for j in range(0,self.n):
                if board[i][j] == myside:
                    t += 1
        
        #辺
        for k in range(0,self.n):
            if board[0][k] == myside:
                t += side_additional
        for k in range(0,self.n):
            if board[k][0] == myside:
                t += side_additional
        for k in range(0,self.n):
            if board[self.n - 1][k] == myside:
                t += side_additional
        for k in range(0,self.n):
            if board[k][self.n - 1] == myside:
                t += side_additional
        
        #角
        if board[0][0] == myside:t += edge_additional
        if board[self.n - 1][0] == myside:t += edge_additional
        if board[0][self.n - 1] == myside:t += edge_additional
        if board[self.n - 1][self.n - 1] == myside:t += edge_additional
        
        #辺より1マス内側に置こうとする場合
        if x == 1:t += outline_additional
        if y == 1:t += outline_additional
        if x == self.n - 2:t += outline_additional
        if y == self.n - 2:t += outline_additional
        
        #敵が角を取った場合
        if board[0][0] == enemyside:t += enemy_edge_additional
        if board[self.n - 1][0] == enemyside:t += enemy_edge_additional
        if board[0][self.n - 1] == enemyside:t += enemy_edge_additional
        if board[self.n - 1][self.n - 1] == enemyside:t += enemy_edge_additional
        
        return t


    def MaxPoint(self,board:list,col:str):
        pos = []
        index = 0
        enemyside = -1 if col == 'white' else 1
        myside = -enemyside
        
        maximum = [0,0,-999]
        
        for i in range(0,self.n):
            for j in range(0,self.n):
                t = self.isTruePos(i,j,board,col)[0]
                if t == 0:continue
                t = 0
                for k in range(0,self.n):
                    for l in range(0,self.n):
                        if self.table[k][l] == myside:t += 1
                
                #得点計算用盤面
                tmpb = copy.deepcopy(board)
                self.BoardUpdate(i,j,col,tmpb)
                
                t += self.TablePoint(i,j,tmpb,col)
                
                pos.append([i,j,t])
                if index == 0:maximum = [i,j,t]
                index += 1
        
        
        for i in range(0,len(pos)):
            if(pos[i][2]>maximum[2]):maximum = pos[i]
        
        return maximum


    def FlipOnLine(self,line,col):
        s = 1 if col == 'white' else -1
        for i in range(len(line)):
            #同色がきたら抜ける
            if line[i] == s:break
            #異色がきたら反転
            if line[i] == -s:line[i] = s
        return line


    def BoardUpdate(self,x,y,col:str,board:list):
        p = self.isTruePos(x,y,board,col)
        if(p[0] < 1):return
        
        for s in p[1]:
            if s== 'right':
                line = []
                for i in range(x,self.n):
                    line.append(board[i][y])
                line = self.FlipOnLine(line,col)
                for i in range(0,len(line)):
                    board[x + i][y] = line[i]
            
            if s == 'left':
                line = []
                for i in range(0,x):
                    line.append(board[x - i][y])
                line = self.FlipOnLine(line,col)
                for i in range(0,len(line)):
                    board[x - i][y] = line[i]
            
            if s == 'upper':
                line = []
                for i in range(0,y):
                    line.append(board[x][y - i])
                line = self.FlipOnLine(line,col)
                for i in range(0,len(line)):
                    board[x][y - i] = line[i]

            if s == 'downer':
                line = []
                for i in range(y,self.n):
                    line.append(board[x][i])
                line = self.FlipOnLine(line,col)
                for i in range(0,len(line)):
                    board[x][y + i] = line[i]
            
            if s == 'right_upper':
                line = []
                for i in range(0,self.n):
                    if((x + i > self.n - 1)|(y - i < 0)):break
                    line.append(board[x + i][y - i])
                line = self.FlipOnLine(line,col)
                for i in range(0,len(line)):
                    board[x + i][y - i] = line[i]
            
            if s == 'right_downer':
                line = []
                for i in range(0,self.n):
                    if((x + i > self.n - 1)|(y + i > self.n - 1)):break
                    line.append(board[x + i][y + i])
                line = self.FlipOnLine(line,col)
                for i in range(0,len(line)):
                    board[x + i][y + i] = line[i]
            
            if s == 'left_upper':
                line = []
                for i in range(0,self.n):
                    if((x - i < 0)|(y - i < 0)):break
                    line.append(board[x - i][y - i])
                line = self.FlipOnLine(line,col)
                for i in range(0,len(line)):
                    board[x - i][y - i] = line[i]
            
            if s == 'left_downer':
                line = []
                for i in range(0,self.n):
                    if((x - i < 0)|(y + i > self.n - 1)):break
                    line.append(board[x - i][y + i])
                line = self.FlipOnLine(line,col)
                for i in range(0,len(line)):
                    board[x - i][y + i] = line[i]
        
        #指定地点に自色を置く
        board[x][y] = 1 if col=='white' else -1


    def NextMaxPointPos(self,board:list,col:str):
        enemycol = 'black' if col == 'white' else 'white'
        
        pos = []
        
        index = 0
        
        #候補地に設置
        for ai in range(0,self.n):
            for aj in range(0,self.n):
                atmp = copy.deepcopy(board)
                a = self.isTruePos(ai,aj,atmp,col)[0]
                if a == 0:continue
                self.BoardUpdate(ai,aj,col,atmp)
                
                #敵の最善手で進める
                epos = self.MaxPoint(atmp,enemycol)
                self.BoardUpdate(epos[0],epos[1],enemycol,atmp)
                
                #次の手の得点を算出
                ptmp = self.MaxPoint(atmp,col)
                
                #得点と座標を格納
                pos.append([ai,aj,ptmp[2] - epos[2]])
        
        #得点で昇順ソート
        for i in range(0,len(pos) - 1):
            for j in range(i,len(pos)):
                if pos[i][2] < pos[j][2]:
                    tmp = pos[i]
                    pos[i] = pos[j]
                    pos[j] = tmp
        
        #同得点のものからランダム選出
        mp = pos[0][2]
        index = 0
        for i in range(1,len(pos)):
            if mp != pos[i][2]:
                break
            index += 1
        
        for i in range(0,index):
            a = random.randint(0,index - 1)
            b = random.randint(0,index - 1)
            tmp = pos[a]
            pos[a] = pos[b]
            pos[b] = tmp
        
        
        return (pos[0][0],pos[0][1])


    def isAbleToPut(self,board:list,col:str):
        for i in range(0,self.n):
            for j in range(0,self.n):
                if self.isTruePos(i,j,board,col)[0] != 0:return True
        return False


    def ReadLvLoop(self,level,board:list,col:str):
        #一手先を出す
        pos = self.NextMaxPointPos(board,col)
        
        if self.isAbleToPut(board,col):
            #これ以上先を読めなければ、座標を返して再帰ループから抜ける
            return (pos[0],pos[1])
        
        #一手先の盤面をつくる
        tmpb = copy.deepcopy(board)
        self.BoardUpdate(pos[0],pos[1],col,tmpb)
        
        if level == 1:
            #level - 1回繰り返したら次の手を返して再帰ループから抜ける
            return (pos[0],pos[1])
        
        print(level)
        #一手先の盤面を現在の盤面、level - 1として再帰呼び出し
        return self.ReadLvLoop(level - 1,tmpb,col)

#AIのターン
    def AITurn(self):
        self.EndGameCheck()
        mycol = 'white' if self.side == 1 else 'black'
        if self.isAbleToPut(self.table,mycol) == False:
            print('AI passed')
            return
        
        fs = self.ReadLvLoop(self.lv,self.table,mycol)
        self.BoardUpdate(fs[0],fs[1],mycol,self.table)
        
        print(fs)
        
        if self.isVisiblePoint == True:
            a = self.TablePoint(fs[0],fs[1],self.table,mycol)
            print(a)

#プレイヤーのターン
    def PlayerTurn(self):
        self.EndGameCheck()
        mycol = 'white' if self.side == -1 else 'black'
        if self.isAbleToPut(self.table,mycol) == False:
            print('You passed')
            return
        
        x = 0
        y = 0
        
        while(1):
            print('x y')
            tmp = input()
            
            chk = re.search(r'\d\s\d',tmp)
            
            if chk == None:
                print("Invalid!")
                continue
            
            i = chk.group(0).split()
            
            x = int(i[0])
            y = int(i[1])
            
            a = self.isTruePos(x,y,self.table,mycol)[0]
            if a == 0:
                print("Invalid!")
                continue
            break
        
        
        self.BoardUpdate(x,y,mycol,self.table)
        
        if self.isVisiblePoint == True:
            a = self.TablePoint(x,y,self.table,mycol)
            print(a)

#ゲームが終了したかどうか判定
    def EndGameCheck(self):
        if (self.isAbleToPut(self.table,'white') == False) & (self.isAbleToPut(self.table,'black') == False):
            print('GAME OVER!')
            w = 0
            b = 0
            for i in range(0,self.n):
                for j in range(0,self.n):
                    if self.table[i][j] == 1:
                        w += 1
                    if self.table[i][j] == -1:
                        b += 1
            print('WHITE:',w,' BLACK:',b)
            return True
        return False

3,2\n　とか打つと、左から4つ目、上から３つ目の位置に自分の色を置けます。
このまま動かすと、デバッグ用に用意した盤面の画像が別窓で表示されます。画像データだけを出力もできるので、tkinterとかで適当にGUIに表示するのがいいかもしれません。

仕組み

AIのカラクリとしては割と単純で、盤面の状態を点数化して、その点数が高くなるように指していきます。点数は、盤面に自分の色が増えるほど高くなり、また角や辺をたくさん取れるとより点数が高くなるようにしています。AIは、プレイヤーも常に点数が高くなるように指してくると想定して盤面を読み進めます。これをすべてのマスに対して行い、一定手数先まで読んだときに一番点数が高かったマスに指します。レベルの数値は、この先読みする手数となっています。

まとめ

クラスメイトを数人ボコボコにできたので非常に満足です。
２つのシステムで盤面を共有できるので、やろうと思えばプレイヤー vsプレイヤーとか、AI vs AIもできます。