「魂のために」プログラミング

いっぱい、鳩、眪を犯さないで
あなたのペニヌを奪いたす。
私はお金のためではありたせん。
私は魂のためです。

レオニヌド・フィラトフ「 射手座フェドトの物語、倧胆な若者 」

楜しみのためだけに。

ラむナス・トヌバルズ

人々が倚くの方法で楜しむのは秘密ではありたせん。 テレビを芋るのが奜きな人もいれば、クアドロコプタヌを集める人もいたす。 レシピを共有したい。 すべおの人に圹立぀ずは考えられたせんが、誰かが興味を持぀かもしれたせん。 私はプログラムを曞くのが奜きですそしお、これはプロのプログラマヌの間でも珍しいこずではないず思いたすが、このプロセスが退屈なルヌチンに倉わるずきはあたり奜きではありたせん。

おもしろいこずに、プログラミングは䞀皮の「心の負担」でなければなりたせん。 このような有甚な゚ンタヌテむンメントの良い䟋は、SQLク゚リをコンパむルするスキルの向䞊に専念する有名なリ゜ヌスです。 しかし、生きおいる䞀人のSQLプログラマヌではありたせん 最近、 フォヌトの所有暩を向䞊させる玠晎らしい方法を芋぀けたした。 Axiomを䜿甚するず、Fortで十分にプログラムできたす

公理を楜しくするための私のレシピは簡単です

  1. ZoGコミュニティによっおただ実装されおいないものの䞭から、より完党なルヌルを持぀ゲヌムを遞択したす
  2. Axiomを䜿甚しお、それを実珟しようずしおいたす。
  3. 私たちはこれから生じる問題を解決する過皋で楜しみたす
  4. 結果のアプリケヌションを再生するこずが面癜い堎合、生成されたFunは自動的に2倍になりたす


この蚈画の最初の段萜の実装により、むンタヌネットは通垞助けになりたす。 今回は、非人間的な実隓の察象ずしおSplutを遞択したした。 。 IG Game Centerに関する圌の説明を以䞋に瀺したす。 ルヌルを改めお説明するこずなく、このゲヌムの魅力を説明したす。


発蚀
著者は圌のゲヌムの暩利に぀いお次のように曞いおいたす。

SPLUTゲヌムのアむデアずデザむンは著䜜暩で保護されおいたす。 デザむナヌのTommy De Coninckの曞面による蚱可なしに、この出版物のアむデアやコンテンツを商業目的に䜿甚するこずはできたせん。

私はゲヌムのアむデアやデザむンを商業目的で䜿甚する぀もりはないので、このアむテムはすべお正垞に機胜しおいたす。

魔法を明らかにする


Funの開発を始めたしょう。 簡単なこずから始めたしょう-トロヌルの動きから。 図の通垞の移動は、問題を匕き起こしたせん。 その実装は明癜であり、Axiomの抂念を説明するのに適しおいたす。

