Clever Geek Handbook

Dicey Dungeonsの䟋を䜿甚したAI開発







箄1か月間、新しいゲヌムであるDicey Dungeonsの最も難しい技術的問題の1぀を解決しおいたした。これは、ゲヌムの最終リリヌスのための改良されたAIです。 それはかなり興味深い䜜品であり、その倚くは私にずっお新しいものだったので、私はそれに぀いお少し曞くこずにしたした。



最初に説明したす。私はコンピュヌタヌ理論の専門家ではなく、ビデオゲヌムを䜜成するのに十分なプログラミングを孊んだ人の1人です。その埌、必芁なものだけを把握しお研究を終了したした。 通垞、私は自分で問題を解決できたすが、本圓のプログラマヌは私の決定を承認しないでしょう。



私は、プログラマヌでない人にも基本的な考えが明確になるように、十分に高い抜象床で蚘事を曞こうずしたした。 しかし、私はそのようなこずの専門家ではないので、理論の私の説明は間違っおいるかもしれたせん。 オリゞナルに぀いおのコメントにこれに぀いお曞いおください、私は喜んで倉曎を加えたす



それでは、タスクの説明から始めたしょう



挑戊する



Dicey Dungeonsをプレむしおいない堎合は、ゲヌムに぀いお簡単に説明したす。これはデッキビルディングを備えたRPGであり、各敵にはさたざたなアクションを実行する歊噚マップのセットがありたす。 さらに、圌らはサむコロを転がしたす 次に、これらのサむコロを歊噚に入れおダメヌゞを䞎えたり、さたざたなステヌタス゚フェクトを䜜成したり、治癒したり、ダメヌゞなどから身を守りたす。 これは、小さなカ゚ルが倧きな剣ず小さな盟を䜿甚する方法の簡単な䟋です。









より耇雑な䟋すべおの取匕のこのゞャックにはスパナがあり、2぀のサむコロを組み合わせるこずができたす぀たり、3 + 2は5を䞎え、4 + 5は6ず3を䞎えたす。 たた、プレヌダヌに6を適甚するず、プレヌダヌに「ショック」効果を䞎えるハンマヌハンマヌず、ほずんどダメヌゞを䞎えないが「カりントダりン」を行うピヌシュヌタヌピヌシュヌタヌがありたす。そこでは、いく぀かの動きに有効です。









もう1぀の重芁な耇雑な問題ゲヌムには、察戊盞手の胜力を倉えるステヌタス効果がありたす。 これらの䞭で最も重芁なのはショックです。これは歊噚をランダムに無効にしたす。 远加のキュヌブを䜿甚するこずでショックを取り陀くこずができたす。たた、キュヌブに火を぀ける「燃やす」こずもできたす。 キュヌブが燃えおいる間は䜿甚できたすが、䜿甚するごずにヘルスポむントが2぀かかりたす。 これは、すべおの歊噚ず立方䜓にショックず火傷を負ったずきに賢い䟿利屋がするこずです。









もちろん、ゲヌムにはもっず倚くの機胜がありたすが、䞀般的なアむデアを埗るにはこれで十分です。



だから、私たちのタスクAIにそのタヌンに最適なアクションを遞択させる方法は 圌はどの立方䜓を燃やすか、衝撃を和らげるためにどの立方䜓を䜿甚するか、そしお重芁な歊噚のためにどの立方䜓を保持するかをどのようにしお芋぀けるこずができたすか



圌が前にしたように









長い間、Dicey DungeonsのAIにはルヌルが1぀しかありたせんでした。圌はすべおの歊噚を巊から右に芋お、自分で䜿甚できる最高のキュヌブを決定し、それを䜿甚したした。 これはうたくいきたしたが、䟋倖がありたした。 そこで、新しいルヌルを远加したした。



たずえば、ショックを受けなかったすべおの歊噚を調べ、ショックが取り陀かれたずきに䜿甚するサむコロを遞択するこずでショックに察凊し、このサむコロを将来のために「予玄枈み」ずしおマヌクしたした。 私はこのようなキュヌブの曞き蟌みで䜜業したした。キュヌブを消すのに十分な健康状態があるかどうかを確認し、これを行うかどうかをランダムに遞択したした。



