コンピュータ将棋
コンピュータ将棋(コンピュータしょうぎ)は、コンピュータによる将棋の対戦、また将棋を指すコンピュータおよびそのプログラムそのものである。
コンピュータ将棋のプログラミング技術・課題
- ミニマックス評価
- チェス、将棋、オセロ、チェッカー等の完全情報ゲームで次の手を決めるための基本アルゴリズム。数手先まで読み、その時点で評価関数により局面に点数(手番の方がプラス)をつけ、手番の方は評価値が最大の手を、手番ではない方は評価値が最小の手を選ぶとして、次の着手を選択する。
- 局面の分岐数を N、先読みする深さを L とすると、評価が必要な局面数は N^L となる。
- 評価関数
- コンピュータ将棋のプログラムは、コンピュータチェスの手法を真似て評価関数という方法論を採用する。数手先の変化を読み、相手が最善を尽くしてきたときに、もっとも自分が有利になる手を探すのである。ここでいう「有利」は、相手の玉を詰ませられる、駒得になるなど、数値化させやすい基準で評価するものが多い。ここでの数値化の方法が評価関数であり、評価関数の作り方と何手先までを評価の対象とするかでコンピュータ将棋の強さが決まってくる。駒の損得を中心に、玉形や駒の働きなどを評価対象としているものが多い。近年、自動学習による評価関数作成の手法が主流になりつつあり、Bonanzaはこれによって開発者の棋力とは無関係にエンジンを強化できる様になった。
- 探索
-
- 枝刈り
- 将棋の場合、平均着手可能手数は80もあるので、L手先までの局面数は 80^L という膨大な数になる。これを全て計算すると限られた時間内では深く先読みすることはできなくなる。そこで、枝刈りという手法を用い、実際に計算する局面数を少なくし、深く読めるようにすることを枝刈りと呼ぶ。
- 枝刈りには全局面を評価した場合の結果と正確に同じ値を返す枝刈りと、少し誤差を含む結果を返すことを許容することでより多くの枝刈りを行うものの二種類がある。前者を後ろ向き枝刈り、後者を前向き枝刈りと呼ぶこともある。
- αβ(アルファベータ)探索
- 再帰的に局面の評価を行う関数を呼ぶときに、その時に判明している評価値の下限値(これをα値と呼ぶ)と上限値(これをβ値と呼ぶ)を引数として渡し、ミニマックス評価に於いて途中で得られた値がα値β値の範囲外の場合は評価を打ち切るアルゴリズム。
- ミニマックス評価で評価する局面数は N^L だが、αβ探索ではおよそ N^(L/2) となる。
- 全幅探索
- ある局面下で指すことが可能な手をしらみつぶしに読む手法(力まかせ探索)。探索法としてはもっとも原始的だが、従来まではうまくいかないと言われていたが、Bonanzaはあえてこの方法を選択している(開発者によれば、この方がCPUの負荷が低いという。後に一部選択探索を取り入れた)[要出典]。
- 実現確率探索
- 激指が得意とする手法[要出典]。プロ棋士の大局観(ある局面を見てすぐに形勢判断ができ、直感的に急所の手がわかる)をコンピュータにおいても再現し、絞り込んだ手だけを読む。
- 合議制
- 近年[1]、複数の思考エンジンを用意して、エンジン間の合議(多数決)によって指し手を決める手法が研究されている。2009年に行なわれた第19回世界コンピュータ将棋選手権では、複数のBonanza[2]を搭載した「文殊」が3位と言う好成績を収めた[3]。
- 水平線効果
- 小さな損を繰り返すことで、大きな損をする状態を先延ばしにし、本来よりももっと不利になってしまうこと。
- この問題は現在でも解決されたとは言えないが、10数手の先までの深い読みが可能になったことにより、致命的な水平線効果は現れることはほとんど無くなった。
歴史
黎明期
将棋は二人零和有限確定完全情報ゲームに分類されるため、将棋を指すプログラムを作る、いわゆるコンピュータ将棋は、人工知能の一分野として開発が進められた。チェスやオセロ(リバーシ)などのボードゲームでも同様の開発が進んでおり、日本国内だけの普及にとどまっている将棋はむしろ後発であった。「人間が考えるように考える」という人工知能としての方法論はすぐに行き詰まる。人間の持つ大局観をコンピュータが理解できる情報に落とし込むことが非常に困難であったためである。
コンピュータ将棋の開発が始まったのは1970年代中ごろと言われている。当時、人工知能の研究をしていた早稲田大学の瀧澤武信教授(現コンピュータ将棋協会会長)をメインプログラマーとするプロジェクトチームによって、1974年11月から開発が進められ、翌1975年5月に完成したものが、おそらくは世界で最初のコンピュータ将棋であり[4]、2010年に情報処理学会が日本将棋連盟に渡した挑戦状にも、この年を起点とした「35年」という開発の歴史の年数が記されている。コンピュータ将棋のゲームソフトが市場に出回ったのは1980年代のことである。当時はハードウェアの性能も低く、評価関数も簡単なものであったため、人間に比べて非常に弱いプログラムであった。アマチュアの級位者レベル以下であったことは間違いなく、そのような級位はないが20級程度といわれていた。
世界コンピュータ将棋選手権
1980年代後半には、多数のコンピュータ将棋プログラムが誕生しており、ファミリーコンピュータのゲームソフトとしてもコンピュータ将棋が製品化されるようになった。結果、「どのプログラムが最も強いのか」という興味を惹くこととなった。
将棋ソフトのプログラミングに興味を持つ有志らが集まり、1986年に『コンピュータ将棋プログラム』の会が発足。翌年、『コンピュータ将棋協会』に改名された。彼らが主体となり、1990年からは将棋ソフトの実力向上を図ることを目的に、コンピュータ将棋選手権が年1回開催されるようになった[5]。記念すべき第1回大会は1990年12月2日、将棋会館で行われた。参加ソフト数は6つ、優勝したのは『永世名人』。第11回からは「世界」を冠するようになった(従来から世界大会であった)。海外の実力あるソフトには、イギリスのSHOTEST、北朝鮮のKCC将棋 等がある。
毎年5月上旬のゴールデンウィーク期間中に開催されており、毎回約40種のプログラムが参加している。
世界コンピュータ将棋選手権の大会ルール[6]によると、対戦は、対戦サーバを介して行うこととされ、対戦サーバが利用できない場合、CSAの規定するRS-232Cプロトコルに則ったRS-232Cによる通信や手入力で対戦が行われる。持ち時間は25分で、これを使い切ると負けとなる。
第16回以降の大会では、開催期間中インターネット上で棋譜のライブ中継が行われている。
歴代の優勝プログラム
※名称はすべて大会出場時のもの[7]
- 第1回(1990年) - 永世名人
- 第2回(1991年) - 森田将棋 3
- 第3回(1992年) - 極
- 第4回(1993年) - 極 II
- 第5回(1994年) - 極 2.1
- 第6回(1996年) - 金沢将棋
- 第7回(1997年) - YSS 7.0
- 第8回(1998年) - IS将棋
- 第9回(1999年) - 金沢将棋
- 第10回(2000年) - IS将棋
- 第11回(2001年) - IS将棋
- 第12回(2002年) - 激指
- 第13回(2003年) - IS将棋
- 第14回(2004年) - YSS
- 第15回(2005年) - 激指
- 第16回(2006年) - Bonanza
- 第17回(2007年) - YSS
- 第18回(2008年) - 激指
- 第19回(2009年) - GPS将棋
- 第20回(2010年) - 激指
- 第21回(2011年) - ボンクラーズ
- 第22回(2012年) - GPS将棋
- 第23回(2013年) -
コンピュータ対人間
コンピュータ将棋が平手でトップ棋士を破る日はさほど遠くないと考えられており、2010年代から2020年までにプロ棋士がコンピュータ将棋に負けると予測されている[8]。
人間との対決の歴史
コンピュータ将棋の黎明期には、当時のコンピュータの性能もあり、コンピュータがプロ棋士のレベルに達するのは当分先のことだと思われていた。 チェスソフトのノウハウを応用して最初に将棋ソフトが作られた時代は、アマチュアの初級者にすら負けるようなひどい有様であり、プロ棋士の間では、この先どれだけ技術が進歩しても、ソフトはプロどころかアマの上級者(当時のプロ・アマの格差は現在よりもはるかに大きかった[要出典])にも勝てないだろうと予想されていた[要出典]。
しかし、90年代に入ると技術の急速な進歩によりソフトの棋力が大きく上昇し、ハード(CPU、メモリ)の進歩などもあり、その後はアマチュアの上位層への勝利を狙えるほどになった[要出典]。
2005年には、さらにアマ県代表クラスに到達し、以降、アマの最上位からプロの最底辺とほぼ互角という水準になっていく[要検証 ]。 その年のコンピュータ将棋選手権でのエキシビジョン対局において、同大会の優勝ソフト『激指』がプロ棋士の勝又清和に角落ちで勝利した[9]。また同年6月の第18回アマチュア竜王戦において招待選手として出場した『激指』は、都道府県代表を相手に3連勝し決勝トーナメント進出・ベスト16入りを果たした[10]。
同年(2005年)の9月には、プロ棋士で北陸先端科学技術大学院大学教授を務める飯田弘之のチームが開発したコンピュータ将棋ソフト「TACOS」が同じくプロ棋士の橋本崇載とイベントで平手の対局。結果は橋本の勝ちとなったが、TACOS は橋本を敗北寸前まで追いつめた[11]。この事態を重く見た日本将棋連盟は、同年10月全棋士と女流棋士に通達を出し、連盟に無断で公の場でコンピュータ将棋と対局しないこととした[12]。
2007年3月21日には、Bonanzaとタイトルホルダーである渡辺明(竜王)との公開対局(平手)が行われた(Bonanza#竜王との対局参照)。Bonanzaはタイトルホルダー相手に健闘し、終盤の読み違いがきっかけとなって敗れはしたものの、対局者の渡辺をはじめとする複数のプロから、プロ予備軍である奨励会の初段から三段の実力に相当するとの高い評価を受けた。
2008年5月5日に行われた第18回世界コンピュータ将棋選手権のエキシビションマッチにおいては、優勝ソフトの激指がアマ名人の清水上徹を、準優勝ソフトの棚瀬将棋が朝日アマ名人の加藤幸男をそれぞれ破るという快挙を成し遂げた。この対局に対し、敗れた清水上と加藤はそれぞれ、「コンピュータの読みが上回った」「完敗だった」とコメントしている[13]。2008年11月8日に行われた清水上、加藤と激指、棚瀬将棋との60分60秒のリターンマッチでは、加藤が勝利して雪辱を果たしたものの、清水上はまたも敗北を喫した[14]。公式対局でプロ相手に何度も勝利を上げているトップアマの二人の敗戦はプロにとっても衝撃であり、渡辺明[15]、遠山雄亮[16]、片上大輔[17]らのプロ棋士がブログにその驚きを綴っている。
2010年4月2日、情報処理学会は、会長の白鳥則郎(東北大学客員教授)名義にて「35年の開発の末名人に伍する力ありと情報処理学会が認める迄に強いコンピューター将棋を完成致しました」と宣言し、日本将棋連盟に挑戦状を渡した。将棋連盟はこれに対し、米長会長名義で「その度胸と不遜な態度に感服した」として挑戦状を受理。最初の対戦相手として女流の清水市代(対局決定時女流王位・女流王将の二冠)を指名した[18][19]。
同年8月23日には対局の詳細が発表され、持ち時間はチェスクロック使用による3時間(1分未満の考慮時間も計測される)、使い切ったあとは1手1分というマイナビ女子オープン五番勝負と同様の条件となった。また、コンピュータ側はハードウェアが東京大学のクラスターマシン(Intel Xeon2.80GHz×4cores:109台・Intel Xeon2.40GHz,×4cores:60台・合計169台676cores)、ソフトウェアは「激指」「GPS将棋」「Bonanza」「YSS」の4種類のソフトが電気通信大学伊藤研究室の開発するマネージャの管制の下で多数決を行う合議制がそれぞれ採用された。このシステムは、10の224乗という、将棋の全局面数10の226乗に近い数を示す語をとって、「あから2010」と名付けられた。
清水とあから2010の対局は同年10月11日に東京大学工学部で指され、86手で後手のあから2010が勝利した。この結果に対し将棋連盟の米長会長は、中央公論2011年1月号における梅田望夫との対談で、次は自身が「引退棋士の代表」としてコンピュータ将棋と対局するという表明を行った[20]。2011年10月6日、日本将棋連盟、ドワンゴ、中央公論の三者が主催する、「米長邦雄永世棋聖 vs ボンクラーズ プロ棋士対コンピュータ 将棋電王戦」の概要が発表された。2011年世界コンピュータ将棋選手権の優勝ソフト「ボンクラーズ」と米長が2012年1月14日に対局し、この対局を「第1回電王戦」として以後継続的にプロとソフトの対局が行われる。対局形式は持ち時間3時間で1分未満の考慮時間は計測せず、途中に1時間の昼食休憩を挟む、ボンクラーズ側のセッティングは消費電力2800ワット内で自由と発表され、会見時に行われた振り駒によって先手がボンクラーズと決まった。
対局に先立ち、2011年12月21日に米長とボンクラーズの前哨戦がインターネット対局対局サイト「将棋倶楽部24」で行われた。電王戦と同じく後手番を持った米長は2手目に6二玉という奇手を指してボンクラーズの撹乱を狙ったが、85手で先手のボンクラーズが勝利した[21][22]。
2012年1月5日には、2013年中に第2回電王戦を実施することが将棋連盟より発表された。プロの代表は、2011年の第1回加古川青流戦に優勝した船江恒平四段、ソフトの代表は2012年5月に開催される第22回世界コンピュータ将棋選手権の成績優秀プログラムとなり、ルールは第1回戦に準じる[23]。
2012年1月14日、米長とボンクラーズの本対局が将棋会館で行なわれ、113手で先手のボンクラーズが勝利した。米長は二手目に6二玉と、前哨戦と同様の手を指した [24][25]。
また、この対局後、2013年に行われる第2回電王戦について、プロ棋士対コンピュータの5対5の一斉対局となることが発表された。プロ棋士側はすでに発表された船江を含む5名が選出される。[26]
詰みを読む力
ある局面において『詰み』の有無を判定する作業は、単純な情報処理能力が力を発揮する分野であり、コンピュータは人間をはるかに超える計算力により、容易に詰みを発見することが可能になっている。
詰みに特化した詰将棋の分野では、大半の局面においてコンピュータはすでにトップ棋士の解図力を上回っている。可能な王手と玉方の応手をすべて検索するコンピュータならではの方法論により、人間を凌駕する実力を備えている。詰将棋の創作にあたって、コンピュータを使用して作品の完全性を検証することは、すでに常識となっている[27]。
持ち時間の長短
基本的に、コンピュータ将棋は持ち時間が短い対局の方が人間に対して有利である。1手30秒などといった早指しなら、プロ棋士に対しても7から8割以上の勝率をあげるまでになっている。 2008年現在の予想では、コンピューターソフトの棋力は遅くとも2020年までには、時間制限がまったくなくてもトップ棋士を追い越すと言われている。
コンピュータチェスとの比較
初期のコンピュータ将棋はコンピュータチェスの理論をもとに開発されたものが多い[28]。チェスと比較した場合、将棋は取った駒を持ち駒として再使用できるというゲーム特性から指し手の選択肢が格段に多いため、類似のゲームではあってもはるかに高度なプログラムが必要とされている。
1997年には将棋と同じく二人零和有限確定完全情報ゲームに分類されるチェスの世界において、当時の世界チャンピオンガルリ・カスパロフがIBMのディープ・ブルーに敗北し、将棋界にも大きな衝撃を与えたが、持ち駒による全局の多さ[29]があることなどから、2012年時点では現役トップレベルには達していないものの、元トップ棋士だった米長邦雄にエキシビジョンマッチ及び3時間の持ち時間制の将棋でも勝利するなど、平手でも敗北する例がではじめている。
代表的なソフトウェア
コンピュータ将棋選手権出場時と商品の名称が異なっているものもある。
- YSS - 「AI将棋」としてイーフロンティア(旧アイフォー)より発売
- 激指 - マイナビ(旧・毎日コミュニケーションズ)より発売
- IS将棋、棚瀬将棋 - 「東大将棋」としてマイナビより発売
- KCC将棋 - 「銀星将棋」としてシルバースタージャパンより発売
- 柿木将棋 - エンターブレインより発売
- 金沢将棋 - アンバランスより発売
- 森田将棋 - 悠紀エンタープライズより発売
- 永世名人 - コナミより発売
- GPS将棋 - 東京大学大学院総合文化研究科の教員・学生のメンバーが中心になって開発が行われているフリーウェア
- Bonanza - 思考部はフリーウェアとして提供。
- デーモン将棋(Daemonshogi) - Linuxで動作する GTK+ ベースのシンプルな将棋プログラム(フリーウェア)
- ハム将棋[30] - Flashを利用したフリーウェア。
- K-Shogi - Windows用のフリーウェア。
- あから(阿伽羅) - 情報処理学会が、清水市代との対局用に用意した専用システム。「GPS将棋」「YSS」「激指」「ボナンザ」の四つが合議制の思考エンジンを、東京大学にあるクラスターマシン上で実行する。
- 将棋所[31] - GUIと思考エンジンを分離する設計思想に基づいたGUIソフト。USI(Universal Shogi Interface)と呼ばれる公開プロトコルを利用し、複数の思考エンジンを利用できる。英語表示にも対応。
- ボンクラーズ
ソフト指し問題
将棋ソフトのレベルが上がった結果、ヒント機能や検討モード、対局機能などを使ってネット将棋を指すユーザーが少なからず出てきている。 ネット将棋大手の将棋倶楽部24では(公認を除き)他の善良な会員の皆様に種々の迷惑がかかるとして、2008年に「24ソフト指し取締委員会」を設置。将棋ソフトの指し手との一致率を基準として「ソフト指し」を認定し、不良利用者アカウントの削除などを行っている[32]。
脚注
- ^ 2010年から見て。
- ^ 合議制のために各々は若干設定を変えてある。
- ^ 「将棋世界」2010年10月号 p.148、「コンピュータ将棋協会」のwebサイト、「合議アルゴリズムと文殊のページ」
- ^ 将棋世界2007年7月号より。また、開発に至った経緯およびその詳細は同号を参照のこと。
- ^ 将棋世界2007年7月号より。
- ^ コンピュータ将棋協会参照。各回ごとにルールが定められ、公開されている。
- ^ 過去に出場した全てのプログラムの成績一覧より抜粋。名称はプログラム名を用いるものとし、製品名のみを掲載することは認められていない。
- ^ コンピュータ将棋の専門家である公立はこだて未来大学の松原仁はそれ(将棋のチャンピオンにコンピュータ将棋が勝つこと)を2015年と予想している(情報処理2005年7月号より)。またコンピュータ将棋協会会長の瀧澤武信もそれを10年後~20年後と予想している(将棋世界2007年7月号より)。
- ^ コンピュータ将棋 対 人間 対戦の記録
- ^ 将棋ソフトの「激指」、アマ全国大会でベスト16に進出 NIKKEI 将棋王国 2005年6月25日
- ^ 飯田教授らが開発したコンピュータ将棋はプロ棋士に惜敗(北陸先端科学技術大学院大学:ニュースとお知らせ)参照。
- ^ これはプロの威厳の維持、及びコンピュータ将棋との対局を重要なビジネスチャンスととらえている連盟の意向であるとされる。
- ^ その名も「激指」…将棋ソフト、人間に勝つ [リンク切れ] ヨミウリ・オンライン2008年5月5日、読売新聞2008年5月6日
- ^ 元アマ竜王2人、1勝1敗…コンピューターとの将棋対局 [リンク切れ]
- ^ コンピュータ選手権の結果。 渡辺明ブログ 2008年5月5日より「アマトップの方々は奨励会で言えばプロ手前の二段~三段の力はあるので、そこに2連勝というのは衝撃的」
- ^ 大きな話題と小さな話題 遠山雄亮のファニースペース 2008年5月5日より「この二人はアマチュアの方の中でもトップ、しかもトップの中のトップですから衝撃的です。将棋も強い内容でした」
- ^ 衝撃 daichanの小部屋 2008年5月5日より「二人そろって完敗したと聞いて衝撃を受けました。彼らの強さは僕もよく知ってますので」
- ^ 情報処理学会が日本将棋連盟に「コンピュータ将棋」で挑戦状社団法人日本情報処理学会 2010年4月2日 2010年4月2日閲覧
- ^ 「コンピュータからの挑戦状」(日本将棋連盟HP、2010年4月2日閲覧)
- ^ 次は私がコンピュータと対局します!清水女流vs.「あから2010」戦のその後を考える 中央公論ウェブサイト
- ^ “「米長邦雄永世棋聖 vs ボンクラーズ プロ棋士対コンピュータ 将棋電王戦」のプレマッチ ボンクラーズの勝利!”. 日本将棋連盟 (2011年12月11日). 2012年1月10日閲覧。
- ^ “[将棋ソフト]米長邦雄、コンピュータ将棋ソフト「ボンクラーズ」に敗れる”. RBB TODAY. (2011年12月11日) 2012年1月10日閲覧。
- ^ 「プロ棋士対コンピュータ 将棋電王戦」 第2回戦 対局者決定!! 2012年1月5日。2012年1月5日閲覧
- ^ “米長氏、将棋ソフトに敗北 永世棋聖も歯が立たず”. 47news. (2012年1月14日) 2012年1月14日閲覧。
- ^ “電王戦対決中!! 序盤は米長永世棋聖が有利か? 戦いの行方はニコ生を見よ!!”. 週刊アスキー (2012年1月14日). 2012年1月14日閲覧。
- ^ “米長元名人、将棋ソフトに負けた!…男性プロ初の屈辱”. スポーツ報知. (2012年1月15日) 2012年1月15日閲覧。
- ^ コンピュータソフトを使用するのは、作品に余詰や不詰がないかを確認するためである。また作成途中の補助に使う場合もある。
- ^ 2006年度の世界コンピュータ将棋選手権で優勝したBonanzaは、開発者自身がコンピュータチェスの文献を主に参考にしたことを表明している。
- ^ 読売新聞 2003年8月18日より
- ^ http://hozo.vs.land.to/shogi.html
- ^ http://www.geocities.jp/shogidokoro/index.html
- ^ “24ソフト指し取締委員会”. 将棋倶楽部24 (2008年1月7日). 2012年1月10日閲覧。