こんにちは！



私たちは、サンクトペテルブルクHSEで応用数学と情報学の1年生の学部研究を行っています。C ++で学期のチームプロジェクトに取り組んでいる間、ボットを備えたIntellectorのコンピューターバージョンを作成することにしました。これは、特殊な図形を備えた六角形のボード上のチェスゲームです。



この記事では、ゲームの開発がどのように進んだか、六角形のボードを飼いならす方法、コマンドラインを描画する方法、そしてほとんど倒せないボットを作成した方法について説明します。







私たちのチームには、Yura Khudyakov、Valera Golovin、MishaSavrasovの3人がいます。私たち一人一人にとって、これは最初のチームプロジェクトであるため、作業の過程で、プロについて書くだけでなく、チームで作業し、バージョン制御システム（この場合はgit）を使用することも学びました。このプロジェクトには、特に自転車など、多くの奇妙な点があります。使用できる優れた既製のソリューションがあります。しかし、私たちのプロジェクトの目標は経験を積むことだったので、私たちは自分たちでたくさんの発明と実装を行いました。

インテリクターとは何ですか？

まず、どのようなゲームを書いたかを説明する価値があります。



ゲーム「Intellector」が最近登場し、今なお人気を集めています。今年、最初のオープンチャンピオンシップがサンクトペテルブルクで開催されました。





インテリクターは、フィールドの構造、ルール、およびピースのセットがチェスとは異なります。ただし、多くの要素は類似しています。たとえば、ゲームにはポーンの役割を果たすプログレッサーフィギュアがあります。彼女は前方にのみ歩き、極端な列に達すると別の人物に変わることができます。



ここの王様はインテリクターと呼ばれる人物です。ゲームの目的は、チェックメイトではなく、このピースをカットすることです（これはほとんど同じことですが）。



ゲームの仕組みの違いは、フィールドの詳細から生じます。Intellectフィールドは対称的であり、キングサイドとクイーンサイドのチェスとは大きく異なります。



この記事を理解するために、ルールの知識とプレイする能力は必要ありません。

一般的なアーキテクチャ

アプリケーションに何が必要ですか？

ゲームを機能させるには、その主要コンポーネントであるゲームのロジックを実装する必要があります。ボードモデルと移動ルールが含まれています。さらに、便宜上、移動の履歴を保持し、元に戻す/やり直しを実装することをお勧めします。



ボードを表示し、ユーザーがプレイできるようにする必要があります。これは、ゲームのグラフィックコンポーネントであるインターフェイスによって行われます。ユーザーフレンドリーなインターフェースには、メニューと設定が必要です。



結局のところ、プレイするには対戦相手が必要です。プレイヤーがコンピューターと競争できるように、これらの目的のためにボットを作成することにしました。この場合、ボットの複雑さは調整可能である必要があります。

アプリケーションプラン：

1. ゲームロジック
   • 六角形のボードモデル
     
     六角形のセルの2次元配列として格納されます
   • ピースを移動するためのルール移動
     
     の有効性をチェックし、プレーヤーのために、ピースに使用可能なすべての移動を取得します
   • 移動履歴移動を
     
     元に戻し、やり直します
2. インターフェース
   
   計画2インターフェース：ncursesとQt。プロジェクトにはncursesのみが実装されています。詳細については、「インターフェース」セクションを参照してください。
   • フィールドの表示
     
     コンソールでのフィールドのレンダリングと更新
   • キーボードキーでカーソルを動かし、マウスなしで再生
   • 移動のテキスト履歴を表示する
   • メインメニューの表示
3. ボット
   • ランダムボット
   • 貪欲なボット
   • アルファベータボット
     
     すべての動きを繰り返すように最適化

それはどのように行われますか？

非常に単純化されたアプリケーションアーキテクチャは、次の図で説明されています。





ゲームセクションは、すべてのゲームロジックを担当し、ボードを保存します。



コンピューターを使用したゲームがオンになると、ゲームはボット