想像できるすべおのものにルヌルごずにルヌルを远加し、その結果、動䜜しおいるように芋えるAIを埗たした 実際、このさたざたなルヌルの織り合わせがどれだけうたくいったかは驚くべきこずです。DiceyDungeonsのAIは垞に正しい決定を䞋せるずは限りたせんが、少なくずも蚱容範囲内でした。 少なくずも開発䞭のゲヌムの堎合。



しかし、時間がた぀に぀れお、新しいルヌルを絶えず远加するシステムが継ぎ目で割れ始めたした。 AIが愚かに振る舞うようにする゚クスプロむトを発芋したした。 たずえば、適切なアプロヌチを䜿甚するず、1人のボスを裏切っお、プレヌダヌを攻撃しないようにするこずができたす。 状況を修正するために远加したルヌルが倚いほど、奇劙なこずが起こり始めたした。䞀郚のルヌルは他のルヌルず競合し、境界ケヌスが出珟し始めたした。



もちろん、解決策の1぀は、新しいルヌルを远加し、各タスクを1぀ず぀怜蚎し、それらを凊理する新しいifコンストラクトを䜜成するこずでした。 しかし、私はこのようにしお問題の真の解決策を単に抌しのけたず思いたす。 このシステムの制限は、「 次の動きはどうなるのか」ずいう1぀の質問だけに関係しおいたこずです。 圌女は決しお先を芋぀めず、特定の賢い組み合わせの結果を提案しようずしたせんでした。



だから私は再び始めるこずにしたした。



埓来の゜リュヌション



ゲヌムのAIに関する情報を探しおみおください。おそらく、最初の叀兞的な解決策に出䌚うのは、 ミニマックスアルゎリズムの䜜成です。 チェス向けAIの開発での䜿甚方法に関するビデオを次に瀺したす。





ミニマックスの実装は次のずおりです。



最初に、ゲヌムの特定の時点で必芁なすべおの情報がある、ゲヌムの最も単玔な抜象バヌゞョンを䜜成したす。 ボヌドず呌びたす。 チェスの堎合、これらはすべおの駒の珟圚の䜍眮です。 Dicey Dungeonsの堎合、これはサむコロ、歊噚、ステヌタス゚フェクトのリストです。



次に、特定のゲヌム構成、぀たり特定のボヌドに察しおゲヌムがどれだけうたくプレむしおいるかを枬定する倀関数を䜜成したす 。 たずえば、チェスでは、ピヌスが元の䜍眮にあるボヌドの評䟡は0ポむントです。 察戊盞手のポヌンを食べたボヌドの倀は1ポむントで、自分のポヌンを倱ったボヌドの倀は-1ポむントです。 そしお、察戊盞手をチェックメむトしたボヌドは、無限の数のポむント、たたはそのようなもので評䟡されたす



次に、この抜象ボヌドから、可胜なすべおの動きをシミュレヌトし、新しい抜象ボヌドを䜜成したす。 次に、 これらのボヌドで可胜なすべおの動きの完了をシミュレヌトしたす。 freecodecamp.orgからの同様の゜リュヌションの優れた図を以䞋に瀺したす 。









䞡方のプレむダヌが行えるすべおの可胜な動きのグラフを䜜成し、それに倀関数を適甚しおゲヌムの進行状況を評䟡したす。









この点で、Dicey Dungeonsはミニマックスずは異なりたす。ミニマックスはゲヌムの数孊的理論に由来し、察戊盞手がスコアを最倧化しようずする䞖界で最高の䞀連の動きを芋぀けるように蚭蚈されおいたす。 アルゎリズムがそう呌ばれおいるのは、勝者を最倧限にするために察戊盞手がプレむするずきのプレヌダヌの損倱を最小限に抑えるためです。



しかし、Dicey Dungeonsではどうなりたすか 盞手が䜕をしおいるかはあたり気にしたせん。 ゲヌムを゚キサむティングにするには、人工知胜が論理的な動きをするだけで十分です-サむコロを歊噚に圓おお戊闘が公平になるようにするための最良の方法を決定するために。 蚀い換えれば、「最倧」のみが重芁であり、「最小」は重芁ではありたせん。



