【疑問】将棋や囲碁のAIはどうやって手を選んでるん？Mini-Max法・αβ法・モンテカルロ法の違い【G検定】

ゲームのAIって、全部の手を読んでるん？
Mini-Max法・αβ法・モンテカルロ法が出てきて、どれが何をするのか分からん

前提のおさらい。探索は、選べる手を枝分かれさせた探索木をたどってゴールを探すこと
ゲームでは自分の手と相手の手が交互に来る木（ゲーム木）になる

＞＞1
全部読めるゲームは少ない。だから、何手か先までの局面に点数（評価値）をつけて、そこから手を選ぶ
Mini-Max法は「自分は評価値が最大になる手、相手は最小になる手を選ぶ」と考えて、下から値を決めていく

＞＞3
具体例で頼む

＞＞4
自分の手が A と B の2つ。それぞれに相手の返し手が2つあって、その先の評価値が
A のあと：3、5
B のあと：2、9
相手は小さいほうを選ぶから、A は3、B は2

だから自分は A を選ぶ。B の9は、相手が選ばせてくれない

＞＞5
αβ法はそれを速くするもの？

＞＞6
そう。調べなくても結果が変わらない枝を省く（枝刈りする）
さっきの例で、A を調べて「最低でも3は取れる」と分かった。B の1つめを見たら2
相手は B のあと2以下を選べるから、B は3より小さいと確定する。B の残りの枝（9）は見なくていい

＞＞7
α と β は何の記号？

＞＞8
α は自分（最大を選ぶ側）が少なくとも取れる値、β は相手（最小を選ぶ側）が抑えられる値

になった枝は、それ以上調べても選ばれないので切る
答えは Mini-Max法と同じで、調べる局面が減るだけ

＞＞9
でも囲碁はそれでも無理って聞いた

＞＞10
囲碁は1手ごとに選べる手が多くて、よく言われる目安はチェスが35くらい、囲碁が250くらい
しかも盤面の良し悪しを点数にする評価関数が作りにくい

＞＞11
そこで出てきたのがモンテカルロ法
ある局面から、最後までランダムに打ち合う（プレイアウト）のを何度もくり返して、勝った割合でその手の良さを見積もる
100回のプレイアウトで62回勝ったら

＞＞12
評価関数を人が作らなくても、勝ち負けの数だけで比べられるのがポイントやな

チェスのほうは、力まかせに大量の局面を調べるブルートフォースでも強くなった
IBM のディープ・ブルーが世界チャンピオンのカスパロフに勝ったのが1997年。専用のハードウェアで大量の局面を読んだ

＞＞14
まとめると、Mini-Max法が基本の考え方、αβ法はその枝刈り、モンテカルロ法は評価関数のかわりにランダムな打ち合いの勝率を使う。ブルートフォースは計算量で押し切るやり方、と