オセロコンピュータを超単純アルゴリズムで実装

近況報告

AIの研究室に所属している先輩にオススメの本を何冊か教えていただき、たまに学びの定着のため簡単なものを作りながら、ただひたすら座学していました。初めてAIについて体系的に学ぶことができて、前に比べればかなり知識がつきました。
ただ、肝心の深層学習について、パソコンのスペック、データ収集などなすべき課題が多く、億劫になりまだなにも作れていません。
自分でいろいろ調べながら、近日中に挑戦しようと思います。

「このままではいけない」という焦りがありつつも、大学、バイトの時間で有害な安心感を得てしまう。停滞に慣れることがないよう、精進します。

アルゴリズムについて

現在置ける候補の場所について、それぞれ置いた際の勝ち負けの期待値を推測、一番期待値の高い場所に置く。
期待値推測は、置いた場所からエピソード終了まで両方方策ランダムで試行、これをε-Greedyで任意の回数行う。

ただこれだけ。価値関数などは設定してないです。

結果

・設定
ε：0.2
一手当たりの試行回数：１５０回

ランダムに置くコンピュータと１００回対戦させた結果、勝ち９６回、引き分け１回、負け３回でした。

考察

さすがにまだ弱かった。
方策ランダムでの期待値推測は正直ではあるけど、状況の前後関係を考慮できていない。オセロのようなゲームは特に、ゲーム木の特定の一本にこそ勝ち筋があると思うから、それは致命的。
盤面が不確定に動くから、もはやDQNしかないのでは、とも思う。

ソースコード

ビット演算についても学んだのに、C++の環境構築が面倒でビットボードでの実装はしていません。遊ぶ用でもないので、細かい処理や例外処理はしてないです。

オセロ

import random
import copy
from abc import ABC, abstractmethod

class Board:
    directions = [-11, -10, -9, -1, 1, 9, 10, 11]
    opposite_stone = {1: 2, 2: 1}
    
    def __init__(self):
        self.places = [
              5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
              5, 0, 0, 0, 0, 0, 0, 0, 0, 5,
              5, 0, 0, 0, 0, 0, 0, 0, 0, 5,
              5, 0, 0, 0, 0, 0, 0, 0, 0, 5,
              5, 0, 0, 0, 2, 1, 0, 0, 0, 5,
              5, 0, 0, 0, 1, 2, 0, 0, 0, 5,
              5, 0, 0, 0, 0, 0, 0, 0, 0, 5,
              5, 0, 0, 0, 0, 0, 0, 0, 0, 5,
              5, 0, 0, 0, 0, 0, 0, 0, 0, 5,
              5, 5, 5, 5, 5, 5, 5, 5, 5, 5
        ]
    
    def putable_directions(self, place, my_stone):
        opp_stone = self.opposite_stone[my_stone]
        putable_directions = []
        
        for direction in self.directions:
            if(self.places[place+direction] == 0 or
               self.places[place+direction] == 5 or 
               self.places[place+direction] == my_stone):
                continue
            
            if self.places[place+direction] == opp_stone:
                for i in range(1, 10):
                    if self.places[place+i*direction] == opp_stone:
                        continue
                    elif self.places[place+i*direction] == my_stone:
                        putable_directions.append(direction)
                        break
                    else:
                        break
        return putable_directions
        
    def put(self, place, my_stone, putable_places):
        for direction in putable_places[place]:
            for i in range(1, 10):
                if self.places[place+i*direction] == my_stone:    
                    break
                self.places[place+i*direction] = my_stone
        self.places[place] = my_stone
            
    
    def putable_places(self, my_stone):
        putable_places = {}
        for place, stone in enumerate(self.places):
            if stone == 0:
                putable_directions = self.putable_directions(place, my_stone)
                if len(putable_directions) != 0:
                    putable_places[place] = putable_directions
        return putable_places
                    
    def show(self):
        print("\n")
        for place,stone in enumerate(self.places):
            if(place > 10) and (place < 90) and (place%10 != 0) and (place%10 != 9):
                if stone == 1:
                    print("O\t", end="")
                elif stone == 2:
                    print("X\t", end="")
                else:
                    print(f'{place}\t', end="")
                
                if place%10 == 8:
                    print("\n")
    
    def cnt_stones(self):
        cnt1 = 0
        cnt2 = 0
        for place in self.places:
            if place == 1:
                cnt1 += 1
            elif place == 2:
                cnt2 += 1
        return cnt1, cnt2
                
    
