2019-11-26

ミニマックス法を学ぶっ！

現在、こちらの書籍で学習しております。

www.borndigital.co.jp

私はChap5-1のミニマックス法でつまづいてしまいました。
ここでは、つまづいた内容である3目並べをミニマックス法で解くAIプレイヤーの作成を目標にして、学習しながら更新していこうと思います。

ミニマックス法とは何ぞや？

人は、3目並べをするときは、何手か先を考えてから石を置くと思います。コンピューターの場合も、どこに石を置くか考える、「思考ルーチン」が必要になります。この１つが、今回の「ミニマックス法」です。また、ミニマックス法を効率化した「アルファベータ法」というのもあります。

ミニマックス法ってどんなアルゴリズム？

自分が行えるすべての行動に対して「もしここに石を置いたら、相手はこうして...」という先読みを行い、その行動を評価します。自分は自分にとって最善手を選び、相手は自分にとって最悪手を選ぶという仮定のもと、最善手を探すアルゴリズムです。

今回は3目並べなので、すべての行動に対して、ゲーム終了まで先読みをして評価します。将棋などの行動に対しての選択肢が多いものについては、 $x$ 手先まで読むなどして、現実的な計算時間で行います。

phtyonで作ろう！

作るもの

3目並べ（ゲームシステム）
プレイAI（ミニマックス）
実行コード

実行コード(仮)

先に、実行コードから考えていきます。
疑似コードになります。

# 3目並べをAI同士に対戦させる

1. 3目並べを用意する。
2. ゲーム終了まで、AI同士で戦う
    2-1. 先手または後手のAIが石を置く。(ループごとに交代)
    2-2. ゲーム終了か確かめる。
    2-3. 表示する。

この疑似コードを、それっぽく書いてみる。

# 3目並べの状態を保持するクラス"State"を初期化する。
state = State()
# ファーストプレイヤーの決定
player_a = random.randint(0,1)
player_b = !player_a

# ゲーム終了までループ。（Stateクラスのis_doneで確認）
while ( state.is_done() ) :
    if player_a:
        # AIの選択した行動を取得する。（現在の状態からミニマックス法で選択）
        action = mini_max_action( state )
    if player_b:
        # AIの選択した行動を取得する。
        action = mini_max_action( state )
    # 行動を状態に反映させる。
    state = state.update( action )

    # 表示
    print(state)
    print("空白")

   # playerの入れ替え
    player_a, player_b = player_b, player_a

ここから、今適当に名前を付けたパーツを定義していけばよいことが分かります。

プレイAI (仮)

さて、次はAIについて考えます。実行コード(仮)から、現在の状態からミニマックス法で選択する、mini_max_action( state )を作成すればよいことが分かりました。早速疑似コードを作ってみます。また、すでに石が置いてあるマスは選べません。ここでは、まだ石が置いていないマスを合法手と呼んでいます。Stateクラスで、合法手のリストを作る必要がありそうです。

# 現在の状態からミニマックス法で選択
def mini_max_action( state ):
    1. 合法手を取得する
    2. すべての合法手に対して、mini_max法で価値を計算する。
    3. 最も価値の高い行動を返す。

ここから、もう少し詳しく考えます。コードっぽく書けるところは、コードにしてしまいます。

# 現在の状態からミニマックス法で選択
def mini_max_action( state ):
    # 1. 合法手を取得する
    # 2. すべての合法手に対して、mini_max法で価値を計算する。
    for action in state.legal_actions():
        # 2-1. mini_max法で価値を取得
        score = mini_max( state )
        # 2-2. 価値が高いなら更新
        if score > best_score:
            best_action = action
            best_score  = score

    # 3. 最も価値の高い行動を返す。
    return best_action

best_scoreなど、変数の定義などもしていきます。行動は、マスの数字で返します。０～８の９通りです。もちろん、合法手も同様にマスの数字を返します。

# 現在の状態からミニマックス法で選択
def mini_max_action( state ):
    #0. 変数の定義（わかりやすさも含めて、scoreも定義しました。)
    score           = -float( 'inf' ) #  行動の価値。－無限大で初期化。
    best_score  = -float( 'inf' ) # 最も高い行動の価値。－無限大で初期化。
    best_action = 0                 # 最も価値の高い行動。マス0で初期化。

    # 1&2. 全ての合法手に対して、mini_max法で価値を計算する。
    for action in state.legal_actions():
        # 2-1. mini_max法で価値を取得
        score = mini_max( state.update( action ) )
        # 2-2. 価値が高いなら更新
        if score > best_score:
            best_action = action
            best_score  = score

    # 3. 最も価値の高い行動を返す。
    return best_action

