友人とオセロAIで勝負する話　準備編

AlphaGoが囲碁世界チャンピオンに勝ったのは何年前のことでしょうか(3年前とのことです[^1])。今となっては様々な手法が開発され、AI同士で戦わせることが多いみたいです。

というわけで今回は私の友人N氏の作るAIと私のそれを戦わせようという話になります（いったい何億番煎じなのだろうか）。

日記みたいにシリーズものとして書いていくので宜しくお願いします。

#縛り
今回友人と対戦する際に縛りを設けました。
それは

**一切の探索をしないことです**

AlphaGoの後継機であるAlphaZeroはモンテカルロ木探索と深層学習を組み合わせた手法[^1]で強さを得ていますが、その半分をあえて捨ててるわけです。なぜこのような縛りを設けているかというと、友人が探索をメインとした手法でAIを作るからですね。いわゆる探索vs深層学習という構図なわけです。

ではどのようにAIを作るかというと、乱数や生成したモデルを基に試合をこなしその譜面情報をAIに学習させるわけです。勝利するために必要な特徴量とかはモデルにがんばって拾ってもらうわけです。

#準備
オセロAIを作る際にまず必要なのはオセロ自体をするためのルール決めや盤面情報の管理手段です。なのでこの準備編ではそれらを作った時の状況について説明したいと思います。

まず最初に述べておきたいことを言っておきます。

**アルゴリズム以外の高速化の手段は取っておけ**

私はオセロゲーム自体の高速化についてはあまり気を配らなかったのですが（なにせ8*8の盤面ですからね、誤差レベルだと思ってましたよ）、既に学習を始めている今、その読みの甘さが今の現状に響いています。高速化については目途がとりあえず立ってるのでその記事についても書けたらいいなって思います。

#初期化、動く

```python:othello.py
def othelloInit():
    board = np.zeros((8,8))
    board[4-1][4-1]=1
    board[5-1][5-1]=1
    board[4-1][5-1]=-1
    board[5-1][4-1]=-1
    board=board.astype(np.int32)
    return board

def othelloMove(board,move):
    if type(move)==int:
        return -1
    tempBoard=othelloMovable(board,move)
    if type(tempBoard) ==np.ndarray:
        return tempBoard
    else:   
        return 0



```

オセロのゲームシステムについては全部othello.pyに書いていきます。
othelloInit()ではオセロの最初の盤面状態(真ん中だけにリバーシ状態で白黒の駒がおいてある状態)をnumpy.ndarray形式で返します。

また盤面情報を直接モデルに入れるのでクラス化はしません。

othelloMove()ではmove変数の情報をもとに盤面情報を更新します。othelloMovable()で更新できるかどうかを確認し、できないなら0を、できるなら盤面情報を返します。

#動けるだろうか？

