モンテカルロ・ゲーム「樹」探索

https://ja.wikipedia.org/wiki/%E3%82%B2%E3%83%BC%E3%83%A0%E6%9C%A8

ゲームの探索には ゲーム木 に使用が必要不可欠になります。早い話が、探索の経路を図表化しただけのことです。

お約束として、良い手を左から並べます。よって上から最左ノードを辿っていくのが最良手順になります。

よってモンテカルロ・ゲーム木探索は…ゲーム木を上から降りてゆき、末端に到達したら

1.ノードを展開(枝を伸ばす)
2.(1)で展開したノードの中から選んでプレイアウト
3.結果を上層に返す

…とアルゴリズムは至極簡単ですう。

と、ここまで書いて…決断タイムです。

>3.結果を上層に返す

ここで 「何」を上層に返す か??? 実験・検証が必要ですにゃ。

~~~~~~~~~~~~~~~~~

http://www.yisongyue.com/courses/cs159/lectures/MCTS.pdf

まあ、ミニマックスにしてしまおう…と考えましたが、ここは教科書通りに進めてみます。

投稿者: webMaster 投稿日時: 土, 03/24/2018 - 13:47 categories [ ]

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。

枝は伸ばして伸ばしまくるのだ

静的探索はしないので 駒の取り合い になった局面に難ありですな。王手が掛かる局面も然りです。

ここはドンドン探索枝を伸ばして落ち着いたらプレイアウトです。

より平等なランダムを要求する

…は意外と難なく実装できました。

副作用として合法手を一気に生成しなくなったので探索数も予想以上にUP…そいつは~良かった。

NPSと仁義なき戦い

探索アルゴリズムはどの程度 NPS(Nodes Per Second = 毎秒ノード数) 出してなんぼの世界です。

ラップトップでの計測ですが、毎秒2万シミュレーション以上出るようになりました。

次はプレイアウトの偏りを直すだべ。

ランダムな拷問

モーニン

顧みると、全数探索が、コンピューターの方法で、それがCPUの能力向上で、電力を掛ければ名人にも勝てるようになった。(といっても未だ実演会は行われていない?)

その先には二つ科学的問題が有りえて、一つは

●電力を掛けて、必要なら世界で「一番」(一番でなければダメかどうかは知らぬ。)のスパコンを使い、先手必勝法(有るとすれば多分こっち)マタは後手不敗法(同左)を発見する。

[もしかしたら先手必勝法に関しては後手(先手もそうするのがフェアだがその方が困難。)千日手は負けと決める必要が有る。チェスでは史上最強の一人に数えられた某(失名)が、白(先手)であれば絶対に負けない(引き分けは否定していない。)と豪語した。もしかしたら将棋序盤研究で、無論終盤まで指してはいないが、こういったルールでプロ同士なら諦めるというようなものが、既に提案されていたのだったか?]

もう一つは

●機材・電力・時間(=コスト)を著しく制限して、コンピューターと人間の能力(=パフォーマンス)を比較する。

これが正確に分かると、名人やプロ棋士達の頭脳が人工物のコストで数値的に評価できることなどいろいろ面白い。

ランダムに着眼するのは、全数探索よりも大幅にコストを削減できる可能性が有るからですね。

[昔四色問題(1975コンピュータで「証明」、最終的に信用を得たのは2004)やフェルマーの定理(1994-95証明発表・確認)が解ける前、ランダム・シミュレーション、つまりモンテカルロ法でこれらの予想が正しい確率を計算したと主張した人が居た。数学的に解けない問題は、正しい確率が十分に高ければ、それで済ませれば良いという数学観延いては人生観が有りえた。その背景にはゲーデルの不完全性定理も有るわけだが。(斯く申す愚は、大谷山が適当に演習に出した問題が解けすに教室で立ち往生した時に助けて上げたり、大志村のゼミナールで少なくとも当時の所属者では一番できた者で御座るよ。今思うとつくづくと恵まれた学生時代だったなー。)]

>拷問

