Geekly Articles each Day

シンプルなツメゎ栌子の曞き方

2察2ゎバネ 箄1幎前、友人が私に行っお、それがどのようにプレむされるかを瀺したした。 最初のゲヌムの1぀で、ボヌドの䞋偎を䞊に接続する石のチェヌンず、巊偎を右に接続するチェヌンを誇らしげに構築したこずをよく芚えおいたす。友人がこれを確かに良いず教えおくれたしたが、私は倱いたした。 その埌、その理由を理解するのに長い時間がかかりたした。 それ以来、私は最初のKGS段に぀いお進み、友人は私ず遊ぶのをやめたした。

倖出先でうたくプレむするには、いく぀かの動きを先に芋る必芁がありたす。このスキルは、倚くの問題を抱えおいる解決策をうたく開発したす。 圓然のこずながら、ある日、これらの事柄の栌子を曞いお、理想的には問題に埋め蟌むのがいいだろうずいう考えに打たれたした。特に、adumがこの考えを承認するので。 私自身は、数秒で玄1の速床で倚かれ少なかれ意味のある動きを詊行する非垞にゆるやかな方法でそれを解決しおいるので、怜玢の開始方法を定期的に忘れおいたすそしおこれは、䞎えられた問題3を自信を持っお解決するのに十分です。速床ず粟床は最も単玔な怜玢、぀たりdfsで機胜し、タスクの耇雑さを「数日間」ず評䟡したした。 すぐに、私はこの栌子を最も単玔なdfsを䜿っお「正面から」玠早く曞き蟌もうずしたしたが、ちょっずした迷惑に぀たずきたした。 考え盎さずに、私は既に決められた䜍眮を保存するためのキャッシュを開始し、すぐに別の迷惑に぀たずきたした別の動きのシヌケンスでこの䜍眮に来るず、䞀床芋぀かった解決策は間違っおいるかもしれたせん。 ここで私は䜕をすべきかわからずにハングアップしたしたが、このトラブルは簡単に解決できるず刀断したした。少し考えおみるだけです。 私は長い間考え、このトピックの準備ができおいるもの、蚘事、アルゎリズムなどを芋るこずが理にかなっおいるず刀断したした。 私が最初に出䌚ったのは、特定の「ラムダ深さ第䞀蚌明番号怜玢」であり、蚘事のサむズが数ペヌゞしかないこずを芋お、喜んで読み始めたした。 この蚘事には、MartinMÃŒllerずAkishi Kishimotoによる他の同様の蚘事ぞのリンクがあり、それらの蚘事にはリンクもあり、Kishimotoによる200ペヌゞの論文ぞのリンクがあり、問題の芏暡を認識したした。非垞に単玔なものでさえ、ほずんどの堎合、アルゎリズムの耇雑さは非垞に耇雑でした堎合によっおは、質問はすべおのオプションをどのように゜ヌトするかではなく、ボヌド䞊で䜕かを芋぀ける方法初心者でもすぐに䜕をするか、䜕をキャプチャたたは防埡する必芁があるかを理解する方法人にずっおも些现なこず、およびどのような動きがありたすか これはほずんどの堎合も明らかですオプションの実際の列挙に関しおは、決定されたず蚀えたすただし、効果的な列挙アルゎリズムは非垞に泚意が必芁です。 䞀般に、私のIQは明らかに倖出先でこのような問題を解決するのに十分ではないこずに気付き、すべおの意味のある動きず目暙が事前に蚭定されおいる最も単玔なケヌスの゜ルバヌを少なくずも曞ければいいず刀断したした-これは問題でも非垞に圹立ちたす。

私の知る限り、すべおを解決するプログラムはほずんどありたせん。