整えます。

# 現在の状態からミニマックス法で行動を選択
def mini_max_action( state ):
    score           = -float( 'inf' ) #  行動の価値。
    best_score  = -float( 'inf' ) # 最も高い行動の価値。
    best_action = 0                 # 最も価値の高い行動。

    # 全ての合法手に対して、mini_max法で価値を計算。
    for action in state.legal_actions():
        # mini_max法で価値を取得
        score = mini_max( state.update( action ) )
        # 価値が高いなら更新
        if score > best_score:
            best_action = action
            best_score  = score

    # 最も価値の高い行動を返す。
    return best_action

さて、肝心のmini_max()がまだ定義されていません。コードが長くなってきたので、mini_max()のみの疑似コードを分けて作っていきます。ミニマックス法では、再帰的な処理を行います。今回はゲーム終了まで探索します。勝敗に価値をつけました。

# ミニマックス法である状態の価値を計算する。
def mini_max( state ):
    #1. もし勝利       なら+10を返す。
    #2. もし敗北       なら -10を返す。
    #3. もし引き分けなら    0を返す。

    #4. もし決着がついてないなら
        #4-1. 現在の状態からすべての合法手に対してmini_max( state.update( action ) ) 
                 を行います。
        #4-2.自分の番か相手の番かを確認し、
            #4-2-T. もし自分の番なら、価値の最大値を返す。
            #4-2-F. もし相手の番なら、価値の最小値を返す。

こんな感じでしょうか。書籍ではNegaMax法というアルゴリズムを使っています。今回は理解を深めるために、ひとまずミニマックス法をそのままコードにします。これを、もっと作りこみます。

# ミニマックス法である状態の価値を計算する。
def mini_max( state ):
    #1. もし勝利       なら+10を返す。
    if   state.is_win():
        return   10
    #2. もし敗北       なら -10を返す。
    elif state.is_lose():
        return -10
    #3. もし引き分けなら    0を返す。
    elif state.is_draw():
        return    0

    #4. もし決着がついてないなら
    else :
        #4-1. 現在の状態からすべての合法手に対してmini_max( state.update( action ) ) 
                 を行います。
        for action in state.legal_actions():
                score = mini_max( state.update( action ) )
            #4-2.自分の番か相手の番かを確認し、
                #4-2-T. もし自分の番なら、価値の最大値を返す。
                #4-2-F. もし相手の番なら、価値の最小値を返す。
                if state.is_first_player() :
                     if score > best_score:
                          best_or_worst_score = score
               else:
                     if score < best_score:
                         best_or_worst_score = score

         return best_or_worst_score

こんな感じでしょうか。

最後に、三目並べ自体を作成します。

三目並べ（ゲームシステム）

盤の状態や、今どちらの手番かや、ゲームの終了判定もここで作成します。

作る機能一覧

ゲームの石の配置状態の保持( __init__(self) )
ゲームの終了状態の確認( is_done() )
ゲームの勝敗状態の確認( is_win( self ), is_lose( self ), is_draw( self ) )
行動を入力して盤を更新する機能 (update( self, action ) )
合法手一覧の取得( legal_actions( self ) )
その状態の手番プレイヤーの取得( is_first_player( self ) )
~~先手後手のルーレット~~
表示を整える( __str__(self) )

# 三目並べの作成

# ゲームの状態
class State:
    # 初期化
    def __init__(self, my_pieces=None, enemy_pieces=None):
        # 石の配置(elseで0で初期化している。)
        self.my_pieces       = my_pieces       if my_pieces       != None else [0] * 9
        self.enemy_pieces = enemy_pieces if enemy_pieces != None else [0] * 9
    # 負けたかどうか
    def is_lose(self):
         処理
    
    #勝ったかどうか
    def is _win(self):
          処理
    #引分かどうか
    def is_draw(self):
         処理
    
    # ゲーム終了かどうか
    def is_done(self):
        処理
    
    # 次の状態
    def update( self, action ):
        処理
       return State( self.my_pieces, self.enemy_piece )

    # 合法手リストの取得
    def legal_actions( self ):
        処理
        return actions

    # 先手かどうか
    def is_first_player(self):
         処理
        return True|False

    # 文字列表示
    def __str__( self ):
        str = ''
        処理
       return str

これらをうまく合体させます。 githubに乗せます。

2019-08-18

Markdown備忘録

GitHubの書籍

最近、GitHubでつまづくことが多いです。
時間が持ってかれます。つらいです。ここは一度、GitHubの書籍を読んでおかないとまずいなと思ったので、kindleでこの書籍を購入しました。

