背景
プログラミングに関する私の最初の多かれ少なかれ真剣なプロジェクトは、「Step into the Future」のチェッカーの実装でした。 残念ながら、しばらくしてプロジェクトの概念が劇的に変化したため、最後まで完了することができませんでした。 それにもかかわらず、プログラムはほとんど準備ができていて、それで遊ぶことさえ可能でした、さらにそれを書くプロセスは非常に面白かったので、私は思いついたアイデアとアルゴリズムを共有することにしました。
ゲームのルール
- ゲームは8x8の正方形のボードで、黒いセルでのみプレイされます
- ゲーム開始時のチェッカーは、各サイドの最初の3行を占めます
- 任意の数のチェッカーを任意の方向に倒すことができます
- 単純なチェッカーは前進のみ
- 簡単なチェッカーで削減できます
- 女性はあらゆる方向にいくつものフィールドを歩く
- 駒や動きがない人は負けます
- チェッカーは、戦闘後にフィールドから削除されます（これは言い換えることができます：1つのチェッカーを1回の移動で2回切り倒すことはできません）
- 確かに打つ
- チェッカーはクイーンに変わり、ボードの8行目（白の場合）または最初の行（黒の場合）に到達します。
- チェッカーがバトル中にダムフィールドを通過した場合、チェッカーはダムに変わり、次の戦い（可能であれば）をダムとして実行します。
実装
まず、ボードがメモリに保存される方法を決定する必要があります。 私の意見では、最適なソリューションは32個のオブジェクトの配列であり、各オブジェクトにはメソッドとプロパティのセットがあります。 プロパティには、セルに関する考えられるすべての情報が格納されます。例：
- name：a1 //実際のボード上のセル名
- color：1 //チェッカーカラー、1-白、2-黒、0-空のセル
- queen：false //チェッカーは女性ですか
- border：false //フィールドが強調表示されているかどうか
- doubleWay：false
- goldWay：true //これら2つのフィールドについては、後ほど説明します
もちろん、これらはすべて必要なプロパティではありませんが、すべてをもたらすという意味はわかりません。 メソッドについては、それらのいくつかがあり、それらは、クイーン、色などのフィールドを変更するなどの単純なアクションを実行してから、画像を更新します。 そのため、戦闘中、戦闘が進行しているセルと倒れたチェッカーが立っているセルを「浄化」し、戦闘が行われるフィールドにチェッカーを描画する機能が呼び出されます。
しかし、チョップするかどうかを決定する方法は？ これを行うには、各移動の前に、ボードがスキャンされ、いくつかの条件が満たされているかどうかがチェックされます。この条件を満たした場合は、勝つ必要があります。 しかし、これを行うためには、対角線上のボードを破壊する必要があります。これは、ボード上で正確に戦闘が行われるためです（ところで、これは通常の動きに必要です）。
- GoldWay：a1、b2、c3、d4、e5、f6、g7、h8 //いわゆる「高速道路」
- DoubleWayG1A7：g1、f2、e3、d4、c5、b6、a7 //ダブル
- DoubleWayH2B8：h2、g3、f4、e5、d6、c7、b8
- TripleWayC1A3：c1、b2、a3 //ティー
- TripleWayC1H6：c1、d2、e3、f4、g5、h6
- TripleWayH6F8：h6、g7、f8
- TripleWayA3F8：a3、b4、c5、d6、e7、f8
- UltraWayA5D8：a5、b6、c7、d8 //雑草
- UltraWayH4D8：h4、g5、f6、e7、d8
- UltraWayE1A5：e1、d2、c3、b4、a5
- UltraWayE1H4：e1、f2、g3、h4
対角線の内訳はまさにそうです。 すべての対角線は下から上にリストされていることに注意してください。 これはプログラマの便宜のために行われますが、必須ではありません。 オブジェクトのプロパティには、これらのすべての対角線がリストされ、セルが存在する対角線の値はtrueで、その他の値はfalseです。
したがって、複数の配列を作成しました。各配列には、配列が対応する対角線上のセルに対応するオブジェクトへの参照が含まれていました。 これにより、チェッカーを移動できます。
アルゴリズムを詳細に書き留めるのではなく、一般的な用語でのみ説明します。対角線のいずれかで次の状況が発生した場合：
「チェッカー（1）-チェッカー（2）-空のフィールド」（1と2はプレイヤーで、プレイヤーN 1は現在移動中）、または「空のフィールド-チェッカー（2）-チェッカー（1）」[両方次に、最初のセルのプロパティを割り当てます。これは、チョップする必要があるかどうかについての情報を担当します。 さらに、バトルを担当する共通変数（jumpIndと呼びましょう）を割り当てます。 これは、プレイヤーがチョップするピースを選択できる状況が発生する可能性があるために必要です。
プレーヤーがチェッカーをクリックすると、最初にjumpInd条件がチェックされます。 jumpInd = 1で、プレイヤーがクリックしたチェッカーが負けてはならない場合、何も起こらないか、プレイヤーがチョップする必要があることを示すメッセージが表示されます。 jumpInd = 0の場合、このチェッカーが移動できるかどうかがチェックされます。 確認は戦闘の確認と同様に、少し短くなります。対角線の1つに「チェッカー（1）-空のフィールド（白の場合）および空のフィールド-チェッカー（1）」[黒の場合、このフィールドを強調表示します。 jumpInd = 1で、プレイヤーがチェッカーを選択した場合、このチェッカーを使用して、この戦いが戦われることになり、戦いが戦われるセルも強調表示されます。 強調表示およびチェッカーすることができます。 これらのアクションは、プレーヤーの利便性のためにのみ必要です。 次のアクションでは、プレーヤーは別のチェッカーをクリックしてアルゴリズムを再度開始するか、強調表示されたフィールドをクリックして移動することができます。
プレーヤーが強調表示されたフィールドをクリックすると、テールをクリーンアップしてセルの色を変更するすべてのメソッドが実行されます。 jumpIndがゼロの場合、移動を2番目のプレーヤーに渡します。 jumpInd = 1の場合、プレーヤーが他の何かをカットできるかどうかを確認する必要があります。 その場合は、戦闘の結果として彼が落ちる可能性のあるフィールドを強調表示します。 チェッカーが女性になったかどうかを確認することを忘れないでください。 もしそうなら、戦いは女性の規則に従って行われます。 戦闘がまったくない場合は、再び女性になっているかどうかを確認し、jumpIndをリセットして移動を渡します。
チェッカーの単純な動きを実現することができましたが、これはほんの始まりに過ぎません。 今、私たちはダムの動きを認識しなければなりません。 エッセンス自体は似ていますが、ここではすべてを実装するのが多少難しくなります。
対角線ごとに、条件は両方向でチェックされますが、エッセンスはチェックの順序のみであるため、1つだけで書き込みます。
動きを確認します。「女性が空のフィールドです」という状況がある場合は、このセルを強調表示して次のセルを確認します。 対角線が終わるまで、または反対色のチェッカー（女性）に会うまで実行します。
戦闘の確認：状況がある場合：「女性-z空のフィールド-反対色のチェッカー（女性）-n空のフィールド」（z> = 0、n> 0）、次に、相手のチェック後にn個のすべての空のフィールドを強調表示します（まだある場合）通常のチェッカーの場合のように、1人の対戦相手のチェッカー、次に停止）、戦闘に関する情報を格納する変数を使用してこれらの操作をすべて実行します。 プレイヤーが強調表示されたセルをクリックした後、私たちが来たものを除く、あらゆる方向の別の戦闘の可能性を確認する必要があります。 これらすべてのチェックと条件の実装には多くの時間とスペースがかかりましたが、何かを逃しただけで、より短く、より美しいものすべてを実装することができました。
そしてもう1つの非常に重要なことは、次の条件を忘れないことです。チェッカーを2回削減することはできません。 これは、現在あなたがいる対角線のチェッカーが既に切り取られている場合、移動が終了することを意味します（現在立っているフィールドの通常のチェッカー、およびこの対戦相手のすでに切り捨てられたチェッカーまでの空のフィールドの女性の場合） ） オプションとして、すでにカットされたチェッカーのアドレスをいくつかの配列に保存し、移動を送信するときにのみリセットすることができます。 （実際、私はそのようなことをしました）
（黒の女性は次のようにカットする必要があります：h4：e1：c3：e5、停止します。g3-チェッカーはまだボード上にあるためです。その後、白が切り込んで勝ちます）
このアルゴリズム全体は、次のフローチャートで簡単に説明できます。
最初のクリック：
2回目のクリック：
プログラムが最初のクリックがどこにあり、2番目のクリックがどこにあるかを理解するために、論理変数false = first click、true = second clickを作成します。
一般に、ゲームのルールの実装はここで終了します。 すべては比較的複雑に見えませんが、アルゴリズムをコードに転送すると、コードが大きくなり、大きくなる多くの小さな問題と困難があります。 私が選んだボードの実装のまさに原則は非難することですが、これはこれらの2週間または3週間（および具体的な中断のあるもの）で私の頭に浮かんだ最高のものです。簡単です。 このためにコードを犠牲にすることは受け入れられると思います。
人工知能
しかし、私たちの冒険はこれで終わりではありません。 チェッカーに移動を教えたのは素晴らしいことですが、誰とプレイするのでしょうか？ ゲームの人工知能を作成する必要があります。 残念ながら、最適化が不十分であるため、5〜6移動（約20〜25,000ポジション）をレンダリングするときにプログラムがハングし始めたため、完全には実現できませんでした。 実装中に、 プログラミングチェスとその他のロジックゲームの本を使用し、ロジックゲームのAIの問題に興味のある人にはお勧めします。 改良されたアルファベータカットオフアルゴリズムについては解決しましたが、ここでは説明しません。これは、私の前にHabréで何度も説明されてきたためです。
日本のチェスをプレイするためのAIの構築における機械学習の使用（将gi）
ウサギとオオカミのゲームの例のミニマックス
その他。
残念ながら、冒頭で述べたように、競争のための私のプロジェクトのコンセプトは変わりました。そのため、AIは未完成のままで、遠方に投げ込まれました。 私がなんとか定式化した位置評価の原則もいくつかあります。 私は彼らをここに連れて行くことができましたが、彼らはその特異性のために特別な興味はありません。 興味のある方は、評価関数とクリッピングアルゴリズムについて別の記事を書くことができます。 このすべてが6か月前に発生し、主に記憶から記事を書いたので、不正確または矛盾が生じる可能性があるため、コメントでそれらを指摘していただければうれしいです。 もっと詳細にペイントする必要がある場合は、同じ場所に連絡してください。 ご清聴ありがとうございました。