アリマア
アリマア (Arimaa) は、チェスの盤と駒を使用してプレイすることができる2人用のボードゲーム。子供でも理解できる簡素なルールでありながら、各局面で指せる手の数を何千通りにもすることでコンピュータによる計算を困難にしていることが特徴。元NASA職員であるオマール・サイド(Omar Syed) が考案し、2002年11月20日に発表した。当時小学生であったオマールの息子アーミル (Aamir Syed) も、開発に大きな役割を果たした。「Arimaa」という名称は、Aamirのスペルをひっくり返し(rimaa)、先頭にaを付け加えたものである。
このゲームを生み出す動機となったのは、チェスの世界チャンピオンと互角に戦うことのできるコンピュータソフトの出現である。世界のトップレベルに到達したことでコンピュータチェスは一応の目標を達成したといえるが、アリマアでは可能な手を端から検索するなどいわば「力業」ともいえる従来の方法は通用せず、強いアリマアプログラムを作成するためには違ったアプローチが必要になると考えられる。そもそもコンピュータのように早くも正確でもなく、膨大な定跡データベースも持つことができない人間の思考能力でコンピュータと対等に戦えるという事実は、いまだ知られていない斬新で強力なアルゴリズムが見つかる可能性を示唆している。人間どうしが行うゲームとしても十分に遊べるものであるが、人間と（人間が書いた）プログラムとの対戦で真価が発揮されるゲームである。
オマールは2020年までにアリマアで人間を打ち負かすプログラムを開発した者には1万ドルの賞金を支払うと宣言している。2004年に行われたゲームでは、世界最強のアリマアプログラムは0勝8敗でオマールに完敗した。このプログラムは囲碁九路盤限定チャンピオンになったプログラム「Many Faces of Go」の開発者であるデイビット・フォットランド (David Fotland) によって書かれたものである。2014年までは人間がコンピュータを退けてきたが、2015年、David Wu が開発したプログラム「Sharp」が人間を7勝2敗で破り、賞金が支払われた。
ゲーム理論上では二人零和有限確定完全情報ゲームに分類されるため、完全な先読みは理論的には可能である。