ゲームScrabbleの移動生成アルゴリズム

こんにちは、Habr！

この記事では、スクラブルのゲーム用に人工知能をどのように作成したかについて説明します。 カットの下の詳細。

スクラブル

スクラブル-世界的に有名なゲームの国内類似品スクラブル-2〜4人でプレイできるボードゲーム。競技場で文字から単語を並べます。 競技場は15 x 15、つまり225セルで構成され、ゲームの参加者はその上で単語を構成します。 構成された各単語は、フィールドの文字とセルの値に応じてポイントを獲得します。

Scrabbleゲームフィールドは次のようになります。


図1.ゲームのフィールド

基本的なルール

通常、ルールはゲームの開始前にプレイヤーによって交渉されますが、ゲームには一般的に受け入れられているルールがいくつかあります。

• ゲームの開始時に、各プレイヤーには7つのチップが与えられます。 いくつかの単語を一挙に入力できます。 新しい単語はそれぞれ、以前にレイアウトされた単語と接触している必要があります（共通の文字がある）。 単語は、左から右に水平に、上から下に垂直にのみ読み取られます。
• プレーヤーが1つの単語を望んでいない、またはレイアウトできない場合、プレーヤーは任意の数の文字を変更する権利があるため、移動をスキップします。
• プレイヤーが1ターンあたり7つのチップすべてを使用した場合、追加の15ポイントが与えられます。
• 各動きのポイントの合計は、構成された文字のポイントの合計と、ボーナスセルに文字を配置するために受け取ったボーナスで構成されます。
• 文字のプレミアムセル：緑色のセルの二重、黄色のトリプルにある文字のグラス。
• 単語のプレミアムセル：単語の文字の1つが青色のセルにある場合、単語全体の合計ポイントは2倍、赤色-トリプルになります。

最初のステップ

動きを生成するアルゴリズムを開発する前に、フィールドに配置できる単語と場所を理解する必要があります。 これを行うには、フィールドですべての可能な単語を水平に構築する方法を見つけるだけで十分です-垂直構造は同じ方法で取得されます。

2つの定義を紹介します。
単語の接頭辞は、単語の最初の文字で始まるが最後の文字を含まない、単語の連続した文字のセットです。

単語の接尾辞は、単語の最後の文字で終わる単語の連続した文字のセットで、最初の文字は含まれません。

アンカーポイント

図2.問題の行

上の図に描かれているシリーズを検討してください。 このシリーズで作成できるすべての単語を見つける必要があります。 ゲームのルールに従って、すべての単語には行からの既存の文字を含める必要があります。 次に、単語を形成できる場所は、すでに占有されているセルに隣接する空のセルです。 これらのセルをアンカーポイントと呼びます（英語acnhor ）。 この行には5つのアンカーポイントがあり、次の図で赤で強調表示されています。


図3.アンカーポイント

すべてのアンカーポイントが見つかったら、単語を形成するアンカーポイントのプレフィックス文字の可能な数を見つける必要があります。 アンカーポイントの左側のセルが占有されている場合、作成中の単語のプレフィックスの一部として使用されます。 この場合、プレフィックス文字の可能な数は固定されています。 このセルが空の場合、プレフィクスはプレイヤーの文字から形成され、プレフィクスの文字数は、空でないセルまたは左に最も近いセルのアンカーポイントまでの距離によって制限されます。


図4.プレフィックス文字の可能な数

行の単語を見つけるためのアルゴリズム

アンカーポイントである各セルについて、次のようにすべての可能な単語を探します。

1. 特定のアンカーポイントに関連付けられた、アンカーポイントに指定されたプレフィックス長の可能性を満たすプレフィックスをすべて検索します。
2. 上記の段落で見つかった各接頭辞について、接頭辞とともに辞書から単語を形成するすべての適切な接尾辞を見つけます。 接尾辞は、プレイヤーの文字または既にフィールドにある文字を使用して作成されます。

単語の接頭辞には、プレイヤーの手からのセルか、既にボードに配置されているセルが含まれますが、同時には含まれません。

これで、フィールド上のすべての単語を見つける方法ができたので、ムーブを生成するアルゴリズムの説明に直接移動できます。