コントローラーからボットと対話し、ゲームからゲームに関するデータを取得して、プレーヤーに表示するためにインターフェイスに転送します。次に、インターフェイスは、ユーザーの操作の結果をコントローラーを介してゲームに返します。



コントローラー形式の中間リンクは、複数のインターフェースがある場合に役立ちます（当初、コンソールとグラフィカルの2つのインターフェースを作成する予定でした）。それらのすべては、それぞれが異なる方法で行うのではなく、コントローラーを介して均一な方法でゲームと通信します。

技術的な詳細

ゲームモデル

六角形のボード

上の図のゲームセクションを考えてみましょう。ボードを保存し、ゲーム内のすべてのロジックを処理する必要があります。



理解を深めるために、このアイデアを取り入れた記事を読むことができます。次の図に示すように、



ボード全体をセルの2次元配列に格納し、その要素は座標のペアによってインデックス付けされ(w,h)ます。このような座標の選択は自然に思えますが、形状の動きを説明するには不便です（たとえば、対角線に沿って移動するときに座標がどのように変化するかを観察してください）。





^{横軸wと縦軸に沿ったセルの座標h}



図の動きを説明するために、3次元座標を使用します。座標を持つ参照セルとしていくつかのセルを選択しましょう{0,0,0}（便宜上、(0, 0)配列のセルと一致します）。





^{座標中心細胞に対して細胞の三次元座標{0,0,0}}



「左、底まで右から」対角線に沿って変位座標で表されるx座標によって- 、下から上への変位をy「ボトムからトップへ、左から右へ」と対角線に沿った変位-座標によってz。隣接するセルに移動すると、対応する座標が1つ変化します。したがって、上の図のように、各セルは3つの座標を受け取ります。



この場合、セルにはあいまいな番号が付けられます。たとえば、座標{0,0,0}を持つ中央のセルから左下に移動してから上に移動すると、セルの座標が取得され{0,1,-1}ます。ただし、{1,0,0}前の図に示すように、中央のセルから直接アクセスすると、同じセルに座標があります。





^{セルの座標を指定するための別のオプション{1,0,0}。}



「左下」-「上」-「右下」のサイクルで任意のセルをトラバースすると、同じセルに移動しますが、その座標{-1,1,-1}にベクトルが追加され、その座標の合計はに等しくなり-1ます。同じ方向または反対方向に精神的にこのような歩行を数回実行すると、任意のセルの座標を同等の座標に変更できます。これは、ベクトル比例によって異なります{-1,1,-1}。あいまいさを取り除くために、各等価クラスで、座標のトリプルを代表として選択します。その合計はゼロに等しくなります。この座標の選択はユニークです（それを証明してください！）。



クラス内で2次元座標から3次元座標に、またはその逆に変換するためのアルゴリズムについてさらに説明しますPosition。

Position(int w, int h) //    
        : x_{-w/2 — w % 2 - h}
        , y_{w % 2 + 2 * h}
        , z_{w / 2 — h} {
}

int posW() const { //       
    return -x_ + z_;
}

int posH() const { //       
    return (x_ + z_ — (x_ + z_)%2) / 2 + y_;
}

コンストラクターは(x,y,z)、合計がゼロになる座標を生成することに注意してください。この場合、座標変換(x,y,z)の(w,h)座標のセットのために正しく動作は、（和はゼロである必要はありません）。



これらすべての式をどのようにして見つけましたか？科学的な突く方法による：2次元座標の1つが1（コンストラクター）によって反対方向にシフトされたときの3次元座標の変化を分析することによって（方法）。



3次元座標を使用すると、セルが同一直線上にあることを簡単に確認できます。たとえば、2つのセルが同じ対角線上zにあることを確認するには、これらのセルを接続するベクトルを見つけて、その等価クラスに次の形式のベクトルが含まれていることを確認する必要があります。{0, 0, z}..。Zは何でもかまいません-この数値はセル間の距離を示します。移動の正確性のチェックを実装し、移動に使用できるすべてのセルを見つけるのは非常に簡単です。



ボードを表す2次元配列に、図形の位置に関する情報を格納します。各セルにチェスピースがある場合は、そのタイプと色を保存します。



