早稲田大学の教育・研究・文化を発信 WASEDA ONLINE

YOMIURI ONLINE | 読売新聞

  • トップ
  • オピニオン
  • ニュース
  • 研究力
  • 文化
  • 教育
  • キャンパスナウ
  • 早稲田評論
  • English

ホーム > オピニオン > サイエンス

オピニオン

▼サイエンス

瀧澤 武信(たきざわ・たけのぶ)早稲田大学政治経済学術院教授 略歴はこちらから

“阿伽羅(あから)”をどう読み切るか
 ――コンピュータ将棋の挑戦

瀧澤 武信/早稲田大学政治経済学術院教授

1.あから2010

 2010年10月11日にコンピュータ将棋システム「あから2010」が女流プロ棋士の清水市代氏(対局当時女流王将)と平手(ハンディキャップなし)で対戦し、86手で「あから2010」が勝った。清水女流は男性プロにもしばしば勝利しており、プロの養成機関である奨励会の最上位グループとほぼ同じ棋力だと思われるので、「あから2010」はそれを上回るレベルである可能性が高い。実際、2010年5月に行われた「第20回世界コンピュータ将棋選手権」の上位ソフト(「激指」など)は、日本将棋連盟の勝又清和六段によりプロ四段レベルであると評価されている。ここでは、コンピュータ将棋の仕組みを概説する。

2.ゲームのプログラミング

図1

 将棋では、ある局面から次の1手を決める場合、図1のような「ゲーム木」を作り、深く読んでいく。局面ごとに可能な手の数の平均値をb、ある局面から、勝敗がつくまでの手の長さの平均値をpとすると、ある局面から勝敗がつくまでに考える手の総数は、ほぼ、bのp乗となる。将棋の場合、bは80強、駒を並べ終わった初期局面からではpは115強であり、初期局面からの考える手の総数(すなわち、ゲームの複雑さ)は、ほぼ10の220乗である。仏教用語の阿伽羅は10の224乗のことで、これに近いので名付けられた。現在の最高速のコンピュータでも、1兆(10の12乗)年程度では初期局面から勝敗が決するところまで完全に読みを進めることはできない。

 実際に次の1手を決める場合には、適当なところで読みを打ち切り、打ち切った局面における勝敗に関する近似(通常は、「評価関数」と呼ばれる「駒得」や「王の守り」等の局面の要素に基づく近似)を行う必要がある。

3.ミニマックス原理とαーβ法

図2

 図1において、○は、現局面における手番の側の指す局面、□は相手側の指す局面である。ここでは、各局面における手が3手ずつであり、2手先(3手目)の局面では勝敗の近似値が得られているものとしその評価を3手目の局面の下に記述している。2手目の局面では相手側が指すので、相手側に取りもっとも有利な手を指すはずである。それは、指した後の局面が相手側にとって最善(手番側にとって最悪)となるようにするもので、2手目の局面から3手目の局面への太線の手(2手目の局面bから局面fへの手、など)である。したがって、1手目でbを選ぶとやや優勢(fの評価)、cを選ぶと互角、dを選ぶとやや劣勢の評価を得ることになる。この結果、1手目(現局面)では、bを選ぶことになる。これは「ミニマックス原理」と呼ばれ、ゲームプログラミングの基本である。図1では、9個の局面について評価関数で近似することになる。

図3

 これに対し、図2では、まずbから先の局面の評価を行うが、ここまでは図1と同じでbはやや優勢となる。しかし、cから先のiの局面の評価(互角)が得られると、jの局面は評価する必要がないことになる。jの評価が互角より手番の側に有利な場合は、その手を相手が選ぶことはないし、jの評価が互角より相手側に有利な場合は、cの評価はより相手側に有利となるが、いずれにしろ、現局面でcへの手は選ばないからである。すなわち、cから先の局面で、bの評価より相手側にとって有利なものが一つでも見つかると、cから先のその他の手は評価する必要がない。これを「βカット」という。同様にdでは、局面lの評価がbの評価より相手側にとって有利なので、その他の手はカットされる(このβカットで、手番の側と相手側が入れ替わったものは「αカット」と呼ばれる)。この方法をαーβ法という。図2では、7個の局面について評価関数で近似することになり、図1に比べ少ない評価関数での近似で、図1と同じ次の1手を得ることができる。

 図3は、理想的に手が並んでいるものである。この場合は5個の局面について評価関数で近似することで、図1や図2と同じ次の1手を得ることができる。