金正恩の中国訪問に絡み、昔の列車の所要時間が拷問同然だったとか、いろいろ話になる。

愚も旅行社のミスでパリに行くのに「南回り」に乗せられたことが有り、羽田を出てなんとなく不思議に思って居たらマニラの熱暑の空港に着いて仰天したことが有る。

その後、バンコクと、ドバイ、アテネに止まった。時間(十時間以上余計に掛かったような。)と言い経由地の暑さと言い、ちょっとした拷問だった。

しかしその後間もなく「南回り」は廃止されたから、人生での体験・思い出としては、むしろラッキーだったやも知れぬ。ドバイの空港でアラブ商人から買った大きな銀杯(ジャーマンシルバー)は数年後に黒くなってしまったから、捨てたが。
         ____________

殆どランダムに犠牲者を選ぶ嫌がらせ・苛めは、今の日本では暴力団や学校でしか起こらないが(会社にもときにモンスター上司がいるという話も読まぬわけではない。)、中世諸国や旧ソ連などでは、通常に存在していたのではないかと思う。

旧ソ連では、権力誇示のためか、運航の不安定性「糊塗」†のためか、外国からの訪問者の飛行機搭乗(乗り継ぎ)を、入国後ランダムに拒絶していた。愚は数万円の二重払いと途中の一夜遅れを除けばさしたる被害に遭わなかったが、ノボシビルスクの学会に招かれたときは、一緒にアメリカから入国した同僚(英人)は、全く無意味に一夜モスコーに止められて開会式に遅れたし、イルクーツクでは或る米国人高校教師夫婦が、その先の旅行のためには莫大な金を払えと言われて(無論全部の旅費を前払いして居なければ入国できなかった時代だった。)、男の方が泣いて居て、私にもしナホトカで会えなければ東京の米大使館にこの紙片(救助要請)を渡してくれと頼まれた。
________

† やくみつる ➡『春日野』
http://www.tokinclub.com/dp/node/245#comment-47758
(と金TOKING 4/10)

節約は正義である

コードを見直して効率化したら2割位探索ノード数増えたみたいです。
もう一ヶ所あるので手を入れます。

ランダム と エセ・ランダム

…あらやだ… 災害とエセ・ランダムは忘れた頃にやって来る…です。

> 1.各候補手から_ランダム_にゲームを進め

…落とし穴がありましたとさ。

((間違ったやり方)) 合法手を生成し、その中から一つ_ランダム_に選ぶ

一見ランダムに見えますが、この選択方法は 大きく動ける駒 の方が候補手が多いので自然と選択される確率が高くなります。これでは駄目・ダメ・駄目ですね。

プレイアウト

…は、普通終局までやりますが、我は適当なところで打ち切っています。

はて…プレイアウトしないでそのまま評価値を返しても大差ないんじゃね?
…と思って比較したらプレイアウトした方が速くて結果も良いです。

納得できる説明が思いつきませんが、そ~ゆうものだとしておきます。

努力は嘘をつかないが、結果は別件であ~る P2

>1.隙間埋め

…は、終了。やはりランダム使用アルゴリズムは気分屋ですな。

詰めのある局面で見つけたり見逃したり…

努力は嘘をつかないが、結果は別件であ~る

なんとか信じられる探索結果が出るようになりました。

残るは…

1.隙間埋め
2.ゲームエンジンに組込む
3.テスト

話題はそれますが、それもよし

アトランター東京の往復航空券は普通$1,200程度ですね。(今年は貯めたマイルですが)

で、中国航空会社では時折超格安の$700前後で販売しますが…問題なのが時間ですね。
2回ストップで片道51時間!!…拷問の一種だとおもう。
まあ、中国の空港を見たいとか稀有な理由でもあれば別ですが。
フライト中のサービスは 値段相応 だそ~な。

ノンストップなら 行き12時間、帰り14時間 です。

コメントの表示オプション

お好みの表示方法を選択し、「設定の保存」をクリックすると、表示方法を変更することができます。