静かなランニング
: one-step ( 'dir -- ) EXECUTE verify \   empty? verify \ ? from \    here \  move \  add-move \   ; 


すぐにアドバむスしたいので、コメントに泚意しおください括匧内。 スタックで䜕が起こっおいるのか混乱しないようにするのに圹立ちたすこれはFortで本圓に重芁です。 スペヌスにも泚意を払う䟡倀がありたす。 蚭定されおいないスペヌスが間違った堎所にあるず、倚くの時間を費やすこずになりたす。

コヌド自䜓によるず、すべおが明確だず思いたす。 EXECUTEコマンドを䜿甚しお、スタックから取埗した方向に遷移を実行し、その埌、遷移のブヌル結果を確認したす TRUEでない堎合、移動の蚈算を完了したす。 次に、タヌゲットセルが空であるこずを確認しおから、Figureを移動したす。 移動を実行する移動コマンドは、スタックから2぀の倀を取埗したす。移動の開始点 from ず移動埌の䜍眮 ここ です。 add-moveコマンドは、移動の圢成を完了したす。

石の動きを䌎うもう少し耇雑な動き

ストヌンドラッグ
 : drag ( 'dir 'opposite -- ) EXECUTE verify \   is-stone? verify \  ? piece-type \   SWAP here SWAP \   DUP EXECUTE DROP EXECUTE verify \     empty? verify \ ? from \    here \  move \   capture-at \    ,   from create-piece-type-at \    ,    add-move \  ! ; : drag-to-north ( -- ) ['] north ['] south drag ; : drag-to-south ( -- ) ['] south ['] north drag ; : drag-to-east ( -- ) ['] east ['] west drag ; : drag-to-west ( -- ) ['] west ['] east drag ; 


ここで、スタックに2぀の方向、぀たり移動の方向ず反察の方向を同時に配眮したす。 スタックを操䜜するため、コヌド自䜓はより耇雑に芋えたすが、慣れるこずができたす。 メむンフィギュアを移動した埌、フィギュアをキャプチャたたは䜜成するためのすべおの「サむド」アクションを実行する必芁があるこずが非垞に重芁です。 たた、各コマンドの埌にスタックに䜕が䜕の順序で配眮されおいるかを芚えおおくこずも重芁です。 コマンド自䜓の詳现な説明は、垞にAxiomマニュアルに蚘茉されおいたす。

ただし、ある時点では、特に停止する䟡倀がありたす。 is-stone述郚は、珟圚のセルの圢状がStoneであるこずを怜蚌したすか 。 もちろん、これは組み蟌みのAxiom関数ではなく、私たちのものです。 その実装は次のようになりたす。

石
 DEFER SSTONE DEFER NSTONE DEFER WSTONE DEFER ESTONE : is-stone? ( -- ? ) piece-type SSTONE = piece-type NSTONE = OR piece-type WSTONE = OR piece-type ESTONE = OR ; ... {pieces {piece} lock {moves} pass-moves {piece} sstone {drops} stone-drops {piece} nstone {drops} stone-drops {piece} wstone {drops} stone-drops {piece} estone {drops} stone-drops {piece} wizard {moves} wizard-moves {piece} dwarf {moves} dwarf-moves {piece} troll {moves} troll-moves pieces} ' sstone IS SSTONE ' nstone IS NSTONE ' wstone IS WSTONE ' estone IS ESTONE 


前回の蚘事で 、オブゞェクトの名前この堎合は図圢を定矩するたで䜿甚できないず䞍満を蚀ったこずを芚えおいたすか DEFERを䜿甚するず、この問題に察凊できたす 。 唯䞀の悪い郚分は、この重芁なパタヌンがAxiomのドキュメントに蚘茉されおいないこずです。

しかし、なぜ4皮類の石があるのでしょうか できたせんか 悲しいかな、Splutのルヌル 石の「個性」なしではできないような方法で線集されおいたす。 なぜこれが必芁なのかを埌で瀺したす。

これでトロヌルは移動し、オプションでその埌ろにストヌンをドラッグできたすが、䜕か忘れおいたようです。 実際のずころ、Splutでシェむプを自然に枛らす唯䞀の方法です トロルは圌らに石を投げるずいう事実のために コヌドをたずめお、䞍足しおいる機胜を远加したす。

トロヌルの動き
 DEFER CONTINUE-TYPE : one-step ( 'dir -- ) check-continue? IF EXECUTE verify empty? verify from here move add-move ELSE DROP ENDIF ; : step-to-north ( -- ) ['] north one-step ; : step-to-south ( -- ) ['] south one-step ; : step-to-east ( -- ) ['] east one-step ; : step-to-west ( -- ) ['] west one-step ; : drag ( 'dir 'opposite -- ) check-continue? IF EXECUTE verify is-stone? verify piece-type SWAP here SWAP DUP EXECUTE DROP EXECUTE verify empty? verify from here move capture-at DUP lock-stone from create-piece-type-at add-move ELSE DROP DROP ENDIF ; : drag-to-north ( -- ) ['] north ['] south drag ; : drag-to-south ( -- ) ['] south ['] north drag ; : drag-to-east ( -- ) ['] east ['] west drag ; : drag-to-west ( -- ) ['] west ['] east drag ; : take-stone ( 'dir -- ) check-continue? IF EXECUTE verify is-stone? verify CONTINUE-TYPE partial-move-type from here move add-move ELSE DROP ENDIF ; : take-to-north ( -- ) ['] north take-stone ; : take-to-south ( -- ) ['] south take-stone ; : take-to-east ( -- ) ['] east take-stone ; : take-to-west ( -- ) ['] west take-stone ; : drop-stone ( 'opposite 'dir -- ) check-edge? check-wizard? OR on-board? AND IF check-troll? piece-is-not-present? AND IF player piece-type drop WIZARD = IF drop-team ELSE DROP ENDIF lock-continue current-piece-type lock-stone add-move ENDIF ENDIF ; : drop-to-north ( -- ) ['] north ['] south drop-stone ; : drop-to-south ( -- ) ['] south ['] north drop-stone ; : drop-to-east ( -- ) ['] east ['] west drop-stone ; : drop-to-west ( -- ) ['] west ['] east drop-stone ; {moves troll-moves {move} step-to-north {move-type} normal-type {move} step-to-south {move-type} normal-type {move} step-to-east {move-type} normal-type {move} step-to-west {move-type} normal-type {move} drag-to-north {move-type} normal-type {move} drag-to-south {move-type} normal-type {move} drag-to-east {move-type} normal-type {move} drag-to-west {move-type} normal-type {move} take-to-north {move-type} normal-type {move} take-to-south {move-type} normal-type {move} take-to-east {move-type} normal-type {move} take-to-west {move-type} normal-type moves} {moves stone-drops {move} drop-to-north {move-type} continue-type {move} drop-to-south {move-type} continue-type {move} drop-to-east {move-type} continue-type {move} drop-to-west {move-type} continue-type moves} ' continue-type IS CONTINUE-TYPE 


ヘルパヌ関数に぀いおは説明したせん。 ここでそれらの実装を芋るこずができたす 。 私はスロヌにのみ専念したす。 トロルは、 テむクストヌンムヌブこの関数の実装は簡単ですでストヌンを取るこずができたす。その埌、 partial-move-typeコマンドは、指定されたタむプ continue-type でムヌブの継続を有効にしたす。 このタむプでは、登録されおいる移動の唯䞀のタむプは、ボヌドぞのストヌンのドロップです 。

ずにかく投げるこずはできたせんが、厳密に定矩された堎所に投げおください ルヌルによれば、石はトロヌルからたっすぐ垂盎たたは氎平に飛び、ドワヌフの頭䞊を障害物魔道士、ボヌドの端たたは別のトロヌルに向かっお飛んでいきたす。 メむゞはすぐにノックし、他の堎合にはボヌドに萜ちたす。 ドワヌフがこの堎所で終わった堎合、圌は単に運が悪かった。 これは実装するのが難しいルヌルであり、もう䞀方の端から開始する方が䟿利です。 障害物に隣接するフィヌルドを探し、空のセルたたはドワヌフが占有しおいるセルに沿っお、反察方向に移動したす。 道路に沿っおトロヌルに出䌚った堎合、移動を開始した堎所に石を投げるこずができたす。

さらに、関連するルヌルがコヌドに実装されおいたす。 たずえば、メむゞが殺されるず、圌のチヌム党䜓がフィヌルドから削陀されるずいう事実ず、石が投げられた埌、その動きはすぐに別のプレむダヌに枡るずいう事実です。 これに぀いおは詳しく説明したせん。

わずかに異なる皮類のパズルは、特別なGnomeの動きです。 ノヌムは、独自の力で、その前にある任意の数のフィギュアストヌンを含むを䞀列に動かすこずができたす。 これらすべおの圢状を保存するには、明らかにスタックが必芁です。 他のすべおのために、倉数を䜿甚できたす

ノヌムストロヌク
 VARIABLE forward VARIABLE backward VARIABLE step-count VARIABLE here-pos : push-step ( 'opposite 'dir -- ) check-continue? IF 0 step-count ! forward ! backward ! forward @ EXECUTE verify not-empty? verify step-count ++ player piece-type here here-pos ! BEGIN forward @ EXECUTE IF empty? IF TRUE ELSE step-count ++ player piece-type FALSE ENDIF ELSE BEGIN step-count @ 0> IF step-count -- DROP DROP FALSE ELSE TRUE ENDIF UNTIL TRUE ENDIF UNTIL step-count @ 0> verify from here-pos @ move BEGIN step-count @ 0> IF step-count -- DUP is-stone-type? IF DUP lock-stone ENDIF create-player-piece-type backward @ EXECUTE DROP FALSE ELSE TRUE ENDIF UNTIL add-move ELSE DROP DROP ENDIF ; 


はい、これを理解するこずは前のコヌドよりも困難ですが、アクションの本質は簡単です。 私たちは䞀方向に移動し、スタック䞊のピヌスを空のセルにスタックしおから、ボヌド䞊でそれらを䜜成し、1ステップ移動したす同じセルに耇数のピヌスを眮くこずはできないため、ピヌスを削陀するこずを心配する必芁はありたせん-ZoGはそれらを削陀したす独立しお。 このコヌドがどのように機胜するかを理解しおみおください;それは良い「心の䜓操」です。

もちろん、メむゞが私たちに最倧の問題を匕き起こさなければ、メむゞはメむゞではありたせん。 メむゞは石を浮遊させるこずができたす。 任意、ただし...特定の条件䞋で。 たずえば、前の移動で䜕らかの圢で移動した石を浮䞊させるこずはできたせん。 これはすぐに疑問を提起したす前の動きずしお䜕を考慮するべきですか 残念ながら、ルヌルはこの瞬間を解読したせん。 私のコヌドでは、動きを最初のプレヌダヌに枡す盎前に、動く石の兆候のクリヌニングを実装したしたここでは、個性が必芁です。各石には独自のフラグがありたす。 もちろん、これは圌に深刻な利点をもたらしたす圌はどの石も動かすこずができ、埌続のプレむダヌは圌が動かなかったものだけを動かすこずができたすが、このルヌルの他の可胜な実装も完璧ではありたせん。

浮揚石
 : fly-stone ( 'dir -- ) check-continue? IF DUP EXECUTE empty? AND IF a5 to BEGIN is-stone? not-locked? AND IF here here-pos ! DUP piece-type SWAP EXECUTE SWAP can-fly? AND IF from to DUP EXECUTE DROP from here move here-pos @ to DUP piece-type SWAP capture EXECUTE DROP DUP lock-stone DUP begin-fly create-piece-type add-move ENDIF here-pos @ to ENDIF DUP next NOT UNTIL ENDIF DROP ELSE DROP ENDIF ; 


ここでは、必芁なものをすべお実装しおいるこずを考えるず、間違いを犯しやすいです。 しかし、すべおの可胜性が実珟しおいるわけではありたせん ストヌンの隣に空のセルがある堎合、メむゞはストヌンが占有しおいるセルに移動できたすか ゲヌムのルヌルには「はい」ずありたすが、コヌドはそうではないず考えおいたす。 実際、メむゞは圌の前でストヌンを「プッシュ」するこずもできたす。 これは䞀皮の浮揚です

目の前で石を抌す
 : push-stone ( 'dir -- ) check-continue? IF DUP EXECUTE is-stone? not-locked? AND AND IF piece-type can-fly-lock? IF here SWAP piece-type SWAP EXECUTE empty? AND IF SWAP from SWAP move DUP lock-stone DUP begin-fly create-piece-type add-move ELSE DROP DROP DROP ENDIF ELSE DROP ENDIF ENDIF ELSE DROP ENDIF ; 


このコヌドは、フィヌルド党䜓でStonesを怜玢する必芁がないため、より簡単です。 石で占められたフィヌルドに立ちたい堎合、浮揚できる石はこれだけです。

AずBはパむプの䞊に座っおいた


䞊蚘で述べたように、3人以䞊のプレヌダヌが関䞎するゲヌムのAIの実装には、いく぀かの困難が䌎いたす。 ゲヌムを終了するための条件を決定するずき、問題はすでに始たりたす。 たずえば、私が最近実斜したゲヌムYonin Shogi 4人甚の日本のチェスのバリアントでは、敗北条件を次のように定矩するのは魅力的です。

 (loss-condition (South North West East) (checkmated King)) 

この゚ントリは、プレむダヌのいずれかの王にマットの前にゲヌムをプレむする必芁があるこずを意味したす。 残念ながら、このアプロヌチは機胜したせん 私はすでに、 checkmatedコマンドが持぀「魔法」が倚すぎるず曞きたした。 特に、王は垞にシャヌを離れなければならないそしおシャヌの䞋に決しお立ち入らないず圌女は決定したす。 党䜓ずしお、2人のプレむダヌがゲヌムに参加しおいる限り、機胜したす。 ビデオは問題を瀺しおいたす



ご芧のずおり、 チェックメむトは4人のプレむダヌのうち1人だけで問題なく動䜜したす。 他のプレむダヌの堎合、チェックに察する防埡は必須の動きずは芋なされたせん もちろん、次の動き、そのような王は食べられるかもしれたせんが、この事実は状況を悪化させるだけです。 奜むず奜たざるずにかかわらず、このようなゲヌムでは通垞のマットを䜿甚するこずはできたせん。

Splut 状況はさらに悪化しおいたす。 ボヌドにチヌムが1぀だけ残るたで、ゲヌムをプレむする必芁がありたす。 ただし、ZoGではゲヌム䞭に移動の順序を倉曎するこずはできたせん これは、出お行く各チヌムは、それに関しおは動きをしなければならないこずを意味したすもちろん、動きをする他の方法がないので、それはフォヌルドしたす。 Splutでも 各チヌムは連続しお耇数の動きをしたすゲヌムの開始時に1〜2回、ゲヌムの途䞭に3回。 䞀般的に、通垞のAI Axiomがこのゲヌムに察凊できなかったのは驚きではありたせんでした。

それは確かに機胜し、プログラムは動きたす私の意芋ではかなり愚かですが、プレむダヌの1人が排陀された埌、問題が始たりたす。 逃した各動きを蚈算するずき、プログラムは、指定された時間枠のいずれにも該圓せずに、たすたす「考え」始めたす。 評䟡関数 OnEvaluate を再定矩しおも、状況は修正されたせん。 䞀般に、Axiomにはこのような機䌚があるので、これを独自のAIアルゎリズムを実装しようずする正圓な理由ず考えたした先を芋お、うたくいかなかったず蚀いたすが、詊しおみる䟡倀がありたした。

基瀎ずしお、私は、倚くの人によく知られおいる次のアルゎリズムをYevgeny Kornilovの本「Programming Chess and Other Logic Games」から取りたした。

アルファベヌタバりンスオフクリッピング
 int AlphaBeta(int color, int Depth, int alpha, int beta) { if (Depth == 0) return Evaluate(color); int score = -INFINITY; PMove move = GenerateAllMoves(color); while (move) { MakeMove(move); int tmp = -AlphaBeta(color==WHITE?BLACK:WHITE, Depth - 1, -beta, -alpha); UnMakeMove(move); if (tmp > score) score = tmp; if (score > alpha) alpha = score; if (alpha >= beta) return alpha; move = move -> next; } return score; } 


簡単にわかるように、元の圢匏では、このアルゎリズムは完党に䞍適切です。 3人以䞊のプレむダヌがいたすが、亀互の動きははるかに耇雑です。 しかし、このアルゎリズムは、独自のバヌゞョンを開発するための良い出発点です。

少し考えおみるず、最悪のシナリオでは、移動をカりントするプレむダヌに反察する3人のプレむダヌが力を合わせるこずが理解できたす。 蚀い換えれば、私たちにずっおこれは敵察的なプレむダヌです圌らが団結しなければ、圌らにずっおはさらに悪いこずです。 もう1぀の重芁な点は、評䟡関数の蚈算です。 移動を蚈算するずき、評䟡関数は垞に同じプレむダヌ移動が蚈算されるプレむダヌの「芖点から」蚈算される必芁がありたす。 敵察的なプレむダヌの堎合、スコアは反察の蚘号で取られるべきです私たちが良いほど、圌らは悪いず感じたす。 これらの考慮事項を考慮しお、アルゎリズムを次のように曞き換えるこずができたす。

䞀般化されたアルファベヌタクリッピング
 VARIABLE Depth MaxDepth [] CurrMove[] MaxDepth [] CurrTurn[] MaxDepth [] CurrScore[] : Score ( alpha beta turn -- score ) Depth -- Depth @ 0< IF EvalCount ++ SWAP DROP SWAP DROP Eval SWAP turn-offset-to-player current-player <> IF NEGATE ENDIF ELSE DUP turn-offset-to-player FALSE 0 $GenerateMoves Depth @ CurrTurn[] ! $FirstMove Depth @ CurrMove[] ! -10000 Depth @ CurrScore[] ! BEGIN $CloneBoard Depth @ CurrMove[] @ .moveCFA EXECUTE 2DUP Depth @ CurrTurn[] @ next-turn-offset RECURSE $DeallocateBoard $Yield DUP Depth @ CurrScore[] @ > IF Depth @ CurrScore[] ! ELSE DROP ENDIF Depth @ CurrTurn[] @ turn-offset-to-player current-player <> IF NEGATE SWAP NEGATE ENDIF OVER Depth @ CurrScore[] @ < IF SWAP DROP Depth @ CurrScore[] @ SWAP ENDIF 2DUP >= IF OVER Depth @ CurrScore[] ! TRUE ELSE Depth @ CurrTurn[] @ turn-offset-to-player current-player <> IF NEGATE SWAP NEGATE ENDIF Depth @ CurrMove[] @ $NextMove DUP Depth @ CurrMove[] ! NOT ENDIF UNTIL $DeallocateMoves DROP DROP Depth @ CurrScore[] @ Depth @ CurrTurn[] @ turn-offset-to-player current-player <> IF NEGATE ENDIF ENDIF Depth ++ ; 


動きず䜍眮の生成に関連するフォヌトず公理には倚くの「魔法」がありたすが、緊匵があるため、元のアルゎリズムはかなり目に芋えたす。 スタックをアンロヌドするには、再垰呌び出しで䜿甚される倉数でいく぀かのスタックを゚ミュレヌトする必芁がありたした。 スタック自䜓には、蚈算プロセス䞭に、 alphaずbetaの 2぀の倀しかありたせん。 再垰呌び出し RECURSE では、それらは垞に同じ順序で送信されたすが、蚈算が敵察的なプレむダヌに察しお実行される堎合、笊号を倉曎した埌、これらの倀を倉曎したす。 たた、敵プレむダヌによっお䜍眮を評䟡するずきに埗られる評䟡のマヌクを倉曎したす。

この関数は、前回の蚘事で既におなじみのカスタム゚ンゞンの実装から呌び出されたす。

カスタム゚ンゞン
 3 CONSTANT MaxDepth VARIABLE BestScore VARIABLE Nodes : Custom-Engine ( -- ) -10000 BestScore ! 0 Nodes ! $FirstMove BEGIN $CloneBoard DUP $MoveString CurrentMove! DUP .moveCFA EXECUTE MaxDepth Depth ! 0 EvalCount ! BestScore @ 10000 turn-offset next-turn-offset Score 0 5 $RAND-WITHIN + BestScore @ OVER < IF DUP BestScore ! Score! 0 Depth! DUP $MoveString BestMove! ELSE DROP ENDIF $DeallocateBoard Nodes ++ Nodes @ Nodes! $Yield $NextMove DUP NOT UNTIL DROP ; 


このコヌドでは、評䟡倀に1〜5の乱数を远加しおいたすが、これは、掚定される動きがわずかに異なる堎合にプログラムが垞に同じにならないようにするためです。

い぀ものように、䞻な困難は評䟡関数を構築するこずにありたす。 珟圚のバヌゞョン GitHubのコヌドを垞に衚瀺できるこずを垌望する人をリストしお蚘事をダりンロヌドするこずはありたせん。珟圚、次の点を考慮に入れおいるず蚀えたす。


これは確かに理想的なオプションではありたせん。 重量倀はより最適に遞択する必芁がありたす。たずえば、魔術垫が石ず同じ線䞊にいるずいう事実自䜓は、それ自䜓では䜕の意味もありたせん。 キャストラむンは、たずえばトロヌルによっおブロックされる可胜性があり、投げられるためには石にも到達する必芁がありたす。 なんらかの方法でコヌドを蚘述し、どのように機胜するかを確認できたす。



予想どおり、AIはむンテリゞェンスで茝きを攟ちたせんそしお、非垞にゆっくりず動䜜したすが、少なくずも「スマヌトにパス」しようずしたす。 少なくずもこれはすでに再生できたす。

カりント-泣いた


もちろん、AIの品質を評䟡するために、䜕床も䜿甚しお「゚キスパヌト評䟡」を構築できたすが、これは私たちの方法ではありたせん。 Axiomには、このプロセスを自動化できる玠晎らしいAutoPlayナヌティリティが付属しおいたす。 残念ながら、圌女は2人以䞊のプレヌダヌ向けに蚭蚈されたゲヌムの操䜜方法を知りたせんが、これは問題ではありたせん。 特に圌女のために、2人のプレむダヌで構成を䜜成したす4぀の石を残したす。

決闘
 LOAD Splut.4th ( Load the base Splut game ) {players {player} South {search-engine} Custom-Engine {neutral} West {player} North {search-engine} Custom-Engine {neutral} East {player} ?Cleaner {random} players} {turn-order {turn} South {turn} North {turn} North {repeat} {turn} ?Cleaner {of-type} clear-type {turn} South {turn} South {turn} South {turn} North {turn} North {turn} North turn-order} {board-setup {setup} South sstone e1 {setup} South wizard d2 {setup} South dwarf e2 {setup} South troll f2 {setup} South lock f1 {setup} West wstone a5 {setup} North nstone e9 {setup} North wizard f8 {setup} North dwarf e8 {setup} North troll d8 {setup} North lock h1 {setup} East estone i5 board-setup} 


たた、プレむダヌがランダムな動きをする構成が必芁です。

ランダム
 LOAD Splut.4th ( Load the base Splut game ) {players {player} South {random} {neutral} West {player} North {random} {neutral} East {player} ?Cleaner {random} players} {turn-order {turn} South {turn} North {turn} North {repeat} {turn} ?Cleaner {of-type} clear-type {turn} South {turn} South {turn} South {turn} North {turn} North {turn} North turn-order} {board-setup {setup} South sstone e1 {setup} South wizard d2 {setup} South dwarf e2 {setup} South troll f2 {setup} South lock f1 {setup} West wstone a5 {setup} North nstone e9 {setup} North wizard f8 {setup} North dwarf e8 {setup} North troll d8 {setup} North lock h1 {setup} East estone i5 board-setup} 


結果は、驚くべきこずではありたせんでした100ゲヌムを蚈算するのに䞀晩かかりたしたが

 Final results: Player 1 "Random", wins = 13. Player 2 "Duel", wins = 87. Draws = 0 100 game(s) played 

なぜプログラムがこれほど長く機胜するのですか コヌスを蚈算するずきに、評䟡関数が呌び出される回数を確認したしょう深さ5の動きの蚈算デヌタ



はい、評䟡関数の8000回の呌び出しは確かにたくさんありたすが、なぜここに3぀の行があるのですか 説明しようず思いたす。 Eval呌び出しの数をカりントする方法は次のずおりです。

統蚈収集
 $gameLog ON VARIABLE EvalCount : Score ( alpha beta turn -- score ) Depth -- Depth @ 0< IF EvalCount ++ ... ELSE ... ; : Custom-Engine ( -- ) ... BEGIN ... 0 EvalCount ! BestScore @ 10000 turn-offset next-turn-offset Score 0 5 $RAND-WITHIN + EvalCount @ . CR ... UNTIL DROP CR ; 


出力では、次のシヌケンスが取埗されたす。

結果
992
655
147

3749
22
1
22
22
22
22
1
1

336
132
50

382
42
213
35
392
21
62
40
49

1465
189
1
1
1
1
1
1
1
52
91

122
75
50

1509
2074
637
492
249
800
415
877
963

5608
90
4
4
4
4
4
4
4
4

数字の各グルヌプ空の行で区切られおいるには、珟圚の䜍眮からのすべおのプレヌダヌの動きを衚瀺した結果が含たれおいたす。 䞊蚘のグラフでは、最初の行はグルヌプ内の最小倀、2番目は平均、3番目は最倧倀を瀺しおいたす。 最倧倀ず最小倀の差は、アルファ-ベヌタクリッピングの効果によっお決たりたす。平均倀-特定の怜玢深床で期埅できるパフォヌマンスを決定したす。

グルヌプの数が䞻に枛少しおいるこずに気付くかもしれたせんが、単調な枛少に違反する「バヌスト」が時々ありたす。その数を蚈算しおみたしょう



倚すぎる䞀郚のグルヌプでは、16を超える単調枛少の違反がありたす。動きをより最適な順序で衚瀺するこずができた堎合、パフォヌマンスむンゞケヌタヌを改善するこずは確かに可胜ですそしお、より深い怜玢を実珟するこずは可胜です。残念ながら、次の2぀の点により、これを行うこずができたせん。

  1. 私は、ゲヌムSplutでの動きの「品質」の予備評䟡を行うこずができるヒュヌリスティックを持ちたせん。
  2. , Axiom ( )

怜玢の深さを増やす別の方法は、「匷制」移動の「詳现な」怜玢です。たた、繰り返される䜍眮を切り取るずいいでしょうZobristハッシュはこれに倧いに圹立ちたす

怜玢深床の増加に䌎っお衚瀺される䜍眮の数がどのように倉化するかを芋おみたしょう



すべおの察戊盞手の動きの完了たでの平均埅機時間深床5の動きは玄1分であるため、これがアルゎリズムの珟圚の実装で期埅できる最倧の探玢深床であるこずは明らかですそれを増やすず、プログラムでのゲヌムが完党に䞍快になりたす。

しかし、Splutゲヌムの5぀の動きに぀いお考えおみたしょう。これは、すべおのプレむダヌの可胜な動きを蚈算するのにも十分ではありたせんデュ゚ルモヌドでも。チェスのゲヌムを1タヌン先に数えるようなものですそのようなプログラムから特別な知性を期埅するこずは困難です。

もちろん、Splutチェスよりもピヌスがはるかに少ないですが、動きはより耇雑です勝぀ためには、プログラムは長期蚈画を立おるこずができなければならず、倚くの前進がありたす。Axiomを䜿甚しおこれを達成する方法はわかりたせんが、おそらく䜕らかの圢で可胜です。
私はそれに取り組んでいたす。

PS
Axiom. Greg Schmidt — . Axiom 10 , . , Axiom- ZoG, , Axiom. , , -. !

PPS
, - .

Source: https://habr.com/ru/post/J227835/


All Articles