ストローク生成アルゴリズム

3つの移動生成アルゴリズムを選択しました：最大値選択アルゴリズム、徹底的な検索方法、およびアルファベータクリッピング方法。

最大値選択アルゴリズム

メソッドの各反復で、残りよりも多くのポイントをもたらす単語が検索されます。 この単語を見つけた後、フィールドに配置され、あるステップで見つかった単語のセットが空になるまで、手の中の新しい位置と新しい文字のセットを再び検索します。

このアルゴリズムの主な問題は、結果として生じる単語のセットが、もたらす位置の数の観点から、この位置で必ずしも最良の動きになるとは限らないことです。

フルブルートフォース法

動きを生成する2番目の方法は、徹底的な検索です。 完全検索は、あらゆる種類のオプションを使い果たすことで解決策を見つける方法です。 最初に、この位置のフィールドで構成できるすべての単語が検索されます。 次に、この単語をフィールドに配置することによって取得された手の新しい位置と新しい文字ごとに、前の手順が繰り返されます。 これは、構成されている単語の多くが空になるまで続きます。
メソッドの動作の結果として、プレーヤーがこの位置で行えるすべての可能な動きが考慮されます。 これらの動きの中で、最も多くのポイントを与えるものが選択されます。

この方法の主な問題は速度です。 メソッドの速度を上げるために、手に単語を配置するときに繰り返される位置と文字を記憶する、つまり動的プログラミングを使用することができます。

アルファベータクリッピング法

ミニマックスは、プレイヤーの最悪のシナリオに従ってイベントが発生したときに防止できない損失を最小限に抑えるための意思決定ルールです。 この方法の改善点は、その変更-アルファベータクリッピング方法です。 アルファベータクリッピング方法は、この分岐の評価関数の値が前の分岐で計算された値よりも悪いことが判明した場合、検索ツリーの分岐の評価を早期に停止できるという考えに基づいています。

メソッドのアルゴリズムは次のとおりです。最初に、この位置で可能なすべての動きが検索されます。 次に、結果の位置について、新しい位置での敵によるすべての可能な動きが検索されます。 これらのアクションは、初期位置の分析の深​​さと同じ回数だけ繰り返されます。 結果の位置ツリーで、プレイヤーと対戦相手のポイントの差が最大になるように移動が求められます。

この方法の主な欠点は、ほとんどのゲームで相手の文字が不明であることです。 したがって、このアルゴリズムを使用するのは、ゲームの最後にのみ意味があります-プレイヤーの手にある文字を除くすべての文字が使用される場合。

結果

実装には、Javaプログラミング言語を使用しました。 辞書は12,000語で構成され、プログラムは通常のSet'aの形式で提示されました。

平均生成時間を次の図に示します。

図5.生成時間チャート

調査サンプルには、プレーヤーに表示される文字の100の異なるシーケンスが含まれていました（スタックの原則に従って）。 その結果、手と位置の文字の約1,500の異なる組み合わせが調べられました。

ただし、生成時間の増加にはポイントの損失が伴います。平均で最大値を選択するアルゴリズムにより、プレーヤーは約30ポイント、残りのメソッドは約60ポイントになります。

藤堂

残念ながら、以下の点は考慮から除外されました。

• まれな文字の組み合わせ分析
• 移動後に残っている文字の分析
• さらなる敵の行動の分析
• ストロークをスキップするときに変更する文字

基本的に、最初の2つの段落は、「 E 」や「 b 」など、できるだけ早く珍しい文字を使用することと、母音とプレーヤーの子音のバランスを維持することに基づいています。 敵の行動の分析には、ボーナスセルを通過する動きを防ぐ試みが含まれます。 上記の点を検討すると、アルゴリズムが改善されるはずです。

文学

• スクラブルに関するピーター・ノーヴィグによる講演 。 このソースから最も多くのアイデアが借用されています。
• ゲームのルール
• 完全なウィキ列挙
• グレートトーマスコーメン：アルゴリズム。 構築と分析。
• アルファベータクリッピング

ご清聴ありがとうございました！