```python:othello.py
def othelloBlank(board,move):#空いてるなら0、空いてないなら1
    k=(board[move[0]][move[1]])*(board[move[0]][move[1]])

    return k
def othelloMovable(Board,Move):#moveにおけるかどうかを判定、おけるなら置いた後の盤面情報、おけないなら０を返す
    board=Board.copy()
    move=copy.deepcopy(Move)
    old_board=board.copy()
    if move[0]<0:
        move[0]=0
    elif move[0]>=8:
        move[0]=7
    if move[1]<0:
        move[1]=0
    elif move[1]>=8:
        move[1]=7
    if othelloBlank(board,move)==1:
        return 0
    for i in range(1,9):
        
        #print("ColorCheck:"+str(ColorCheck(board,move,i))+" i:"+str(i))
        if ColorCheck(board,move,i)==-1:
            if i==1:#上
                #print("i:"+str(i))
                check=1
                for k in range(move[1],8):#自身を含めたマスのチェック
                    
                    if k==move[1]:#自分は調べ済みなのでパス
                        pass
                    else:
                        #print([move[0],k])
                        temp=ColorCheck(board,[move[0],k],i)#マスチェック
                        #print("Check:"+str(check))
                        if temp==-1:#相手ならカウントを増やす
                        
                            check=check+1
                        elif temp==1 and check>0:#自分なら反転、一度も相手のマスが出なかった時を除外
                            
                            check=check*-1
                        else:#おいても反転しないので除外
                            
                            break
                    if check<0:#負の値の場合はおける
                        
                        for c in range(0,(check*-1)+1):#カウントの値を参照して変更するべきマスを確定させる。
                            board[move[0]][c+move[1]]=1
                        break
            elif i==2:#右上
                #print("i:"+str(i))
                temp_move=max(move)
                check=1
                for k in range(temp_move,8):#自身を含めたマスのチェック
                    
                    if k==temp_move:#自分は調べ済みなのでパス
                        pass
                    else:
                        temp=ColorCheck(board,[move[0]+k-temp_move,move[1]+k-temp_move],i)#マスチェック
                        #print("Check:"+str(check))
                        if temp==-1:#相手ならカウントを増やす
                            check=check+1
                        elif temp==1 and check>0:#自分なら反転、一度も相手のマスが出なかった時を除外
                            check=check*-1
                        else:#おいても反転しないので除外
                            
                            break
                    if check<0:#負の値の場合はおける
                        for c in range(0,(check*-1)+1):#カウントの値を参照して変更するべきマスを確定させる。
                            board[c+move[0]][c+move[1]]=1
                        break
            elif i==3:#右
                #print("i:"+str(i))
                check=1
                for k in range(move[0],8):#自身を含めたマスのチェック
                    
                    if k==move[0]:#自分は調べ済みなのでパス
                        pass
                    else:
                        temp=ColorCheck(board,[k,move[1]],i)#マスチェック
                        #print("Check:"+str(check))
                        if temp==-1:#相手ならカウントを増やす
                          
                            check=check+1
                        elif temp==1 and check>0:#自分なら反転、一度も相手のマスが出なかった時を除外
                            
                            check=check*-1
                        else:#おいても反転しないので除外
                            
                            break
                    if check<0:#負の値の場合はおける
                        for c in range(0,(check*-1)+1):#カウントの値を参照して変更するべきマスを確定させる。
                            board[move[0]+c][move[1]]=1
                        break
            elif i==4:#右下
                #print("i:"+str(i))
                temp_move=max(move[0],7-move[1])
                check=1
                for k in range(temp_move,8):#自身を含めたマスのチェック
                    
                    if k==temp_move:#自分は調べ済みなのでパス
                        pass
                    else:
                        temp=ColorCheck(board,[move[0]+k-temp_move,move[1]-k+temp_move],i)#マスチェック
                        #print("Check:"+str(check))
                        if temp==-1:#相手ならカウントを増やす
                            check=check+1
                        elif temp==1 and check>0:#自分なら反転、一度も相手のマスが出なかった時を除外
                            check=check*-1
                        else:#おいても反転しないので除外
                            
                            break
                    if check<0:#負の値の場合はおける
                        for c in range(0,(check*-1)+1):#カウントの値を参照して変更するべきマスを確定させる。
                            board[c+move[0]][-c+move[1]]=1
                        break
            elif i==5:#下
                #print("i:"+str(i))
                check=1
                for k in range(move[1],0,-1):#自身を含めたマスのチェック
                    
                    if k==move[1]:#自分は調べ済みなのでパス
                        pass
                    else:
                        temp=ColorCheck(board,[move[0],k],i)#マスチェック
                        #print("Check:"+str(check))
                        if temp==-1:#相手ならカウントを増やす
                            check=check+1
                        elif temp==1 and check>0:#自分なら反転、一度も相手のマスが出なかった時を除外
                            check=check*-1
                        else:#おいても反転しないので除外
                            
                            break
                    if check<0:#負の値の場合はおける
                        for c in range(0,(check*-1)+1):#カウントの値を参照して変更するべきマスを確定させる。
                            board[move[0]][-c+move[1]]=1
                        break
            elif i==6:#左下
                #print("i:"+str(i))
                temp_move=min(move)
                check=1
                for k in range(temp_move,0,-1):#自身を含めたマスのチェック
                    
                    if k==temp_move:#自分は調べ済みなのでパス
                        pass
                    else:
                        temp=ColorCheck(board,[move[0]+k-temp_move,move[1]+k-temp_move],i)#マスチェック
                        #print("Check:"+str(check))
                        if temp==-1:#相手ならカウントを増やす
                            check=check+1
                        elif temp==1 and check>0:#自分なら反転、一度も相手のマスが出なかった時を除外
                            check=check*-1
                        else:#おいても反転しないので除外
                            
                            break
                    if check<0:#負の値の場合はおける
                        for c in range(0,(check*-1)+1):#カウントの値を参照して変更するべきマスを確定させる。
                            board[-c+move[0]][-c+move[1]]=1
                        break
            elif i==7:#左
                #print("i:"+str(i))
                check=1
                for k in range(move[0],0,-1):#自身を含めたマスのチェック
                    
                    if k==move[0]:#自分は調べ済みなのでパス
                        pass
                    else:
                        temp=ColorCheck(board,[k,move[1]],i)#マスチェック
                        #print("Check:"+str(check))
                        if temp==-1:#相手ならカウントを増やす
                            check=check+1
                        elif temp==1 and check>0:#自分なら反転、一度も相手のマスが出なかった時を除外
                            check=check*-1
                        else:#おいても反転しないので除外
                           
                            break
                            
                    if check<0:#負の値の場合はおける
                        for c in range(0,(check*-1)+1):#カウントの値を参照して変更するべきマスを確定させる。
                            board[move[0]-c][move[1]]=1
                        break
            elif i==8:#左上
                #print("i:"+str(i))
                temp_move=max(7-move[0],move[1])
                check=1
                for k in range(temp_move,8):#自身を含めたマスのチェック
                    
                    if k==temp_move:#自分は調べ済みなのでパス
                        pass
                    else:
                        
                        temp=ColorCheck(board,[move[0]-k+temp_move,move[1]+k-temp_move],i)#マスチェック
                        #print("Check:"+str(check))
                        if temp==-1:#相手ならカウントを増やす
                            check=check+1
                        elif temp==1 and check>0:#自分なら反転、一度も相手のマスが出なかった時を除外
                            check=check*-1
                        else:#おいても反転しないので除外
                            
                            break
                    if check<0:#負の値の場合はおける
                        for c in range(0,(check*-1)+1):#カウントの値を参照して変更するべきマスを確定させる。
                            board[-c+move[0]][c+move[1]]=1
                        break
    if np.allclose(board,old_board):
        #print("置けないです")
        return 0
    return board

```