ボードクラスでの実装では、ピースのタイプのみをセルに格納します。このボード上のピースの可能なすべての動きを見つけて、動きの正確さをチェックできるクラスが必要です。

ピースの動き

FigureMoveValidatorフィギュアの種類ごとに6つの子孫を持つ クラスを作成しました（各メソッドでフィギュアの種類のスイッチケースを作成すると、子孫なしで実行できました）。クラスコンストラクタには、位置とボード参照の2つのパラメータがあります。また、クラスには2つのメソッドallMovesとがありcheckMoveます。



方法を考えてみましょうallMoves。すべての動きを見つけるために、可能な変位のベクトルの配列を作成し、それを通過してみましょう。一歩動くピースの場合、ボードから飛び降りたり、ピースのあるセルに落ちたりしていないことを確認する必要があります。複数のセルを直線で移動する図の場合、前の条件が通過する間に移動ベクトルを追加します。



今checkMove..。数字が同じ直線上にあるかどうかを確認する方法を知っていることを覚えています。この行に他の部分がないことを確認すると、ドミネーター（ルークのアナログ）の既製のメソッドが得られます。ピースが1つの直線上にある場合、それらの間の距離を見つけて、プログレッサー（ポーン）、ディフェンダー（キングのように歩く）、インテリジェンス（キング、カットできない）、リベレーター（1つのセルを通過して任意のセルに移動できる）のメソッドを取得できます。側）。現在のものから6つの方向に斜めにセルに移動するアグレッサ（象のアナログ）、依然として存在する（細胞から{0, 0, 0}の{0, 1, 1}へ、{0, 2, 2}などが、：以下の画像の灰色のセルを参照します）。この図では、座標の1つをゼロにして、残りの2つの座標の絶対値が等しいことを確認できます（3次元座標のおかげで）。





^{攻撃者に考えられる動き次に、その動きを}



どうするかを理解する必要があります。移動に必要なすべての情報を格納するMoveクラスを作成しましょう。2つの位置と4つのピースを保存することにしました。ピースが移動する位置、ピースが来る位置、およびこれらの各セルにどのピースが立っているか、移動を適用した後にどのピースが立つかに関する情報です。これにより、移動履歴システムと移動ロールバックの実装が簡単になります。

インターフェース

建築

アプリケーションはncursesコンソールライブラリに記述されています（ここにそのチュートリアルがあります）。このライブラリを使用すると、コンソールで疑似グラフィックを作成できます。たとえば、MidnightCommanderとNanoはそれに基づいています。



選択は非常に奇妙に思えるかもしれません。他にも多くのライブラリがあり、より美しく、便利で、クロスプラットフォームです。これは、当初、コンソールとグラフィカルの2つのインターフェイスを作成することを計画していたという事実に関連しています。プロジェクトが配信されるまでに2つのインターフェイスを作成することはできず、代わりにコンソールバージョンでより多くの機能を作成しました。アーキテクチャ上ではありますが、アプリケーションはさまざまなインターフェイス用に設計されています。ディスプレイとコントローラーの



2つの主要なエンティティがあります..。マッピングはプレイヤーに画像を表示し、コントローラーはさまざまなマッピングと内部ゲームモデルの間を仲介します。



ディスプレイは、カーソルの位置と動き、形状の選択、使用可能なフィールドの強調表示、ゲームの完了など、すべてのユーザー操作を処理します。ボードに影響を与えるアクションは、コントローラーを参照し、モデルとの間で必要な情報を送受信します。



ディスプレイは独自のバージョンのボードを作成しますが、カーソルの位置やセルの色など、必要な追加のパラメーターがあります。マッピングごとに必要なパラメータが異なるため、これらのパラメータをメインモデルに追加することはできません。たとえば、コンソールインターフェイスでは、図の選択と移動はマウスで行われるため、グラフィカルインターフェイスではなく、カーソルの位置を保存する必要があります。



プレイヤーが移動に使用できるフィールドを知りたい場合は、次のようになります。

