チェッカーの遊び方を学んだマシン

チェッカー ゲームの歴史は 5,000 年以上あります。これは最古のボードゲームではありませんが、今日まで生き残っている最古のボードゲームの 1 つです。しかし、その名声は他人のものになります。たとえば、チェス、バックギャモン、あるいはリスクやスクラブルなどのより現代的なものです。しかし、ボードゲームにライバルがいるとすれば、チェスが主なライバルになるかもしれない。誰もがチェスのチャンピオンの名前を 1 人や 2 人挙げることができますが、実際にはチェッカーの世界チャンピオンを知っている人は誰もいません。さらに、人工知能を使用してチェスのプレイ方法を知っているコンピューターであるディープ ブルーについては誰もが知っていましたが、チェッカーのプレイ方法を知っているコンピューターであるチヌークについて知る人はほとんどいませんでした。

それは、ゲームのプレイを担当するコンピューター プログラムをホストするために使用されるマシンに関係している可能性があります。それはマーケティング キャンペーンが悪かったか、まったく行われなかった可能性があります。あるいは、選ばれたゲームであるチェッカーは、冷戦時代にロシアとアメリカのチェスプレイヤーの対立により非常に流行したボードゲームであるチェスほど人気が​​なかったということもある。

興味深いことに、世界チェッカーで 9 回チャンピオンになったマリオン ティンズリーは次のような言葉を残したと言われています。「チェスは広い牧草地を見渡すようなものです。」一方、「女性は深い井戸を覗いているようなもの」です。それでは。 Chinook プログラムはそのことをよく調べて、チェス分野で Deep Blue が勝利する前に、ワールド チェッカー トーナメントで優勝することに成功しました。彼はどうやってそれができたのでしょうか？

優勝したプログラム

Chinookと名付けられたこのプロジェクトは、1989 年に米国のアルバータ大学で始まりました。公式ウェブサイトで説明されているように、その目的は、女子の世界チャンピオンに勝つことができるコンピュータープログラムを開発することでした。人工知能かそれに近いものを介して。否や言うほどない。 1990 年、Chinook は、ワールド カップへの参加が認められた、あらゆる種類のゲーム用の最初のコンピューター プログラムでした。今回の場合はレディースワールドチャンピオンシップです。それは贈り物ではありませんでした。その権利を獲得するには、マイナーだが非常に重要な大会である全米選手権で2位になる必要があった。

そして、彼には自分をサポートしてくれるゴッドファーザーも必要でした。予想通り、イギリス婦人協会とアメリカ婦人連盟は、原則として人間のためのトーナメントに機械、あるいはむしろコンピュータープログラムが参加するという考えを好まなかった。有名なチェッカー選手であるマリオン・ティンズリーでなければならず、もしチヌークの出場が許可されなければ世界チャンピオンのタイトルを放棄することになるだろう。

ハリウッド映画ではよくあることだが、1992年の初出場では負けた。しかし、1994年に彼はチャンピオンシップを獲得しました。正確に言えば、どちらの決勝でも、チヌークのライバルはマリオン・ティンズリーその人であり、1992年には4対2で勝ったものの、2年後には負けることになった。実際、彼は負けていませんでした。彼は健康上の理由から引退しなければならなかった。 1週間後、彼は膵臓がんと診断され、それが原因で7か月後に死亡した。それにもかかわらず、チヌークは女子世界チャンピオンに輝いた。人工知能先史における画期的な出来事。

そして1995年、彼は自分の称号が賜物や幸運によるものではないことを世界に示すことができた。チヌークはドン・ラファティと32チェッカーゲームで対戦した。最終的には、マシン、というよりはコンピューター プログラムが 1 試合 31 引き分けで勝利しました。この勝利の後、チヌークの作成者は 1996 年に彼を競技会から引退させ、トーナメント以外でも対立はあったものの、プライベートでプログラムの改善に専念することに決めました。たとえば、ラファティはチヌークに対して 8 回勝ち、7 回負け、109 回引き分けました。

マシン内部のアルゴリズム

Deep Blue プロジェクトは、人工知能の歴史の中で最も重要な瞬間の 1 つを主導しました。それは、自ら学習し、進化し、最終的にはチェスのような複雑なゲームに勝つことができる機械、またはコンピューター プログラムでした。正確に言えば、このプログラムを実行するには強力なマシンが必要でした。 IBMワークステーションRS/6000 には、独自の VLSI チップも含まれていました。 1997 年に 11.38 gflops の処理速度を達成した堂々たる巨体。実際には、当時のスーパーコンピューターです。