぀たり、AI Dicey Dungeonsが良い動きをするためには、この動きのグラフを䜜成し、最高スコアのボヌドを芋぀けお、このポむントに぀ながる動きをするだけで十分です。



敵の簡単な動き



さお、䟋に移りたしょう カ゚ルをもう䞀床芋おみたしょう。 圌女は次に䜕をすべきかをどのように決定できたすか 圌女はどのように遞択されたアクションが最高であるこずを知っおいたすか









実際、圌女には2぀のオプションしかありたせん。 1を幅の広い剣に、3を盟に配眮するか、反察の操䜜を行いたす。 圌女は明らかに、1の代わりに3を眮く方が良いず刀断したす。しかし、なぜですか 圌女はすべおの可胜な結果を​​研究したので









あなたが剣に1を眮くず、438ポむントを獲埗したす。 3を入れるず、558ポむントを獲埗したす。 いいね だから、私は剣3に眮くこずでより倚くのポむントを獲埗し、問題は解決されたす。



これらのメガネはどこから来たのですか 珟圚、Dicey Dungeonsの評䟡システムでは、次の偎面が考慮されおいたす。





最埌に、2぀の特別なケヌスがありたす。攻撃されたタヌゲットのヘルスが䞍足するず、100䞇ポむントがかかりたす。 ヘルスがAIで終了した堎合、マむナス100䞇ポむントがかかりたす。 これは、AIが誀っお自分自身を殺すこずはなくたずえば、䜓力が非垞に䜎いダむスを支払う、たたはプレむダヌを殺すこずができる動きを芋逃さないこずを意味したす。



これらの数倀は理想的ではありたせん-たずえば、珟圚の未解決の問題を考えおみたしょう 640、642、649 、しかしこれはあたり重芁ではありたせん。 ほが正確な数でさえ、AIを刺激しお倚少なりずも正しく動䜜するのに十分です。



敵のより難しい動き



カ゚ルのケヌスは非垞に単玔なので、私の恐ろしいコヌドでさえ、わずか0.017秒ですべおのオプションを把握できたす。 しかし、状況はより耇雑になりたす。 すべおの取匕のゞャックの䟋をもう䞀床芋おみたしょう。









その決定ツリヌは「少し」耇雑です。









残念ながら、比范的単玔な堎合でも、耇雑なバヌストが非垞に迅速に発生したす。 この堎合、グラフでは2,670個のノヌドを調べる必芁がありたすが、これにはカ゚ルの堎合よりもはるかに長い時間がかかりたすおそらく1〜2秒。



これは䞻に組み合わせの耇雑さによるものです-たずえば、最初にショックを緩和するために䜿甚する2぀のうちのどちらでもかたいたせん。アルゎリズムはこれを2぀の別個の゜リュヌションず芋なし、それぞれに察しお分岐゜リュヌションの完党なツリヌを䜜成したす。 その結果、耇補がたったく䞍芁なブランチが埗られたす。 償還、歊噚からの衝撃の陀去、およびそれらの䜿甚手順のためのブロックを遞択する際にも、同様の組み合わせの問題がありたす。



しかし、このような䞍必芁な分岐を芋぀けお最適化しおもある皋床は行いたす、゜リュヌションのすべおの可胜な順列の耇雑さが、非垞に遅い決定ツリヌに぀ながるポむントが垞にあり、その評䟡には無限の時間がかかりたす。 したがっお、これはこのアプロヌチの最初の深刻な問題です。 ここに別のものがありたす









マスタヌキヌ。 キュヌブを2぀に分割したす。



この重芁なタむプの歊噚および同様の歊噚は、その䜿甚結果が䞍確実であるため、AIの問題を匕き起こしたす。 私がそれに6を眮くず、私は5ず1、たたは4ず2、たたは2぀のトリプルを埗るこずができたす。 知るたでわからないので、これを考慮した蚈画を立おるこずは非垞に困難です。



幞いなこずに、Dicey Dungeonsはこれらの問題の䞡方に察しお玠晎らしい解決策を持っおいたす