-Thomas WolfのGoTools最倧15の可胜な動き、クロヌズド゜ヌス、非垞に高床な静的解析を備えた簡単なdfs。
-Martin MullerのTsumego Explorerちなみに7が䞎えられたす最倧30の可胜な移動、オヌプン゜ヌスJavaどこで入手できるかは明確ではありたせんが、Mullerの蚘事ず論文で説明されおいる非垞に高床な静的分析による高床なl-df-pn-r怜玢岞本。
-Martin MullerのFuegoオヌプン゜ヌスのC ++SourceForgeからダりンロヌド可胜を䜿甚しお、本栌的な2+ボットが提䟛されたす私よりも明らかに匷力なので、その匷さは評䟡できたせん。

MÃŒllerもadumもjs栌子を聞いおいたせんそしお、栌子はgosbleblemsに埋め蟌むこずができるようにjs䞊になければなりたせん、もしそうなら、それを曞くこずは理にかなっおいたす-特にMÃŒllerずKishimotoが倚くの蚘事ずこのトピックに関するプログラムですら。

タスク№18629、第䞀段 巊は兞型的な぀めごです。 䞀般的なケヌスでは、タスクは黒ず癜の䞡方に察しお最適な動きおよび必芁かどうかを芋぀けるこずです。 明らかに、癜が先に動いた堎合、圌らはコヌナヌをキャプチャしたす。 黒が最初に移動するず、角床を保存できたすが、解の1぀はkoに぀ながり、黒がkoに負けた堎合は角床を倱い、もう1぀の解はkoなしで角床を保存したす。これは通垞望たしいこずです。

簡単にするために、ボヌドを芋お、解決するために敎理する必芁があるすべおの意味のある動きを芋぀ける方法があるず仮定したす実際、これはすべおの動きが手動で蚭定されるこずを意味したす。 ボヌドbで誰が勝぀かを瀺す関数Rを定矩したす。



Rの定矩により、黒は秒のバランスを厩したずしおも最初の動きをする矩務がありたす-これは癜ず黒が絶えず通過する状況を排陀したす。 癜人に぀いおも同様です。 黒ず癜の䞡方が倱われた堎合、これらはセクです。 次に、この関数を次のように再垰的に定矩できたす。



少しわかりにくいですが、その本質はシンプルです。

  1. Rの定矩により、ブラックは䜕らかの動きを䜙儀なくされおいるため、可胜な限りすべおの動きの䞭からベストを遞択したす。 したがっお、すべおの移動の最倧倀はmです。
  2. その埌、動きは癜になり、圌らは動きをするかしないかを決めるかもしれたせん-これは最小です。 ホワむトが動きをする堎合、結果は ここで、b + mは、黒い石mが远加されたボヌドbです。
  3. 癜が動きを逃した堎合そしお、これがRの定矩ず矛盟しない堎合、黒には遞択肢がありたす動きをするかセヌブするか、ゲヌムを終了したす-これは2番目の最倧倀です。 黒が動けば、刀明 、そしお、それらが倱敗した堎合、Rb + mは誰が勝ったかを決定したす実際には、これは、捕獲する必芁がある石がボヌド䞊にあるかどうかを確認するためだけです。


癜に぀いお察称匏が埗られたす。 「額」ず数えるず、すべおのオプションを列挙した単玔なdfsが埗られたす。これは、5ポむントの最も単玔な攻撃でも非垞にゆっくりず動䜜したす。 次のように曞くこずができたす。

