コンピュータ アリマア

各プレイヤーがゲーム開始時に駒を配置できる方法の数は、以下のとおりです。

${\displaystyle {\dbinom {16}{8}}\cdot {\dbinom {8}{2}}\cdot {\dbinom {6}{2}}\cdot {\dbinom {4}{2}}\cdot {\dbinom {2}{1}}\cdot {\dbinom {1}{1}}=64{,}864{,}800}$

プレイヤーは、16個のマス目にウサギを8匹配置し、残りの8個のマス目に猫を2匹、残りの6個のマス目に犬を2匹、残りの4個のマス目に馬を2頭、残りの2個のマス目のうちの1つにラクダを1頭、そして最後の未使用のマス目に象を配置することができる。

各プレイヤーは64,864,800通りのオープニングセットアップのうちの1つでゲームを開始できるため、オープニングの総状態空間は次のようになります。

$64,864,800² 約 4.2 × 10¹⁵$

クリスト＝ヤン・コックスが修士論文で述べたように、可能な初期状態の数が非常に多いため、「オープニングムーブの完全なデータベースを開発することは非常に困難である」^{[ 3 ] [ 4 ]。}

コンピュータが盤上の駒の価値を評価できることは重要です。そうすることで、駒の捕獲や交換が望ましいかどうかを判断できるからです。駒の相対的な価値を評価することは、Arimaaの研究が継続的に行われている分野です。現在使用されているシステムには、DAPEやFAMEなどがあります。

Arimaaをプレイする人工知能プログラムの一部または全部は、以下の技術を使用しています。

• ビットボード
• 転置表
• ゾブリストハッシュ
• ミニマックス法とアルファベータ法による枝刈り
• 必殺技と反論表
• 静的評価関数
• 静止状態探索
• モンテカルロ木検索
• UCT

• オープニングブック
• エンドゲームテーブルベース

最も単純なチェスプログラムは、総当たり探索と、駒の配置状況を重視した静的な局面評価を組み合わせています。これらのプログラムは、非常に多くの可能な手を検討しますが、一方の駒が他方より多くない限り、一連の指し手の最後にどちらが勝つかを判断する能力は（人間と比べて）劣ります。Arimaaプログラムも同様ですが、実際の結果はあまり良くありません。

Arimaa に総当たり探索を適用すると、探索の深さは各プレイヤーが各ターンに持つ膨大な数の選択肢によって制限されます。計算上、プレイヤーが利用できる選択肢の数は、プレイが進むことができる異なる経路の数を決定します。これは分岐係数として知られています。チェスのゲームにおける平均的な分岐係数は約 35 ですが^{[ 5 ]} 、 Arimaa では約 17,000 です^{[ 6 ] 。}

これらの分岐要因の違いは、チェスでは各プレイヤーに対して8ターンの深さまで探索できるコンピュータでも、アリマーでは各プレイヤーに対して約3ターンの深さまでしか探索できないことを意味する。

$35⁸ 約 17000³$

チェスソフトウェアにおける総当たり探索の深さは、アルファベータ枝刈りによってほぼ2倍になります。アルファベータ枝刈りでは、ソフトウェアは弱い手のすべての可能な継続手順を調べることなく、ある手が別の手よりも優れていると結論付けることができます。相手が1回の応答で特定の手を圧倒できる場合、他の応答を調べる必要がないため、探索速度が劇的に向上します。しかし、Arimaaでは、手番は4ステップごとにしか切り替わらないため、ステップベースの探索で使用できるカットオフの数が減少します。

さらに、アルファベータ枝刈りの有効性は、手を検討する順序に大きく依存します。悪い手を無視するためには、良い手を悪い手よりも先に検討する必要があります。特に、チェックと捕獲の手は、他の手よりもはるかに優れていることが多いため、枝刈りの鍵となります。Arimaaソフトウェアでは、捕獲が少ないため、アルファベータ枝刈りによる高速化効果は小さくなります。arimaa.comで行われるレーティングゲームでは、チェスの手のうち捕獲につながるのは約19%であるのに対し、ステップのわずか3%しか捕獲につながりません。

アリマーのほとんどの局面、特に盤面がまだ混み合っているゲーム序盤では、熟練したプレイヤーは次の2ターン以内に駒を失うことを回避できます。チェスと比較すると、アリマーではどちらのプレイヤーも駒の奪取をより長く遅らせることができます。実際、チェスでの最初の駒の奪取の平均的な手数は6ターン目ですが、アリマーでは12ターン目です。アリマーでは、序盤の攻防はより局面的なものとなり、将来のある時点で駒の奪取が避けられない状況を作り出すことに重点が置かれます。これは、非物質的な方法でどちらが優勢になっているかを正しく判断することの重要性を高めます。したがって、コンピュータプログラムの強み（何百万もの局面を分析できること）は、弱み（どちらがより多くの駒を持っているかという観点以外で局面を判断できないこと）ほど重要ではありません。