代わりに、Chinook はアルゴリズムベースでした。それは、当時のどのマシンでも実行できるコンピューター プログラムでした。まあ、それも違います。 1992 年には、8 つのプロセッサと 256 MB のメモリを搭載したシリコン グラフィックスコンピュータ 4D/480 が使用されました。この種の中で最も強力なものの 1 つであり、ジュラシック パークの最初の作品に登場しました。 Chinook の責任者は、指揮を執る Jonathan Schaeffer、アルバータ大学の研究者である Rob Lake、Paul Lu、Martin Bryant、Norman Treloar でした。その後、他の研究者も加わりました。具体的には、Chinook には、開始の手を含むデータベース、検索アルゴリズム、手を評価する関数、およびゲームを終了するために考えられる手を含む別のデータベースが含まれていました。

しかし、この技術的な詳細は、Chinook プロジェクトの成果を損なうものではありません。チェッカーをプレイして、世界チャンピオンを含むどんな相手にも勝ちましょう。 1996 年には、世界選手権で人間に勝った最初のコンピューター プログラムとしてギネスブックにも掲載されました。 1 年後に人工知能を使用してこの偉業を達成したディープ ブルーよりも前です。そして、Deep Blue プロジェクトは Chinook の 4 年前、1985 年にChipTestという名前で始まりました。

そして、女性の複雑さを理解するために。シェーファー氏と彼のチームが 1989 年に初めて Chinook をプログラムしたとき、4 つのピースでゲームを終了するためのデータベースには 700 万のポジションがありました。翌年、これは 250 万の異なる位置から開始する最大 6 つのピースでゲームを終了するように拡張されました。そして 1994 年には、チヌークが最大 8 個の駒でゲームを終了できるように、444,000 万の局面のデータベースを作成できるようになります。

このプロジェクトは公式競技会からは撤退しましたが、継続的に改良が続けられました。 2005 年には、エンドゲーム データベースが 10 個のエンディングで拡張されます。可能なポジションは 390 億。つまり、39 の 10 の 12 乗です。そして、ついに 2007 年に、彼らは完璧を達成します。同点につながる完璧なプレーで試合を解決します。これを行うには、チヌークは 500 の 10 の 18 乗を分析する必要がありました。英語では 500 quintillion、スペイン語では 500兆として知られています。

人工知能の遺産

忘却の彼方、あるいは多くの人に知られていないものの、チヌーク プロジェクトは完全に消滅したわけではありません。この研究は1989年に始まり、チェッカーで世界チャンピオンを破り、完全試合を達成した後、2007年に終了した。これを記録するために、アクセスできるページを作成しました。プログラム自体が使用するデータベース、研究の結果として出版された出版物などを編集します。

何よりも、アルバータ州に行かなくても、自分でチヌークに挑むことができます。 Web ブラウザからチェッカーをプレイできます。まあ、実際には、これはチヌークの簡易版です。担当者いわく「同点チャンスを与えるために威力は抑えられている」という。彼を倒すのはさらに難しいですが、 3 つのレベルから難易度を選択できます。白か黒のどちらでプレーするかを選択することもできます。

チヌークと対戦するには、私たち側にもある程度の努力が必要です。最近では一般的なインタラクティブグラフィックボード上でチェッカーをプレイするのではなく、付属のイラストとマス目の数を参照して、実行したい手の組み合わせを選択する必要があります。各ターンで、リストから可能な動きの 1 つを選択し、 「Submit Move」をクリックする必要があります。プログラムは即座に動き始めます。など、ゲームが終了するまで続きます。

そしてプロジェクトの話に戻りますが、チヌークの最も目立つ顔である研究者兼教授のジョナサン・シェーファーは、現在もアルバータ大学で教鞭と研究を続けています。さらに、MOOC タイプのインタラクティブな教育コンテンツの作成に特化した非営利団体Onlea を運営しています。そして、人工知能の分野では、チェッカーをプレイするだけにとどまりませんでした。 90 年代から 2007 年まで、彼はポーカーのプレイに特化したコンピューター プログラムまたはボットであるPolaris と呼ばれるプロジェクトに参加していました。彼の成功は大きく、2007 年の夏には 3 人のプロと対戦したことで世間に知られるようになりました。 1勝1引き分け2敗を経て、2008年に6人のプロ選手と対戦し勝利した。