つくってわくわくゲームAI🐻 ～ゲームモデリング編～

ゴロリ「ワクワクさん、きょうは何つくるの？」
ワクワク「きょうはPythonでゲームAIをつくるよ」
ゴロリ「わーすごいやー！」
Wikipedia「コンピュータゲームにおける人工知能は、コンピュータゲームにおいて、ノンプレイヤーキャラクター (NPC) の振る舞いに知能があるかのような錯覚を生み出す技法である。主な技法は人工知能 (AI) の既存技術を活用したものである。」
Wikipedia「ゲームプレイはAIの初期から研究対象となっていた。初期のAIの例として、ニムというゲームをコンピュータ化したものがあり、1941年に開発され、1942年に発表された。ポンの30年以上前、当時の最先端技術を使ったゲームだが、比較的小さい箱型のゲームであり、ニムの熟練プレーヤーにも普通に勝てるレベルだった。」

ということで、昨今はDeepLearningブームではありますが、第二次世界大戦以前からAIというものは研究されており、その歴史をたどること、言い換えると初歩的なAIを手探りでつくることに萌える方は私だけではないでしょう。

今回は、あえて戦前から楽しまれているようなマイナーボードゲームのAIを開発し、先人の足跡を辿ってみようと思います。

プレイするゲーム

概要

今回は Shut The Box というゲームをプレイしようと思います。

