連載「人間VSコンピュータ 10番勝負！」
将棋対決・第1回 チェスコンピュータからの応用でもアマ20級
2013年に行われた第2回電王戦は、5人の棋士と5つのコンピュータ将棋ソフトが対決。結果は人間側、1勝3敗1引き分けで、団体戦としてはコンピュータに軍配が上がった。コンピュータと人間の対戦、今回からは将棋に舞台を移していく。
チェス・将棋の基本
チェス・将棋・囲碁ともに、2人でプレイし、決められた駒を使う。「サイコロを振る」などの不確定要素はない。お互いの手の内はすべてオープンで、2人の勝ち負けを足すとゼロになる、「ゼロサムゲーム」である。こうした性質を持つゲームは「二人零和有限確定完全情報ゲーム」と呼ばれている。
麻雀やポーカーのように、相手の持ち札が分からない「不完全情報ゲーム」とは違う分、コンピュータからすると探索の方法が明確になる。トーレス・ケベードが発明した「エル・アヘドレシスタ」で紹介したような、駒の動かし方のパターンだ。
 |
|---|
| 終盤戦のみを扱ったエル・アヘドレシスタの探索方法雑誌「BYTE」の記事をもとに作成 （クリックすると拡大します） |
この図のように、次に選ぶ手が決められているので、条件を付けて探索することができる。ただ、エル・アヘドレシスタの場合は自分の駒が1つ、相手の駒が2つだけという、極めて限られた条件である。
駒がすべてそろった状態で最初から対戦をするとなると、とたんにハードルが高くなる。チェスの場合、1手から最終局面までの手順数（探索空間）は10の120乗程度と言われている。将棋の場合は、10の220乗。一度取った相手の駒を使うことができるため、とたんに増えてしまう。囲碁は盤面の広さもあって10の360乗である。
将棋の局面を全て読もうとすると、1秒に1800万手を読むことができるソフトでも、宇宙が終わっても計算が終わらないという代物だ。「情報が全てオープン」であることと、「簡単にできる」ことは、イコールではないのだ。コンピュータ将棋の開発も、最初は苦難の連続だった。
70年代のソフトは、アマチュア20級
「名人がコンピュータ将棋ソフトを参考にするなんて、開発当時は考えられませんでした」。そう語るのは、コンピュータ将棋協会（CSA）会長の瀧澤武信氏だ。
2013年に行われた第71期名人戦で、羽生善治3冠を4勝1敗で破った森内俊之名人。第5局で森内名人が指した△3七銀は、第2回電王戦に出場した将棋ソフト「ポナンザ」が指した手だった。名人戦3局目の打ち上げ時にポナンザの打ち手を見た森内名人が、同じ局面になったために指したという。
名人が将棋ソフトの打ち筋を参考にするくらいのレベルになっているが、今から40年前に針を戻してみると…。コンピュータ将棋の開発が始まったのは1974年、NECから「（江戸末期の棋士）天野宗歩と中原誠名人（現・永世十段）ら現在のトップ棋士が対戦したらどうなるか」というシミュレーションソフト作成の依頼を受けて始まった。「その時は詰め将棋を指すソフトしかなかったんです」と開発に携わった瀧澤氏は語る。
詰め将棋について、瀧澤氏の研究グループでソフトを完成させたものの、その実力はアマチュア20級。シミュレーションの様子を見に来た中原名人も、あまりの棋力の低さに解説ができなかったという。
ミニ・マックス原理、アルファ・ベータ探索
瀧澤氏が開発した将棋ソフトで利用されたのは「ミニ・マックス原理」という方法だ。これは、現在の将棋ソフトもベースにしている、ゲームを進めるにあたっての基本的な考え方である。
例えば、「3手先までを読む」将棋ソフトであれば、それぞれの局面で点数をつけ、図1のような「探索木」と呼ばれる構造で評価を行う。
 |
| 図1 ミニ・マックス原理（クリックすると拡大します） |
この時、自分が指す番では、当然自分が一番有利になる局面を選ぶ。なので、局面の数字で最も大きいもの（マックス）を選択する。逆に、相手の番のときは「相手が最も有利になる＝自分が一番損をする」方を選ぶので、最小（ミニマム）の数字を選ぶ。図の場合は、自分の番で「B」を指すという結果になる。
こうして探索木の中からベストの1手（図では「B－E－K」の手順）を選んでいくのがミニ・マックス原理だ。しかし、1手につき約80パターンある将棋では、この方法だけだとコンピュータの行う計算量は膨大になる。対局という限られた時間の中でペストの手にたどり着くのは至難の業だ。そこで「アルファ・ベータ探索」と呼ばれる、無駄な計算作業のカットをするアルゴリズムが使われることになる。
アルファ・ベータ探索は、先程のミニ・マックス原理の枝のうち、読まなくても計算結果が変わらないものを「枝刈り（カット）」していく方法だ。
 |
| 図2 アルファ・ベータ探索（クリックすると拡大します） |
図2は、先程の図1の木をアルファ・ベータ探索したもの。自分の番である「N」の部分がカットされている。左にあるMは「8」で、この段階でFが8となる。Eが6で、Fは8。この時は相手の番なので、少ない方を選ぶ。そうなると、Nで8以上が出てFが大きくなったとしても、Eが選ばれることになるので、計算は不要になるから、Nはカット。この、自分の指す時の数字を切ることをベータカットと呼ぶ。
真中の「H」の部分もカットされている。ここでは、まず相手の番であるGとHを考える。すでにGは「1」が選ばれていて、相手の番では少ない数を選ぶから、Hが選ばれる候補になるには「1より小さい数字」になる。
だが、その上にあるBとCは、自分の番。すでにBが「6」という数字が出ている。Cは、この段階で1が出ており、「1より小さい数字」が出ても、自分の番では大きい数を選ぶので、Hで何が出ても計算する必要がないのだ。これをアルファカットと呼ぶ。
局面評価の難しさ
アルファ・ベータ探索は、選択肢の選び方や効率的な選択方法の代表例である。このカットも読みの順番によっては、さらに計算量を削ることができる。
ただ問題なのは、アルファ・ベータ探索の基準となる評価数値だ。「局面に点数をつけて自分に有利な数字を選ぶ」と書いたものの、これがなかなか難しい。そもそも、どのようにして盤面を評価するのか？ という問題がある。仮に飛車を10点、角を8点などとして強い駒を点数化して、駒得を踏まえて局面評価を行うにしても、序盤と中盤、終盤では同じ駒でも意味合いが違ってくる。
「序盤から中盤は駒得で、終盤は王手を狙う」と一言で言っても、これをプログラムに落とし込むには開発者がアマ段位を持つレベルくらい、将棋を熟知していなければものすごく困難な作業だ。読みの深さを簡単にしつつ、その都度出てくる局面評価も正確に行う。考えただけでもため息が出る。
1970年代から1980年代の将棋ソフト開発は、将棋にハマったプログラマしか手が出せないような状況だったのである。
過去の連載
人間VSコンピュータ 10番勝負！チェス対決・第4回 カスパロフとディープ・ブルー、対決の後に（2013/6/27）
チェス対決・第3回 チェスマシン「ディープ・ブルー」誕生前夜（2013/5/30）
チェス対決・第2回 スペイン生まれの「エル・アヘドレシスタ」（2013/5/2）
チェス対決・第1回 産業革命のあだ花・オートマトン「ターク」（2013/3/28）
コンピュータウイルス事件簿［全12回］（2012/3/15～2013/2/28）
暗号と暗号史［全12回］（2011/3/22～2012/2/16）
【関連カテゴリ】
