Habréで、ブルダゲームの単語検索アルゴリズムに関する記事を見つけました： habrahabr.ru/post/207734私自身はRobot Balda 2ソルバーの著者であり 、長年にわたってBaldaゲームの多くのオンラインプレーヤーの間で人気を得ています。 そして、私の経験を共有し、ブルドーザーのゲームのユニークなアルゴリズムについてお話したいと思います。これはまだ誰も使用していません。
その記事全体について。 同じアルゴリズムに従って、プレフィックスツリーを使用して単語を検索します。 しかし、2つのツリーの代わりに、シンボル「separator」を含むツリーがあり、その後、残りの単語が反転します。
シンボル「ダミー」を使用して、より複雑なプレフィックスツリー（「ターボモード」）を含めることもできます。 この場合、ターミナルノードには、ダミーに入れることができるすべての文字が含まれています。 たとえば、K * Tに移動して、ターミナルノードに出会いました。 「O」と「And」の2つの文字が含まれます。 セル「O」にはKOTという単語へのリンクがあり、「I」にはKITという単語へのリンクがあります。 その結果、ダミーを使用すると、空のセルでの各反復での32文字の枯渇を取り除くことができます。 ただし、プレフィックス辞書のサイズは約5倍になります。 純粋な形では、これにより4倍の加速が得られます（メモリを変更しない場合）が、単語の検索に加えて、分析にも時間を費やしているため、合計加速はわずか1.5倍です。
ダミーツリーをプレフィックスツリーの最初の文字（ルートノード）にして、常にダミーから単語の検索を開始することをお勧めします（ダミーシンボルのないツリーがある場合でも）。 この場合、検索速度ははるかに速くなり、ツリーは5倍になりません。 ただし、既に設定されている文字から検索を開始するように特別に設定しました。 これは非常に効果的ではありませんが、 再帰的なパッセージの数が増加し、単語が通過する各セルに必然的に現れる重複をふるいにかける必要があります。 しかし、そのようなアプローチ（空でないセルからの検索）は、1つのトリッキーな最適化を適用できるように特別に考案されました。これについては、最後に説明します。 これにより、重複の問題が解消され、速度が補正され（さらに大きくなります）、新しいプロパティ（検索時間の安定性）が表示されます。
多くの人がなぜもっと速くなるのかと尋ねるかもしれません。 最も単純で最も遅いアルゴリズムでさえ、ミリ秒単位で単語を探す場合。 これらの質問は、「チャンピオン」と対戦しようとしたことのないプログラマーに対してのみ発生します。 彼らのプログラムは、いくつかの前進を考えることができます。 これは、プログラムが単語を検索するだけでなく、戦術も適用する必要があることを意味します。 そして、すべての論理ゲームで最も普遍的な戦術はミニマックスです。 内容： ここまたはここで詳しく説明してい ます 。 また、ミニマックスを使用すると、多くの仮想移動を行う必要があります。 たとえば、各プレイヤーが1ターンあたり平均100ワードを取得する場合、4ターン先のゲームを開発するためのすべてのオプションを調べるには、100 ^（4-1）= 1,000,000の検索が必要になります。 プログラムが1ミリ秒ですべての単語を検索できる場合、4分前のゲームが16分でチェックされます！ そして、原則として、移動の反映のために2分が与えられます。 これで、非常に迅速な検索が必要な理由がわかりました。 私のプログラムでは、数秒で8〜10の動きを分析できます。
最大の加速は、単語をふるい分けることによって与えられます。 簡単に言えば、最も長い単語のみが検索ツリーの分岐になります（これはおおよそです。実際には、単語の選択はもう少し複雑です）。 実践が示しているように、ゲームの開始時と途中で、将来の短い単語が長い単語でポイントの差を出し、さらに多くのポイントをもたらすことは非常にまれです。 相手には「回収」する選択肢が多すぎるため、相手を捕まえる確率が低すぎます。 したがって、短い言葉で時間を無駄にすることは意味がありません。 そして、それがゲームの終わりであり、多くの動きが残っていない場合、プログラムは分析された単語のリストを展開します。 ゲームの終了前にすでに4〜6の動きがあり、絶対にすべての単語が列挙に参加します。 そして、ゲームの終わりまでに、短い言葉を見るのが適切です。 4〜5文字の単語を含むゲームの終わりに、2〜3文字からなる方が収益性が高いことは珍しくありません。
2番目の重要な加速は、 アルファベータクリッピングによって与えられます。
その前に、私はあなたが常に見つけて慣れ親しむことができる標準的なアルゴリズムに言及しました。 そして今、「発明」を書きます。 仮想移動のツリーを構築するプロセスでの単語検索の最適化に関するものです。 ここを見て。 いつものように、ブルドーザーで検索ツリーを構築します。
1.すべての単語を検索します。
2.すべての単語を並べ替え、各単語を順番にプレイフィールドに配置します。
3.ポイント1に再帰的に通過します。または、深く登りすぎると再帰から戻ります。
そして今、私が持っているように、書きます：
1.すべての単語を検索します。
2.すべての単語を並べ替え、各単語を順番にプレイフィールドに配置します。
3.すべての単語を見つけますが、原則は異なります！ 最後のターンですでに見つかったすべての単語を検索結果にコピーします。 このリストから、現在作成できない単語を除外します。つまり、挿入された文字が、最後に再生された単語の文字が置かれたセルと同じセルにあるすべての単語を削除します（結局、このセルは現在占有されているため、それ以上は構成できません言葉）。 次に、新しい単語をリストに追加します。 これを行うために、私たちは競技場ですべての単語を探しているのではなく、最後の単語で占有されているセルを通過する単語だけを探しています。 結局のところ、前の動きから何が変わったのか-新しい手紙が競技場に現れました。 したがって、新しい単語が出現した場合、それらはすべて新しい文字を通過する必要があります。 それらが合格しない場合、これらの単語はすでに以前に発見されており、リストに含まれています。
結果：競技場の各セルから単語の再帰検索を開始する代わりに、1つのセルで開始します！ 競技場のサイズに関係なく。 競技場に百万個の細胞が含まれていても。 常に1つのセルで新しい単語を「探し」ます！
4.ポイント2に再帰的に通過するか、深く登りすぎると再帰から戻ります。
私の実際の単語リストは毎回コピーされるわけではなく、単語は純粋な形で削除されません。 そして、これはすべて、次元を「セルアドレス」、「ストロークの深さ」、および特定の深さで特定のセルで見つかった単語のID文字として定義されている多次元配列のページへのポインタを切り替えることで行われます。 したがって、ツリー内の1レベルをロールバックするとき、このノードで見つかった単語のリストを復元する必要はなく、単に「ページ」へのポインターを減らします。 そして逆に、さらに深くなると、インデックスが増加し、新しいページに新しい単語が入力されます。 そのように。 10番目の動きのどこかで、このターンのすべての単語を見つけるために、10個の「検索ページ」からすべての単語を追加する必要があります。 それらはすべて合計であり、通常の方法で検索されたかのように、単語のリストです。 しかし、正直なところ、多次元配列の構造に関する技術的な詳細をすべて覚えているわけではありません。
奇妙なことですが、単語を「検索」するための私のアルゴリズムでは、驚くほどの加速は得られませんでした。 しかし、彼は検索時間に安定性を与えました。 通常の検索方法は、ゲームの途中ですでにかなり遅くなりますが、私の「負荷」に気づいていません。 結局のところ、前述のように、競技場にいくつの文字があっても-各仮想ムーブの単語はすべてではなく、最初のセルでのみ検索されます。 この特性は、特に大きな競技場で価値があります。
結論として、ミニマックス解析は辞書の精度に強く依存すると言いたいです。 したがって、重要なのは辞書のサイズではなく、ゲームポータルの辞書との対応です。
ゲームBaldaで単語を見つけるためのアルゴリズムと戦術
All Articles