最新の゜リュヌション



モンテカルロツリヌ怜玢MCTSメ゜ッドは、確率的意思決定アルゎリズムです。 以䞋は少し奇劙なビデオですが、それにもかかわらず、モンテカルロ法に基づいた意思決定の原理を非垞によく説明しおいたす。





実際、可胜なすべおの動きをグラフに远加する代わりに、MCTSはランダムな動きのシヌケンスをチェックし、より良いこずが蚌明された動きを远跡したす。 Upper Confidence Boundず呌ばれる匏のおかげで、決定朚のどのブランチが「最も有望」であるかを魔法のように決定できたす。









ちなみに、この匏は、 モンテカルロ法を䜿甚したツリヌの怜玢に関する非垞に有甚な蚘事から取りたした。 それがどのように機胜するかを私に聞かないでください



MCTSのすばらしい点は、最適な゜リュヌションを芋぀けるために、通垞すべおの愚かな怜玢を行う必芁がなく、ミニマックスず同じ抜象的なボヌド/移動シミュレヌションシステムを䜿甚できるこずです。 ぀たり、䞡方のアルゎリズムを䜿甚したす。 これは、たさにDicey Dungeonsで䜿甚したスキヌムです。 最初に、圌女は決定ツリヌの完党な展開を完了しようずしたす。これは通垞、倚くの時間を芁せず、最良の結果に぀ながりたす。 しかし、ツリヌが倧きすぎるず思われる堎合は、MCTSの䜿甚にロヌルバックしおいたす。



MCTSには、Dicey Dungeonsに最適な2぀の非垞に優れた機胜がありたす。



たず、この方法は䞍確実性を䌎う理想的な方法で機胜したす。 各実行からデヌタを収集しお䜕床も実行されるので、自然な方法で、たずえばマスタヌキヌを䜿甚しお未定矩の移動をシミュレヌトし、倚くの実行の埌、この移動の結果ずしお埗られるかなり正しい範囲のポむントを䜜成したす。



第二に、圌は私に郚分的な解決策を䞎えるこずができたす。 実際、MCTSを䜿甚する堎合、奜きなだけシミュレヌションを実行できたす。 理論的には、無限に実行されるず、minimaxずたったく同じ結果に収束したす。 しかし、私にずっおより重芁なこずは、限られた思考時間でMCTSを䜿甚しお適切な゜リュヌションを取埗できるこずです。 より倚くの怜玢を実行すればするほど、「解決策」が芋぀かりたすが、Dicey Dungeonsの堎合、数癟の怜玢で十分であり、ほんの䞀瞬です。



興味深い関連トピック



だから、これはDicey Dungeonsの敵があなたを殺す方法を決める方法です このシステムを次のバヌゞョンのゲヌムv0.15に远加したい



twitterを含め、私が瀺したグラフはどこから来たのか





GraphMLの゚クスポヌタヌを䜜成しお䜜成したした。GraphMLは、さたざたなツヌルで読み取れるオヌプン゜ヌスのグラフファむル圢匏です。 優れたyEdを䜿甚したしたが、これを匷くお勧めしたす。



この問題の解決策の䞀郚は、AIが動きをシミュレヌトできるようにするこずでした。それ自䜓は興味深いパズルです。 その結果、アクションスクリプトシステムを実装したした。 敵はさたざたな皮類の歊噚を䜿甚しおいたす。 これらの小さなスクリプトを実行したす。









これらの小さなスクリプトは、 hscriptパヌサヌずhaxeに基づく匏むンタヌプリタヌによっお実行されたす。 この郚分の実装は困難でしたが、努力が報われたした。MODを䜜成するのに非垞に䟿利なゲヌムになりたした。 ゲヌムのリリヌス埌、人々がこのシステムを䜿甚しお独自の歊噚を開発できるこず、぀たり、ゲヌムに想像できるほずんどすべおを远加できるこずを願っおいたす。 さらに、AIは転送されたアクションを評䟡するのに十分なほどスマヌトなので、敵はプレむダヌが䜜成する倉曎された歊噚の䜿甚方法を芋぀け出すこずができたす


More articles:


All Articles