1. プレイヤーはカーソルをフィギュアフィールドに移動し、スペースバーを押します
2. 形状のフィールドは選択済みとしてマークされます
3. インターフェイスはselectCell、コントローラー上のメソッドを参照します
4. メソッドselectCellはallFigureMoves、モデルのメソッドを指します
5. allFigureMovesFigureMoveValidator利用可能なすべての動きを計算する作成
6. allFigureMoves 見つかった転送はコントローラーに戻ります
7. コントローラはそれらをインターフェイスに渡します
8. インターフェイスはフィールドを再描画し、使用可能なフィールドを強調表示します

^{カーソルはボードの中央、つまり淡いブルーの正方形にあります。この位置に移動する前に、ユーザーは形状を選択しました。利用可能な移動は緑色で強調表示され、選択したセル自体は紫色で表示されます。}

フィールドはどのように描画されますか？

コンソールインターフェイスは、テキスト行のある長方形のウィンドウにレンダリングされます。シンボルを適切な場所に配置して色を付けると、次のような画像が得られます。





^{（「o」の文字で描かれた邪悪なパックマン）} ncurses



の関数move(int y, int x)は現在の位置を変更し、関数addch(chtype c)は文字を追加して現在の位置1を右にシフトします（x —> x+1）。



複雑な画像を2次元配列として保存し、1行ずつ表示できます。行が終了したら、現在の位置を次の行の先頭に移動します。原理はタイプライターと非常に似ています。



ユーザーのコンピューターでは、端末が色やその他のテキスト属性をサポートしている場合、ゲームのフィールドは色付けされます。



Ncursesを使用すると、開発者はテキストがコンソールに出力されるときにテキストの属性（色、太字、点滅）を変更できます。これを行うには、次のコードを記述します。

attron( *attributes* );
addch(c);
attroff( *attributes* );

各シンボルには、独自の色と背景色があります。最新のコンソールは最大256色をサポートしているため、限られたセットで作業する必要があります。カラーデザインの点で非常に悲しいです。



出力用の画像は、（最初​​に行ったように）コードに保存することも、プログラムの起動時に別のファイルに保存して読み取ることもできます。このために、独自のファイル形式を考え出しました*.btn。



ゲームが読み取って表示するテキスト画像を保存します。たとえば、形状、または「白が勝つ」/「黒が勝つ」という碑文、またはメニューボタン。この場合、以前に描画されたものを上書きしないために、透明性が必要になる場合があります。これを行うには、最初の行#と、出力で無視される「透過的な」シンボルのリストの後にハッシュを追加します。



たとえば、画面に3つの長方形が描かれているとします。





次のファイルから中央に長方形を追加します。

#C
AAAAAAAAA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
ACCCCCCCA
AAAAAAAAA

そして、次の図が表示されます。





^{（わかりやすくするために黄色で強調表示されてい}



ます^）この形式は、メニューを開発するときに特に役立ちました。

メニュー

ゲームには設定を含むメニューもあり、ゲームの開始前と終了後に描画されます。



メニューボタンはファイルから読み取られます*.btn。これらのボタンには、大きくて美しいテキストが必要です。ASCII文字を使用して美しく描画する方法はわかりませんが、ASCIIテキストをさまざまなフォントで表示するためのユーティリティであるfigletは次のことができます。





ボタンは、ファイルから読み取られたラベルを囲みます。





次に、それらは中央に配置され、順番に出力されます。





一部のメニューでは、失敗して、たとえば、ボットの複雑さと色を調整できます。





メニューシステムの設計で最も興味深い部分は、その要素を1つのシステムに結合することです。これは、マルチプレクサと呼ばれるシステムの別の要素によって行われます。この名前は、ターミナルマルチプレクサに由来しています。



マルチプレクサは、ユーザーが押したキーを受け入れ、現在表示されているすべてのメニューに送信します。各メニューは、キーをどう処理するかを自分で決定します。無視するか、何らかの方法で処理します。メニューの処理結果はマルチプレクサに返され、マルチプレクサは次に何をするかを決定します。メニューを閉じ、新しいメニューを作成し、設定を変更し、アプリケーションを閉じます...