class Player(ABC):
    def __init__(self, stone, name):
        self.stone = stone
        self.name = name
    
    @abstractmethod
    def decide_place(self, putable_places):
        """置く場所を決めて、置く場所を返す"""
        ...


class HumanPlayer(Player):
    def decide_place(self, putable_places, board):
        print(f"あなたの番です。{list(putable_places.keys())}に置けます")
        return int(input("どこに置きますか？"))
    
    
class ComputerPlayer(Player):
    def __init__(self, stone, name):
        super().__init__(stone, name)
        self.strategy = KitaitiGreedy()
    
    def decide_place(self, putable_places, board):
        return self.strategy.evaluate_greedy(board, putable_places)
    

class RandomPlayer(Player):
    def decide_place(self, putable_places, board):
        return random.choice(list(putable_places.keys()))


class KitaitiGreedy:
    def __init__(self, epsilon = 0.2):
        self.epsilon = epsilon
        
    def trial_run(self, board, place, putable_places):
        putable_or_False = True
        my_stone = 2
        board.put(place, my_stone, putable_places)
        while True:
            my_stone = board.opposite_stone[my_stone]
            putable_places = board.putable_places(my_stone)
            if len(putable_places) == 0:
                if putable_or_False:
                    putable_or_False = False
                    continue
                break
            else:
                putable_or_False = True
            place = random.choice(list(putable_places.keys()))#置き方はランダム
            board.put(place, my_stone, putable_places)
        cnt1, cnt2 = board.cnt_stones()
        if cnt1 > cnt2:
            return -2
        elif cnt1 == cnt2:
            return 1
        elif cnt1 < cnt2:
            return 2
            
    
    def evaluate_greedy(self, board, putable_places):
        value_places = {}
        for place in putable_places.keys():
            value_places[place] = 0
            for _ in range(10):
                try_board = copy.deepcopy(board)
                value_places[place] += self.trial_run(try_board, place, putable_places)
            value_places[place] /= 10
        for n in range(150):
            if self.epsilon > random.random():#epsilonの確率でランダム実行
                place = random.choice(list(value_places.keys()))
            else:
                max_value = -150
                for place, value in value_places.items():
                    if value > max_value:
                        max_value = value
                        max_place = place
                place = max_place
            try_board = copy.deepcopy(board)
            reward = self.trial_run(try_board, place, putable_places)
            value_places[place] = n*value_places[place] + reward / (n+1)#平均の逐次計算
            
        return max_place#最後の一回はいいや。

    
def main():
    board = Board()
    human = HumanPlayer(1, "あなた")
    computer = ComputerPlayer(2, "コンピューター")
    turn = {human: computer, computer: human}
    player = computer
    putable_or_False = True
    
    while True:
        player = turn[player]
        board.show()
        putable_places = board.putable_places(player.stone)
        if len(putable_places) == 0:
            print(f"{player.name}はどこにも置けません。")
            if putable_or_False:
                putable_or_False = False
                continue
            break
        else:
            putable_or_False = True
        place = player.decide_place(putable_places, board)
        board.put(place, player.stone, putable_places)
        
    cnt1, cnt2 = board.cnt_stones()
    print(f"{cnt1}対{cnt2}で")
    if cnt1 > cnt2:
        print("あなたの勝ちです")
    elif cnt1 == cnt2:
        print("引き分けです")
    elif cnt1 < cnt2:
        print("コンピュータの勝ちです")
        

if __name__ == "__main__":
    main()