4.コンピュータ将棋の歴史と未来

 コンピュータ将棋は筆者らの研究グループが1974年11月に開発を開始した。1986年に東京農工大学の小谷善行氏等と「将棋プログラムの会」を立ち上げ、翌1987年に「コンピュータ将棋協会(CSA)」と改称し、今日に至っている。CSAは1990年から「コンピュータ将棋選手権」を主催している。この選手権は、何よりも公平性を重んじる一方、最高のパフォーマンスを追求するため、マシンスペックには制限をかけていない。選手権上位入賞プログラム製作者によるアルゴリズムなどの研究会や論文等による発表を促し、積極的な公開を進めてきた。このことが、コンピュータ将棋の進歩に貢献したと考えている。特に、2005年に「激指」が実装した「実現確率探索」と2006年に「bonanza」が実装した「評価関数の自動学習」のアルゴリズムの公開が大きい。最近は「bonanza」や「GPS将棋」がソース・コードの公開も行っており、新規参入を容易にしている。コンピュータ将棋の歴史を表1に、世界コンピュータ将棋選手権の概要を表2に、2007年以降の人間との対局を表3に示す。

表1 コンピュータ将棋の歴史
項目
1974 コンピュータ将棋の開発が開始される
1984 瀧澤のソフトと窪田義行小学生名人(当時、現プロ六段)の対戦、完敗で5級と評価される
1986 「将棋プログラムの会」発足
1987 「将棋プログラムの会」を「コンピュータ将棋協会」に改名
PC上で動くコンピュータ将棋ソフトが発売される
1990 第1回コンピュータ将棋選手権開催
1995頃 コンピュータ将棋選手権の上位ソフトが初段に到達
2005 コンピュータ将棋「激指」がアマ竜王戦で全国大会ベスト16に入る
コンピュータ将棋「TACOS」が橋本崇載七段と平手で対戦。善戦する
日本将棋連盟が、プロ棋士が公式の場でコンピュータと対戦することを禁止
2007 コンピュータ将棋「Bonanza」が渡辺明竜王と平手で対戦。善戦する
2008 短い持ち時間の試合で激指、棚瀬将棋がアマトップに勝つ
1時間の持時間(切れたら1分の秒読み)の試合で激指がアマトップに勝つ
2010 世界コンピュータ将棋選手権の上位ソフトがプロ四段に到達
3時間の持時間(切れたら1分の秒読み)の試合でコンピュータ将棋システム「あから2010」が清水市代女流王将に勝つ
表2 世界コンピュータ将棋選手権
年月 日数 優勝 準優勝 3位 参加数 会場 試合方式
1 1990.12 1 永世名人 柿木 森田 6(2) 将棋会館 総当たり
2 1991.12 1 森田 金沢 永世名人 9 将棋会館 総当たり
3 1992.12 1 金沢 柿木 森田 10 将棋会館 スイス7回戦
4 1993.12 1 金沢 柿木 森田 14(1) 将棋会館 スイス7回戦
5 1994.12 1 金沢 森田 YSS 22 シェラトン スイス7回戦
6 1996.1 2 金沢 柿木 森田 25(1) シェラトン 予選7回戦、決勝
7 1997.2 2 YSS 金沢 柿木 33(1) シェラトン 予選7回戦、決勝
8 1998.2 2 IS 金沢 Shotest 35 シェラトン 予選2クラス、決勝
9 1999.3 2 金沢 YSS Shotest 40 シェラトン 1次/2次予選、決勝
10 2000.3 3 IS YSS 川端 45 シェラトン 1次/2次予選、決勝
11 2001.3 3 IS 金沢 KCC 55 かずさ 1次/2次予選、決勝
12 2002.5 3 激指 IS KCC 51(1) かずさ 1次/2次予選、決勝
13 2003.5 3 IS YSS 激指 45 かずさ 1次/2次予選、決勝
14 2004.5 3 YSS 激指 IS 43 かずさ 1次/2次予選、決勝
15 2005.5 3 激指 KCC IS 39 かずさ 1次/2次予選、決勝
16 2006.5 3 Bonanza YSS KCC 43(1) かずさ 1次/2次予選、決勝
17 2007.5 3 YSS 棚瀬 激指 40 かずさ 1次/2次予選、決勝
18 2008.5 3 激指 棚瀬 Bonanza 40(1) かずさ 1次/2次予選、決勝
19 2009.5 3 GPS 大槻 文殊 42 早稲田大学 1次/2次予選、決勝
20 2010.5 3 激指 習甦 GPS 43(1) 電気通信大学 1次/2次予選、決勝
21 2011.5 3         早稲田大学 1次/2次予選、決勝