function solve(board: Board, color: Color): Result { var result = -color; // that's a loss for (const move of board.getMovesFor(color)) { const nextBoard = board.fork().play(move); result = bestFor(color, // it's +color's turn, so he chooses result, bestFor(-color, // now it's -color's turn solve(nextBoard, -color), // -color makes a move bestFor(color, // -color can pass, but then it's +color's turn again solve(nextBoard, color), // +color makes two moves in a row estimate(nextBoard)))); // neither player makes a move } return result; }


このアルゎリズムは、最も単玔な秒が秒であるこずを蚌明するために倚くの時間を浪費するこずに泚意しおください。 癜ず黒のグルヌプに共通の自由のみがあり、これらの自由が倚数ある堎合、このアルゎリズムは最初に最初の自由でプレむしようずし、それが機胜しないこずを芋぀け、次に2番目の自由でプレむし、再び勝おないこずを芋぀けたす。 このアルゎリズムがすべおのオプションを反埩するために行う移動の数に぀いお、単玔な再垰匏を䜜成するこずもできたす。 成長は指数関数以䞊です。 この問題は、おそらく静的解析によっおのみ解決できたす。

ここで、同じボヌドが2回解決されないようにする必芁がありたす。 たずえば、5ポむントの高架道路の解決策を芋぀けたら、別の䜍眮がその高架道路に䞋がった堎合に再利甚できたす。 このような゜リュヌションキャッシュは通垞、転眮テヌブルttず呌ばれたす。 このテヌブルのキヌは、ボヌドのハッシュ+最初に行く人の色です。 最初は、このように単玔に実装したした。

 const tt: { [key: string]: Result } = {}; function solve(board: Board, color: Color): Result { const key = color + board.hash(); var result = -color; // that's a loss if (key in tt) return tt[key]; for (const move of board.getMovesFor(color)) { const nextBoard = board.fork().play(move); result = bestFor(color, // it's +color's turn, so he chooses result, bestFor(-color, // now it's -color's turn solve(nextBoard, -color), // -color makes a move bestFor(color, // -color can pass, but then it's +color's turn again solve(nextBoard, color), // +color makes two moves in a row estimate(nextBoard)))); // neither player makes a move } return tt[key] = result; }


このコヌドの問題は、石の䜍眮を芋ただけでは刀断できない䜍眮があるこずです。 たずえば、ホワむトの動きは巊偎にありたすが、誰が勝぀かを理解するこずは䞍可胜です。なぜなら、ホワむトがブラックの石を捕らえるこずができるかどうかは䞍明だからです぀たり、兞型的な共同たたは2移動サむクル ルヌルのこの小さな修正-䜍眮を繰り返すこずはできたせん-はゲヌム䞭に圓たり前のこずであり、問​​題を匕き起こすこずはありたせん。たた、スヌパヌコルヌル぀たり、数回の移動を䌎うサむクルの犁止は、毎日10ゲヌムをプレむしおも䞀生䌚いたす。 奇劙なこずに、アルゎリズムの列挙䞭に、いく぀かの動きの長さ5-7でそのように動きたすのサむクルが存圚するずいう仮想的な可胜性も確実に実珟され、これが考慮されない堎合、結果が正しくないか、アルゎリズムがルヌプしたす。 したがっお、この䞀芋仮想の問題は、岞本の論文「反埩の存圚䞋での正確か぀効率的な怜玢アルゎリズム」ずしお200ペヌゞも授䞎されたした実際、私はそれを圧倒しようずしおいたす。

この問題の解決策はミュラヌず岞本の蚘事で䜕床も蚀及されおおり、次のように聞こえたす解決策の怜玢で繰り返しが芋぀からなかった堎合、それは圌らがこの䜍眮に来た方法に䟝存したせん。 あなたがそれに぀いお考える堎合、ステヌトメントはたったく明らかではありたせん。 私が蚌明にうんざりしおいるずき、私はミュラヌに手玙を曞きたした、そしお、圌はそうです、これは非垞に匷くお普遍的な声明であり、蚌明は論文のどこかにあるようです。 そこにはこの蚌拠が芋぀かりたせんでしたが、既に解決されたパスに䟝存しないすべおの決定がメモリ䞍足のため削陀されるこずはないず仮定すれば機胜する独自の蚌拠を考えたした。

説明のために、私は恥知らずに誰かから写真をコピヌしたした:)可胜な動きのグラフは通垞、写真の䞭のこのツリヌのように芋えたす。 このグラフの䞊郚は、ボヌド䞊の石の䜍眮を衚し、色は誰が動くかを瀺したす。 簡単にするためそしお䞀般性を倱うこずなく、13番目のポゞションが先に決定され、怜玢プロセスでサむクルが芋぀からなかった間にBlackが開始しお勝ったこずが刀明したず仮定したす。 ゜リュヌションはツリヌでありサむクルはありたせん、各黒い頂点から1぀の動きが行われ゜リュヌションの本質は任意の䜍眮で正しい動きを瀺すこずであるため、必芁ありたせん、すべおの可胜な動きは各癜い頂点から行われたす゜リュヌション癜の動きごずに黒の動きがあり、黒の勝利に぀ながるこずを蚌明する必芁がありたす。 ここで、ステヌトメントが真実ではなく、13の䜍眮で芋぀かった解がそれが含たれるパスに䟝存するず仮定したす。 どういうわけか決定を間違える方法がありたす。 そのようなパスがデシゞョンツリヌず亀差しなかった堎合、そのパスに圱響を䞎えるこずはできたせん。この仮想パスには、ツリヌの少なくずも1぀の頂点が含たれたす。 このピヌクを取り、それを忘れずにこの経路に沿っおピヌク13に進んでください。

  1. 13の゜リュヌションは既にキャッシュされおおり、
  2. サむクルを怜出せずに芋぀かったすべおの䞭間゜リュヌションもキャッシュに残りたした。


頂点17から始めお、13に到達しようずするずしたす。蚌明の本質は、決定ツリヌにサむクルがないため、17から13に接続するためにツリヌを超える必芁があるこずです。 頂点17は癜たあ、はい、それは赀ですが、それが癜であるず仮定したすであり、したがっお、それからのすべおの動きはツリヌ内にありたす。 25番目のブラックピヌクに達したずしたしょう。 頂点は黒であるため、その゜リュヌション正しい移動はキャッシュに曞き蟌たれそこからは䜕も削陀されたせん、25の゜リュヌションが芋぀かった埌、この仮想パスに沿っお進むため、既補の゜リュヌションをキャッシュから取埗し、ただツリヌ内にある癜いピヌクに入りたす。 ですから、この仮想的な道をたどり、動きのない行き詰たりに陥るたで埅ちたす。

ご芧のずおり、ルヌプの問題を解決するには、かなりの量が必芁です。

  1. 䜍眮ではなくパスの解決策を探したす解決パスボヌド[]、色色。
  2. 怜玢䞭に繰り返しに遭遇した堎合、それを敗北ず芋なしたすが、同時に、繰り返されるパスの先頭を指したすパスのむンデックスを芚えおおいおください。 ペア結果、むンデックスの意味は、解は無条件ではなく、特定の䜍眮での繰り返しに䟝存するずいうこずです。
  3. すべおの可胜な動きの䞭ですべおが敗北に぀ながる堎合、繰り返しを瀺すすべおのむンデックスの䞭で最小倀を芋぀け、この最小倀を返したす。
  4. 勝ち手がある堎合は、可胜な限り倧きな繰り返しむンデックスを持぀ものを遞択するこずが望たしいです。 最良の堎合、ゲむンは無条件になりたす。 パスに䟝存したせん。


これおよび石の自由床を最倧化し、他の人の自由床を最小化する単玔なヒュヌリスティックは、最も単玔な倧工の正方圢を解くのに十分です。

最初の䟋のように、もっず面癜いこずを解決するには、coを考慮する必芁がありたす。 考えられるアプロヌチの1぀は、「動的に」怜蚎するこずです。 怜玢プロセスで繰り返しが発生する堎合は、怜玢を2぀のケヌスに分岐したす脅嚁がある堎合ずない堎合が、このためにはコヌド党䜓を培底的にシャベルする必芁がありたす。 別のアプロヌチは、次の「静的」な䌚蚈です。

  1. 新しいパラメヌタヌは、倖郚の脅嚁の数です。 このパラメヌタヌが+3の堎合、黒にはさらに3぀の脅嚁があり、-2の堎合、癜には2぀の脅嚁がありたす。
  2. 決定プロセス䞭に繰り返しが発生し、この繰り返しに察する脅嚁がある堎合、無駄になり、パスがリセットされたす実際、脅嚁の目暙は、パスをリセットし、れロから怜玢を開始するこずです。
  3. キャッシュ内の決定は、単䞀の数倀+1たたは-1ずしおではなく、䞡偎の数字の無限の配列ずしお曞き蟌たれ、それぞれの共脅嚁の数に察しお結果が曞き蟌たれたす-2共脅嚁の堎合、癜が共脅嚁を1぀だけ持぀堎合、癜が勝ちたす。 secaが刀明し、脅嚁がなければ黒が勝ちたす。 明らかに、黒がN個の脅嚁で勝った堎合、圌はN + 1でも勝ちたす。 癜人に぀いおも同様です。 これは、゜リュヌションが2぀の数字の圢匏で蚘述できるこずを瀺しおいたす。勝利するのに十分な黒の脅嚁の数maxbず、勝利するのに十分な癜の脅嚁の数minwです。 そしお、k個のco脅嚁を持぀bの解を探しおおり、b minwずmaxbが以前の解決の詊みから知られおいる堎合、k <minw癜勝ずk> maxb黒勝の答えをすぐに返すこずができたす。 minw <k <maxb解決策を探す必芁がありたす。


 interface Results { minw: number; // white wins if nkt <= minw maxb: number; // black wins if nkt >= maxb } const tt: { [key: string]: Results } = {}; function solve(path: Board[], color: Color, nkt: number): Result { function solveFor(color: Color, nkt: number): Result { const board = path[path.length - 1]; const key = color + board; const cached = tt[key] || { minw: -Infinity, maxb: +Infinity }; if (color > 0 && nkt >= cached.maxb) return +1; // black has enough ko treats to win if (color < 0 && nkt <= cached.minw) return -1; // white has enough ko treats to win var result = -color; // that's a loss var depth = Infinity; // where repetition occured /* ... */ if (color > 0 && nkt < cached.maxb) cached.maxb = nkt; if (color < 0 && nkt > cached.minw) cached.minw = nkt; tt[key] = cached; return [result, depth]; } return solveFor(color, nkt); }


さお、倖郚の脅嚁を考慮しお問題を解決するために、最初に脅嚁がないずいう仮定の䞋でそれを解決する必芁がありnkt = 0、結果が倉わるたでこのパラメヌタヌを増枛し続けたす。 これは、理論的には決定グラフによっお決定できたす。芋぀かった゜リュヌションが倱われたkoに䟝存する堎合、1぀の倖郚ko脅嚁を远加しお再床解決するのが理にかなっおいたす。 実際には、私はこれをしたせんでした。必芁な脅嚁の数が1を超えるこずはほずんどありたせん。 解決するために2぀のkoを獲埗する必芁がある問題がありたすが、これぱキゟチックです。したがっお、| nk2 | <2で解決した堎合、䞀般に、問題は解決したず蚀えたす。 このように、キャッシュを埋める最初の゜リュヌション通垞はnkt = 0の堎合の怜玢に99の時間が費やされ、その埌、他のnktの゜リュヌションがJSでもほが瞬時に芋぀かるこずに泚意しおください。

それだけです。 最適化のないJS䞊のこのような単玔なラティスは、すべおの人GCがロヌドするものに䞀時オブゞェクトを䜜成し、各移動がボヌド党䜓をコピヌする前に、数秒で合蚈10個の空きセルをすばやく解決できたすたずえば最初に芋せたもの。 少し倧きくなるず、ほずんどの堎合、ハングし、GCをロヌドしたす。 ただし、アルゎリズムを高速化する方法はたくさんあるため、この皮の最適化には意味がありたせん。



気にする人は 、 githubでコヌドを芋るこずができたす。 率盎に蚀っお、速床を犠牲にするこずなくモゞュヌルに分割されるようにラティスコヌドを敎理する方法を理解したらすぐに、すべおを曞き換えおnafigする必芁がありたす。など さお、単䜓テストを曞くこずができるように、そうでなければ、各倉曎の埌、「このがらくたはただ機胜したすか」

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

More articles:


All Articles