[Sittuyin]


Checkersとコンピューター

第二次世界大戦前から、Checkersは数学者の研究対象として注目されていました。
現代計算機科学の父 Alan Turingも、Checkersの基本プログラムを書きました。当時はコンピューターの能力が十分でなく、このプログラムには紙と鉛筆で計算しなければなりませんでした。

1950年代に入ると、そのころコンピュータ技術の進歩とともに揺籃期を迎えた人口知能研究分野で、CheckersはゲームAIの研究対象としてとりあげられました。 Checkersの最初のコンピューター・プログラムは、1951年、後年オクスフォード大学Programming Research Groupにてdirectorに就任する、C. S. Stracheyによってかかれました。このプログラムは、AIプログラムとして最初の成功例となりました。

人工知能研究のパイオニアでIBMの研究員であったArthur Samuelは、1952年にCheckersのプログラムを書き、プログラム同士を対戦させて勝者を残す、というプロセスを繰り返してこのプログラムを強化しました。SamuelはCheckersの研究を通じて、「経験を学習する」コンピューター・プログラムを実現したのです。 このプログラムは1962年に、公開試合でコネチカット州のチェッカー・マスターに勝利しました。

しかし、SamuelのこのAI研究史においての偉業が当時の研究者たちに「Checkersは完全解析された」という印象を与えたためか、それから25年もの間、Checkersというゲームは、研究者たちからほとんど注意を払われることがありませんでした。

コンピューターの性能の飛躍的な向上によって、Checkersプログラムの能力もまた、大きく発展します。

1989年、University of AlbertaのJonathan Schaeffer率いるチームによって、Chinookというプログラムがつくられました。 1992年、Chinookとの戦いに一度は勝利したMarion Tinsley(1955-1962, 1975-1991 のワールドチャンピオン)は、1994年の再対戦では途中で病に倒れ、まもなく亡くなったため、対戦結果はChinookの勝利となりました。 1995年、ChinookはDon Laffertyと対戦、1勝31引き分けという結果で、タイトルを守りました。1996年、ChinookはUSAナショナル・トーナメントで今までなかったような大差で勝利を収め、これを最後に「現役」を引退しました。 以来、人 vs. コンピュータの対戦はおこなわれていません。

1997年、Chinookは人間のチャンピオンに勝った初のコンピュータプログラムとしてギネスブックに記載されました。

2007年7月のサイエンス・マガジンでChinookの開発者は、プレイヤーが互いにミスを犯さなければ「負けない」(勝てないまでも常に引き分ける)ところまで、Checkersは解明されたと発表しました。 研究のピーク時には200台ものコンピューターを使い、初期配置から高々10個の駒が盤面に残った状態からのデータベース*1に至までの1014個の計算を作りました。その結果、18年の歳月をかけて、 5×1020 の探索空間を解析したことになります。

プレイヤーが不完全な手をさした場合も含めた解析はまだ完了していませんが、Checkersは2009年7月時点で、数学的に「解決」された、もっとも大きなゲームの探索空間を持つゲームです。


以下、書きかけの項目です

Deep Blue vs. カスパロフ

参考文献/bit別冊 ゲームプログラミング 第2章 チェス チェスマシンDeep Blueから学んだ教訓にDeep Blueプロジェクトに関わったFeng-hsiung Hsu氏による資料が掲載されています。

1996 Deep Blue 敗戦

Deep Blueの構造

1997 Rematch

The Game is Over

GAME OVER:

Deep Blue vs. カスパロフ (本)

カスパロフの主張

将棋世界

おわりに

SEE ALSO

Feedback

選択肢 投票
おもしろい 0  
役に立つ 0  
興味ない 0  
理解できない 0  
やってみたい 0  
食べてみたい 1  

*1 MASG解釈: おそらく、この研究前に残り駒10個からのEnding Game Databaseの作成が完了していたのではないでしょうか。

TOP   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS   [Privacy Policy]  
Last-modified: 2014-12-23 (火) 02:38:14 (1454d)