このアプローチは私たちのニーズに便利であることがわかりましたが、一般的には十分ではないかもしれません。2つの異なるメニューが同じキーに反応し、ユーザーはどちらのメニューに反応するかを選択できるはずです。解決策は、さまざまなメニューを切り替えることができる特別なキーボードショートカットです。たとえば、tmuxのように。しかし、これはやり過ぎであり、必須ではありませんでした。

ボット

上記のように、私たちのゲームにはボットがあります。初心者にもベテランにも面白くしようと思いました。



ボットについて説明する前に、いくつかの実装の詳細について説明したいと思います。各形状に重みを割り当てました。大きいほど、この数字の価値は高くなります。式（白い部分の重量の合計）-（黒い部分の重量の合計）を使用して、ボード上の位置がどれだけ適切かを判断します。白がこの表現を最大化し、黒が最小化することは有益です。



動きのツリー全体を完全に計算するのは難しい作業なので、最初の数回の動きだけを計算しました（先を見据えて、6回先に計算されたことがわかりました）。ボード上の特定の深さのすべての状態を、トラバーサルツリーの葉と見なしました。



ゲームには3つの異なるタイプのボットがあります。

• RandomBot — . .
• GreedyBot — «» , , .
• AlphaBetaBot — , - .

最適化の実験を開始したとき、ボットのユニットテストなしでは実行できないことに気付いたので、AlphaBetaBot「a」の双子の兄弟を作成しましたOptimizedAlphaBetaBot。で最適化のすべてのアイデアをテストし、OptimizedAlphaBetaBotユニットテストは、2人の双子の兄弟が同じ有用な動きを見つけることを確認するのに役立ちました。RandomBotは、ボード上にランダムなパターンを生成することで、私たちに役立ちました。これを行うにはRandomBot、双方に数十回尋ねて行くだけで十分でした。



合計でOptimizedAlphaBetaBot 、3つの主要な最適化が実装されました（ここでは、ユーティリティの降順で示されています）。

• ロールバックの使用。この最適化の後、移動するためにボードを何度もコピーする必要がなくなりました。
• FigureKeeper, , . std::vector .
• std::unordered_map Zobrish hashing.

主要な最適化に加えて、より小さなものもありました。たとえば、並べ替える前に、特定の動きを考慮してボード上の位置のすべての値を計算する場合、複雑なオブジェクトを並べ替える必要Moveはなく、単にint'sを並べ替える必要があります。



当初、いくつかの評価機能を実装することが計画されていました。たとえば、敵に脅かされた人物は半分のコストで見積もられます。しかし、ボットは非常に「きれいに」再生され、いくつかのピースを失うことが判明したため、単純な量の方がより効果的であることが判明しました。



ただし、ボットアーキテクチャは、新しい評価機能の追加を引き続きサポートします。これを行うには、次の3つだけを定義する必要があります。

1. 与えられた図の配置について「ゼロから」コストを計算する必要がある場合に機能します
2. デルタ関数。特定の移動のコストをすばやく再計算する必要があります。
3. カスタムクラスのコンストラクターのこの関数セットの数FunctionSet。

ボットの戦いをオンにして、プロセスを見ることができます。





^{同じ難易度の2つのボットのゲーム（6つのうちレベル4）。カーソルはゲーム全体のフィールドの中央にあります}

結論

チェスに似たゲームを実装しましたが、ルールが異なり、ボードが異なります。私たちの実装には拡張の余地があります。Intellector自体も開発および変更されています。最近、ルールが更新されましたが、アプリケーションではまだサポートされていません。たとえば、最初の2ターンは中心線を越えることができなくなりました。



さらに、当初計画したさまざまな機能がありますが、プロジェクトの時点では実装できませんでした。たとえば、このアプリケーションでは、ネットワークゲームを見たいと思っています。また、たとえばQtのような優れたクロスプラットフォームインターフェイスは問題ありません。



おそらく、これの全部または一部が近い将来に現れるでしょう。それまで、読んでくれてありがとう！



Githubリポジトリ