Arimaa プログラムの序盤における弱点は、セットアップ段階でさらに顕著になります。チェスでは、どのゲームも同じ局面から始まります。チェス プログラムは、ゲーム開始前にすべての標準的なオープニングの動きに対する定型的な応答のリストを作成することで、「考える」前に 12 手以上もの優れた手を指すことができます。人間も同様のことをしますが、オープニングに関する記憶はより小さく、信頼性も低いため、チェスでは相対的に不利になります。一方、Arimaa は、最初の駒が動く前から駒を配置する方法が何百万通りもあります。このため、プログラムには意味のあるオープニング ブックが存在しません。

ゲームが進むにつれて、駒の交換やウサギの前進によって局面はよりオープンで戦術的なものになりがちである。Arimaaプログラムは、人間が見落としがちな戦術的な一手を見抜くことができるため、このような局面では通常より優れたプレイを見せる。しかし、人間は保守的なプレイによってオープンな局面を避け、コンピュータが苦手とする戦略的な局面を狙うことが一般的に可能である。保守的な相手に対してArimaaで局面を崩すのはほぼ不可能だが、チェスでは単に難しいだけである。防御的なプレイに勝つには、小さな長期的な優位性を積み重ねる必要があるが、これはプログラムがあまり得意としないことである。

コンピュータチェスで使われている技術で、Arimaaには適用されないものの1つに、エンドゲームテーブルベースがあります。マスターレベルのチェスゲームでは、キングとナイト対キングとルークのように、駒が数個しかない不明瞭なエンドゲームに陥ることがあります。逆算分析によって、このような局面すべてにおける正しい手を網羅したテーブルを作成することが可能です。プログラムは、このような局面では新たに「考える」のではなく、事前に生成されたテーブルを参照するだけで済むため、人間に対して相対的に有利になります。一方、Arimaaではエンドゲームになることはめったにありません。駒の等価交換はチェスほど一般的ではないため、Arimaaのゲームで「駒の交換」が続いても不明瞭なままになることは稀です。Arimaaの平均的なゲームでは駒の取り合いはわずか8回（チェスでは17回）で、トップレベルの人間は、例えば2014年のチャレンジマッチの第2ゲームのように、駒を1つも失うことなくトップレベルのプログラムにArimaaで勝つことがよくあります。捕獲密度が低いもう一つの例は、2012年世界選手権の準決勝戦で、ゴールを強制する象の犠牲というたった1回の捕獲しかなかった試合である。

オマール・サイードは、従来の人工知能技術がアリマーに対して中程度の効果しか発揮しないため、プログラマーは強力なアリマー対戦プログラムを作成するために新しい人工知能技術を使用せざるを得なくなるだろうと期待している。世界選手権レベルのチェスプログラムを構築するという成功への探求は、ゲームをうまくプレイするための多くの技術を生み出したが、より一般的な推論にはほとんど貢献していない。実際、チェス対戦プログラムの技術は、人工知能の定義から除外されている。アリマーの目標は、アリマーのプレイに関わる技術が、人工知能のより大きな目標に役立つことである。

サイード氏が主催する人間対機械のチャレンジは、ハードウェアの進歩ではなく、AIソフトウェアの進歩を称えることに重点を置いている。毎年開催されるこのチャレンジでは、サイード氏自身が選定・提供するマシン上でプログラムが実行される。その基準は、一般的な安価な市販の家庭用コンピュータであることだ。このチャレンジは、トップレベルのチェスプレイヤーに挑戦する際に使用されるような高価なマルチプロセッサマシンを必要とする人には参加資格がなく、ましてやカスタムメイドのスーパーコンピュータ「ディープ・ブルー」のようなものではなおさらだ。もっとも、このハードウェア重視のアプローチの成功こそが、アリマーの発明のきっかけとなったのだが。サイード氏は、2004年のチャレンジで使用されたコンピュータ（Pentium 4 2.4GHz  、RAM 512MB）でさえ、適切なソフトウェアさえあればチャレンジ賞を獲得するのに十分なハードウェアを備えていたと考えている。スーパーコンピュータは、従来のAIソフトウェアを用いて力ずくでアリマーを打ち負かす能力を既に持っているかもしれないし、ハードウェアが現在のペースで進歩し続ければ、いずれはパーソナルコンピュータも同様の能力を持つようになるだろう。そのため、アリマーチャレンジ賞は当初、2020年までの期間限定で提供されていたのです。