三目並べ 人vs人 から 人vs CPU

Question

三目並べの人vs人のプログラムを完成させ、ここから人vs CPU に派生させたいと思っているのですが
いろいろサイトを調べてもどうしたらよいかわからずご教授願いたいです。

モンテカルロ法で強化学習をしたいと考えています。

Answer 1

CPUってそんな簡単にできるものじゃないんですよ。探索ってご存知ですか？ゲーム理論でいうゲーム木を用いたものなのですが、まずはそこを学んだ方が良いと思います。一つ一つ着実に行きましょう。

ボードゲームの思考アルゴリズムの入門

再帰関数として実装してやるのが一般的です。
あくまで一例です。色々な例外処理は抜けていますし省略も多いです。そこは自分で考えてください。

def min_search(board,depth,target):
    moves = generate_moves(board)
    min_move = 1000000
    if depth != target:
        for move in moves:
            value = max_search(update(move),depth+1,target)
            if value < min_move:
                min_move = value
    else:
        for move in moves:
            value = evaluate_move(update(move))
            if value < min_move:
                min_move = value
    return min_move

def max_search(board,depth,target):
    moves = generate_moves(board)
    max_move = -1000000
    best_move = moves[0]
    if depth != target:
        moves = generate_moves(board)
        for move in moves:
            value = min_search(update(move),depth+1,target)
            if value > max_move:
                max_move = value
                best_move = move
    else:
        for move in moves:
            value = evaluate_move(update(move))
            if value > max_move:
                max_move = value
                best_move = move
    return best_move if depth == 1 else max_move

def min_max(target):
    return max_search(board,1,target)

if __name__ == '__main__':
    best_move = min_max(5)#５手探索

Comments

[DANNBU]

読ませていただきました。
そのサイトの中にあるようにminimax法について勉強した方がよいでしょうか？

[_Victorique__]

minimax法は探索の中でも基礎の基礎にあたる大事な部分ですのでそこから始めるのが妥当ですね。

[DANNBU]

返信遅くなって申し訳ありません。
minimax法について調べていたアルゴリズムは理解できたのですが、
ここからコードに起こすとなるとイメージがつかめてない状況です・・・

[_Victorique__]

追記しました

[DANNBU]

コード載せていただきありがとうございます。
このコードを読み解くことから始めてみます！

[DANNBU]

すみません。

このコードでのboard と generate_movesは何を表しているのでしょうか？

[_Victorique__]

それぞれ盤面、指し手の生成です。
関数の実装は省略しています。

[DANNBU]

boardとはself.boardとまた別物ですか？？

指し手の生成というのがよくわからないんですが、碁を打ったときに打った場所の位置を保存するっていう感じの関数ですか？？

[_Victorique__]

ボードゲームにおける一般的な盤面の情報なので作りたいゲームの盤に当てはめてください。

5手読みなら
▲1手目
△2手目
▲3手目
△4手目
▲5手目
のように盤面を5手進めた後の盤面の評価を数字にします。generate_moveではその手番で考えうる全ての手を用意して全て調べます。なので手番で各50通りの指し方があった場合、50^5乗通りの盤面を調べることになります。

もう少しゲーム木について調べてください。

[DANNBU]

かなり遅くなって申し訳ないです。

generate_movesとevaluate_moveの関数を新たに作らないとだめですよね？

[_Victorique__]

そうです。
そこらへんは自分で頑張って実装してください。

[DANNBU]

質問が多くなって申し訳ないです。
moves = generate_moves(board)
for move in moves:
このfor文の動きがいまいち理解できなくて...

Answer 2

盤の大きさによりますが、まずはシンプルにminimaxやAlpha-Beta Pruningなど定番の探索アルゴリズムを幾つか実装してみるのはいかがでしょうか。

その過程で局面ごとの評価関数の実装方法や、ゲーム木探索時のクセが見えてくると思うので、アウトプットを強化学習にも活かせると思います。また複数のアルゴリズム同士を対戦させて評価過程を見たりするのも楽しいですよ。

Comments

[DANNBU]

私自身、そういった探索アルゴリズムに関してはまったく無知なのですが
やはり実装するなら最初はminimaxとかから取り組むほうが良いですか？

[shuntksh]

大学の授業などではゲーム木や探索について軽く触れたあと、MiniMaxから始めるのが定番だとおもいます。シンプルな総当りのアルゴリズムで実行が遅いですが、実装は楽です。おそらくDANNBUさんが一番苦戦するのは評価関数の実装でしょうか。_Victorique__さんの回答にある通り、入門書／サイトを探して一つづつ進めていくと良いと思いますよ。