シャット・ザ・ボックスはダイスを使った伝統的なパブゲームで、遅くとも19世紀の北フランス・ノルマンディー地方や、フランスに近くフランス文化の色濃い英国領のチャネル諸島に存在しており、船員や漁師などの間で盛んに遊ばれておりました。
イギリスには20世紀の中頃に存在した記録が残っており、北フランスよりチャネル諸島を経由して伝わったとされています。東南アジアの国でもよくみかけられ、タイのパブなどではメジャーなゲームとして存在しております。(出所：http://sekaiyugi.com/games/shutthebox-1.html)

↑弊社オフィスになぜかあるやつ

こんな外観をしていて、ギャンブル性がありつつも頭をつかう、いわゆる「不完全情報ゲーム」の一種です。
囲碁がAlphaGoに破られたあたりから、AIは完全情報ゲームでほぼほぼ人類を蹂躙できるようになったと言っても過言ではないでしょう。そのなかAI開発者の興味は、より実世界に近い、現在不完全情報ゲームに移っており、不完全情報ゲームの研究はエッジな領域と認識しています。
たとえばポーカーの特殊シチュエーションについてのAIはすでに人間のプロを破っており、今後一般的シチュエーションについてもハイレベルなAIが開発されるでしょう。麻雀についても同様に「爆打」というAIがほとんどの人間よりも強くなっています。
なぜ人間はポーカーでAIに負けたのか？　日本トッププロが解説する“違和感” (1/2) - ITmedia PC USER
「もう自分では勝てません」 28歳の東大院生が最強の麻雀AIを作るまで (1/3) - ITmedia NEWS

そのなか、このゲームは適度に難易度が低く、またAIが作られたことのない手頃な未踏領域な気がします。

ルール

じつはいくつか変種のルールがあるのですが、今回は下記を採用します。
(Shut the Box（シャット・ザ・ボックス）を参考に筆者編)

目的

より多くのタイルを閉じて、失点を少なくすること。

手番

まず全てのタイルを開きます。
そして、サイコロ２個を振り、その目の合計に等しくなるようなパターンでタイルを閉じます（例えば２と４の目が出たならば、「１と２と３」「１と５」「２と４」「６」のいずれかのパターンでタイルを閉じます）。
タイルを閉じることができなくなるまでサイコロ２個を振り続けます（残っているタイルの合計が６以下の場合は１個で振っても構いません）。
全てのタイルを閉じるかいずれのタイルも閉じることができなくなったら手番終了です。残ったタイルが失点になります（例えば、１と５と８のタイルが残ったとすると158点が失点になります）。全てのタイルを閉じた場合は即座に勝利となります。

失点計算保補足

タイルが[10]まである場合、タイルを倒すときは数値10として扱い、失点を読むときは数字０として扱います。例えば[2][4][7][10]が残ったならマイナス2470点です。

ゲームモデリング

大枠

さて、いかんせんマイナーゲームなのでまずはゲームをモデリングしなければいけません。
基本的な構造としては、下記のような感じでplayerを生成して終了条件を満たすまでゲームをさせ続ける構造がよさそうです。
各プレイヤーがゲーム終了したら、スコアを計算して結果を発表します。

main.py

def play():
    player1 = Player('Human')
    player2 = AIPlayer('AI')
    is_continued_1p = True
    is_continued_2p = True
    while is_continued_1p or is_continued_2p:
        if is_continued_1p:
            result = player1.roll_dice()
            is_continued_1p = player1.shut_the_box(result)
        else: pass
        if is_continued_2p:
            result = player2.roll_dice()
            is_continued_2p = player2.shut_the_box(result)
        else: pass
    winner, score_of_winner, score_of_loser = calc_result(player1, player2)
    print("Winner is", winner, ":", score_of_winner, "-", score_of_loser)

if __name__ == '__main__':
    play()

roll_dice()

2個のダイスを振ります。ただし1個のダイスにできるとき、すなわちself.remain_boxes > 6のときは1つのダイスにもできるようにしてあげます

    def roll_dice(self):
        print(self.name, 'rolls dice')
        one_dice_bool = (self.remain_boxes > 6)
        can_i_use_one_dice = (one_dice_bool.sum() == 0)
        decision = 'N' # 基本は2ダイス
        # 1ダイスにできるときに、そうするか聞く
        if can_i_use_one_dice:
            decision = self.make_decision_about_dice()
        else:
            pass
        
        if decision == 'Y' or decision == 'y':
            dice1 = random.randrange(1, 7)
            print('□◇□◇…', dice1)
            return dice1
        else:
            dice1 = random.randrange(1, 7)
            dice2 = random.randrange(1, 7)
            result = dice1 + dice2
            print('□◇□◇…', dice1, '+',dice2, '=', result)
            return result

shut_the_box()

残っているBOXと、出たダイスの目をもとに、

• どんな組み合わせでBOXを倒せるか
• もしくはゲームオーバーか
  を判定してあげます

    def shut_the_box(self, result):
        combination = self.get_valid_combination(result)
        remain_boxes_list = self.remain_boxes.values.tolist()
        print('Remained boxes:')
        print(remain_boxes_list)
        print('Options:')
        for i, c in enumerate(combination):
            print(i, [i for i in c if i != 0])
        if len(combination) > 0:
            decision = self.make_decision_about_shutting(combination)
            option = [i for i in combination[int(decision)] if i != 0]
            remaining = set(remain_boxes_list) ^ set(option)
            remaining_list = list(remaining) #念のためソート
            self.remain_boxes = pd.Series(remaining_list).sort_values()
            print('-'*30)
            return True
        else:
            print('Game Over')
            self.score = self.calc_score()
            print('Score:', self.score)
            print('*' * 30)
            return False

モデルとしてはだいたいこんな感じです。

超簡単なAI

対戦できないとつまらないので、一旦超簡単なAIを作っておきましょう。
Playerを継承しつつ意思決定の部分をoverrideしてあげます。
AIを高度化するときはこのoverrideした2メソッドを拡張する感じになりそうです。
また、AIの「鍛錬」においてはAIPlayer同士を戦わせることも想定しています。

class AIPlayer(Player):
    def __init__(self, name):
        super().__init__(name)

    def make_decision_about_dice(self):
        flag = random.randrange(0, 1)
        if flag == 0:
            print('I use TWO dice')
            decision = 'N'
        else:
            print('I use ONE dice')
            decision = 'Y'
        return decision

    def make_decision_about_shutting(self, combination):
        if len(combination) > 1:
            decision = random.randrange(0, len(combination)-1)
        else:
            decision = 0
        print('I choose #', decision)
        return decision

これで完成です。

遊んでわくわく

こんな感じでどの組み合わせで倒すか聞かれます

AIも同様ですが、現状のAIはランダムに行動します

なのでAIはちょっと弱いです。
倒せるBOXがなくなると、下記の通りScoreが表示されます

僕も死にました、最後にスコア同士が比較され、どちらが勝者か判定されます

つぎどうしよっか

一般的で、AlphaGoでも応用されている、モンテカルロ木探索法とか試そうと思います。
フルスクラッチで書くつもりですが、高速に書けるかが不安…