長い...
othelloBlank()はmove情報を基に盤面上でそこが空いてるかどうかを確認します。分岐使いたくなかったので無理やり計算して返します。

othelloMovable()はmove情報を基にルール的におけるかどうか（ひっくり返る駒があるかどうか）を確認します。ただ長いですね。深夜テンションで書いており、当時の自分はこれでも改善したつもりだった気がするんですが、ここら辺が遅い原因になってそうです。

#やったか？とその他
```python:othello.py
def othelloEndCheck(board):#もうおける場所がないかを調べる。おけるなら1、置けないなら０を返す。
    for i in range(0,8):
        for n in range(0,8):
            #print([i,n])
            if type(othelloMovable(board,[i,n]))==np.ndarray:
                #print("Nope")
                return 1
    return 0

def ColorCheck(board,axis,way):#時計回りで上が１スタートし、8まで予約。0は全方位。盤外なら-2,相手なら-1、空白なら0、自身なら１を返す。
    if way==1:
        if axis[1]>=7:
            return -2
        else:
            #print("ColorCheck")
            #print(board[axis[0]][axis[1]+1])
            return board[axis[0]][axis[1]+1]
    elif way==2:
        if axis[0]>=7 or axis[1]>=7:
            return -2
        else:
            return board[axis[0]+1][axis[1]+1]
    elif way==3:
        if axis[0]>=7:
            return -2
        else:
            return board[axis[0]+1][axis[1]]
    elif way==4:
        if axis[0]>=7 or axis[1]<=0:
            return -2
        else:
            return board[axis[0]+1][axis[1]-1]       
    elif way==5:
        if axis[1]<=0:
            return -2
        else:
            return board[axis[0]][axis[1]-1]
    elif way==6:
        if axis[1]<=0 or axis[0]<=0:
            return -2
        else:
            return board[axis[0]-1][axis[1]-1]
    elif way==7:
        if axis[0]<=0:
            return -2
        else:
            return board[axis[0]-1][axis[1]]
    elif way==8:
        if axis[0]<=0 or axis[1]>=7:
            return -2
        else:
            return board[axis[0]-1][axis[1]+1]


    return 0

```

これまた長い...
othelloEndCheck()はもう打ち手がないかどうかを確認します。打てるなら1を、打てないなら0を返します。

ColorCheck()は（なんでお前だけothelloがついてないんだ？）はmove情報を基にその周囲にあるコマの色を返します。コメントアウトにある全方位については結局使わなかったので未実装です。

#なんか表示するやつ
```python:othello.py
def othelloReverse(Board):
    board=Board.copy()
    #print("reversing")
    board=board*-1
    return board

def othelloShow(board):
    for i in reversed(range(0,8)):#y
        #print("i:"+str(i))
        for k in range(0,8):#x
            if board[k][i]==-1:
                print("○",end=" ")
            elif board[k][i]==1:
                print("●",end=" ")
            elif board[k][i]==0:
                print("■",end=" ")
        print("")
        print("")
    #print(board[7])
    return 0

```
othelloReverse()は盤面の色をひっくり返します。つまり先行後攻を入れ替えるわけですね。これによって打つ側は盤面データ上は常に１になります。

othelloShow()は盤面の状況を表示します。左下を(0,0)にするためにちょっと面倒な感じになってます。将来的には利便性も考えてpygamesを利用したgui方式にしたいと思ってます。


#まとめ
**絶対にネットに出回ってるやつの方が早い。**

私なんて競技プログラミングがめっちゃできるとかそういう人でもなければプログラミングガチ勢でもないのでもっと早くできるアルゴリズムとか思いつきません。

そしてこれらを一通り作ったあとに高速化する手段を知ったので愕然としましたよ...

次回はモデル構築編でお会いできたら幸いです。


[^1]: https://ja.wikipedia.org/wiki/AlphaGo (Wikipediaばんざい)