*第10回までは「コンピュータ将棋選手権」
*参加数は招待を含む。()内は招待数(内数)
*決勝はすべて総当たり、予選は(変形)スイス式
*第5回まで金沢将棋は「極」の名称
*プログラム名、会場名は略称
*第21回は予定

表3 2007年以降の人間との対局(一部)
イベント プログラム 人間 勝者 手合 持時間 秒読み
2007 3 21 第1回大和証券杯 Bonanza 渡辺明竜王 渡辺竜王 平手 2時間 60秒
5 5 第17回世界コンピュータ将棋選手権 YSS 加藤幸男氏 加藤氏 平手 15分 30秒
2008 5 5 第18回世界コンピュータ将棋選手権 激指 清水上 徹氏 激指 平手 15分 30秒
棚瀬将棋 加藤幸男氏 棚瀬将棋 平手 15分 30秒
11 8 ゲームプログラミングワークショップ2008 激指 清水上 徹氏 激指 平手 60分 60秒
棚瀬将棋 加藤幸男氏 加藤氏 平手 60分 60秒
2009 3 10 第71回情報処理学会全国大会 激指 稲葉聡氏 稲葉氏 平手 60分 60秒
3 22 第3回電通大E&C シンポジウム 合議*1 谷崎生磨氏 谷崎氏 平手 40分 60秒
11 7 電通大E&C「コンピュータ将棋の最前線」 文殊with bonanza 谷崎生磨氏 谷崎氏 平手 60分 30秒
GPS将棋 稲葉聡氏 GPS将棋 平手 60分 30秒
2010 2 6 大阪商業大学「頭脳スポーツと教育」 激指 古作登氏 激指 平手 20分 切れ負け
10 11 情報処理学会50周年記念イベント あから2010 清水市代女流王将 あから 平手 3時間 60秒

*1 激指,Bonanza,AI将棋,新東大将棋の多数決合議

 2011年5月には早稲田大学国際会議場で「第21回世界コンピュータ将棋選手権」が開催される。どのような新しいアルゴリズムが登場するか楽しみである。さらに、今回の「あから」の活躍で、プロのトップ棋士への挑戦も楽しみになってきた。

瀧澤 武信(たきざわ・たけのぶ)/早稲田大学政治経済学術院教授

1951.11生まれ

【学歴・職歴】
1974年3月 早稲田大学理工学部数学科卒業
1977年3月 早稲田大学大学院理工学研究科数学専攻修士課程修了
1980年3月 早稲田大学大学院理工学研究科数学専攻後期課程単位取得後退学
1978年4月 玉川大学工学部助手
1981年4月 玉川大学工学部専任講師
1985年4月 早稲田大学政治経済学部専任講師
1987年4月 早稲田大学政治経済学部助教授
1992年4月 早稲田大学政治経済学部教授
2004年4月 早稲田大学政治経済学術院教授
現在に至る

【著書(共著)】
「ファジイ理論 -基礎と応用-」共立出版,2010.8
「経済系のための微分積分」共立出版,2007.3
「Excelで楽しむ統計」共立出版,2004.2

  • 早稲田大学東日本大震災復興支援室 早稲田大学東日本大震災復興支援室
  • 大学体験web もっと動画でワセダを体験したい方はこちら
  • QuonNet まなぶ・つながる・はじまる、くおん。