www.amazon.co.jp

まだ第一章ですが、すでにいくつか気づかされております。
やっぱり、書籍として情報がまとまっていると飲み込みやすいですね。
GitHubのマスコットの名前が「octcat」だということが分って満足しています。

GFMって何？

GitHubでは、ユーザが文字入力するすべての機能にGitHub Flavored Markdown (GFM) という記法で記述できます。

Markdown記法の亜種でしょうか。下のサイトを見る感じだと、CとC++のような関係なのかな。通常のMarkdown記法にテーブルや打ち消し線のルールを加えたのがGFMという解釈でいいのかな。というか、テーブルは通常のMarkdown記法の一部だとばかり思ってました。はてなのMarkdownにもテーブルは実装されてますよね！

sugarnaoming.github.io

通常のMarkdown

そもそもMarkdownも怪しいので、ここはしっかりと備忘録を作っとかなあかんと思いやす。下の記事の、大事だなと思った部分だけ抜き出しておきます。

sugarnaoming.github.io

Markdownのそもそもの役目

もともとは手軽にプレーンテキスト形式で書かれたファイルからHTMLを生成するために作られたものです。

Markdownで補えない部分

Markdownのルールで使用できない部分については素直にHTMLタグを使用してください。
唯一、<div>、<table>、<pre>、<p>"などのブロックタグを使用するときにはルールがあります。
これらのタグで囲まれた前後は空行でなければなりません。更にこれらのタグは行頭に置かなければなりません。タグの前にスーペスやタブを記述しないでください。

※< は<、>は>と書くことも知れたので、今回の収穫は大きい（笑）

コードを乗せる

コードブロックの開始に続いて言語名を記述することで、記述した言語に対応したシンタックスハイライトを使うことができます。 Github上でハイライトすることができる言語は以下のページに示されています。

打ち消し線

文字列を"~~"で囲むことで打ち消し線をつけることができます。

hoge~~bar~~

hoge~~bar~~

タスクリスト

-（ハイフン）に続いて角括弧をつけることでチェックボックスを表示することができます。角括弧の中には半角スペースを入れてください。また、角括弧の中にx（半角）を入れることでデフォルトでチェックを入れることができます。

- [x] hogehogehgoe
- [ ] foofoo

[x] hogehogehgoe
[ ] foofoo

※ ↑はてなだと出来ない模様

今回はこれで以上です。

2019-08-05

STATIONWORKを使ってみた

雑記

こんにちは、Kenaです。東京駅に突如、ヱヴァっぽい箱が出現しました。名前はSTATIONWORK。今回、試しに利用して来たので、ここに感想を書きます。 f:id:Kena:20190805183140j:plain

STATIONWORKって何？

https://www.stationwork.jp/user/top-before

どうだった？

wifi完備だった。
空調が足元にある。威力は真夏でも申し分ないと感じた。
hdmiケーブルが垂れているサブモニターがある。その裏には、申し訳程度に冷却設備もついていた。これいる？？？
机、椅子は必要十分。
特に登録しないでsuicaで入場したが、時間内なら再入場可能だった。
退出5分前になると結構大きめのアナウンスが。いきなりなるのでびっくりする。
時間を過ぎるとアナウンスが定期的にはいる。蛍の光は流れないもよう。
時間が過ぎても、突然扉が空くこともなかった。
退出時に照明は自動で消えない。出る前は手動で切ること。
防音はバッチリ！中で少し大きめに音楽ながしても漏れない模様。
隣のボックスの物音などは特に聞こえなかった。
利用終了時刻の五分後から次の人が使える。
外にサポートのおじさん二人が心配そうに待機していた。頑張れ！
閉じ込められた時の為の緊急脱出ボタンみたいのがついていて、ずっと押したい気持ちをこらえていた。
金額
15分あたり250円だが、今は絶賛キャンペーン中で150円です。気になるならいまだと思うぞ。
まとめ
安心安全の個室空間が駅ナカで得られる！ありがとうJR。引きこもり遺伝子が喜んでいるぜ！
設備は必要十分。くつろぐのは難しいだろう。資料作成などにはありあり。そういう用途にコミットしていると思われるので、サービスとしては上手くできていると思う。
一方で、退出時に電気がきれなかったり、中に居続ける人への対応が甘いなと、感じた。wifiも利用時間が過ぎても接続が切れなかった。ここら辺は今後改善されていくんじゃないかと思います。

Kenaのプログラム備忘録

今まで書いたソースコードをどうにもできていないので、せめてもの供養でここに挙げていきます。「新・解きながら学ぶC言語」を中心に書いていきます。