将棋ソフトにみるAIのアルゴリズム | SiTest (サイテスト) ブログ

メニューボタン閉じるボタン

将棋ソフトにみるAIのアルゴリズム

AIが現在注目され、どんな世界になるか様々な想像や推測が飛び交っています。
将棋の世界では一足先に棋士を負かすような強いAIが登場し、既にある程度共存していると言っても過言ではない状態となっています。

そんな一足先にAIと現実が融合した将棋の世界を紐解きつつ、
人とAIの関わり方を考えていきたいと思います。

将棋の強い弱いはどう決まる?

そもそも将棋が強いとはどういう事なのでしょう?
駒損しない、囲いや崩し方を知っている、詰将棋が得意、手筋を多く知っている…
様々な勝つ為に欠かせない要素がありそうです。

その中でも、1手の価値を知ることが特に重要です。
序盤は単純な動きしか出来ませんが、駒の交換が発生する中盤以降は好きな場所に自由に駒を打ち込んで相手陣地を脅かす事が出来るので、
終局に向かうにつれて1手の価値が飛躍的に高くなります。

将棋の解説でも「この順に進めば先手になる・手番を取る・0手で角を成る」等の単語が飛び交い、こちら側が一方的に攻撃する事が勝利に繋がります。
逆に無視しても構わないような手は緩手と呼ばれ、厳しい攻撃が出来ないと直ぐ様攻守が交代し、投了するまで一方的に攻め続けられてしまいます。

大局観とは?

Wikipediaの記事では「的確な形勢判断を行う能力」と定義されています。

棋士は研究や対局を重ねて他の棋士に勝利する職業ですので、勝負勘とも言うべき形勢判断力が極めて優れています。
盤面をちら見した程度で有利不利はもちろん、指し手を数手に絞り込むことができます。

先手先手で攻撃しやすい、駒得をしつつ簡単に相手の王将を脅かす事ができるなら評価はよくなりますし、
防御に回った時も駒同士の連携が良く、粘りやすい形ならば評価が良くなります。

将棋ソフトが読む何億通りの価値

昨今では将棋ソフトはコンピューターの性能次第では既に棋士より強いと言われています。
その強さの根底には秒間何億通りもの局面を読めるのだから棋士が敵うはずがないという論調で語られる事が多いのですが、本当でしょうか?

詰み将棋のロジックは十年以上もの昔から既にありますので、これが判別出来た時点で勝負あったと仮定します。

将棋は基本的にルール上指せる手は平均80パターン程あるそうです。
終局までに平均140手であることから、ざっと80の140乗程のパターンを生成して、そのいずれでも勝利出来る手を指し続ければ必勝です。
10手読むと10,737,418,240,000,000,000パターンなので、この天文学的な数字を更に14乗すれば将棋の全てのパターンで勝てることでしょう。

パターンを用意するだけなので、仮に秒間1,000億通りのパターンを計算出来る高性能コンピュータが存在したと仮定します。
しかしそれでも1年間かけて3,153,600,000,000,000,000パターンしか生成できず、このペースで3年かけてもまだ最初の10手を解き明かすことすらできません。

実際には平均80手の半数以上は攻撃も防御も行わない無駄な手であり、例えば初期局面からお互いのプレイヤーが王将を前後左右に動かすだけで140手過ぎるようなケースも考えられます。
このように無策に何億局面を並べても無限ループに陥る為、全ての状況で勝てる手を指す事は出来ません。

評価関数の登場

そこで、将棋ソフトに大局観を実装します。
必ず勝てるかどうかは分からないが、駒の連結が良く相手の攻撃を持ちこたえられるし、相手の陣地を攻撃しやすい。
きっとこの手を指せば優勢だろうという判断をさせるアプローチです。

もし極めて正確な大局観が実装できれば、
こちらに有利になる手ばかりを指すことで対局に確実に勝利することが可能でしょう。

将棋ソフトでは盤面を解析し評価関数という数値で形勢判断をおこないます。
この棋士の大局観に負けない正確な評価関数をいかに作り出すかが、
強い将棋ソフトの肝であり壁となるポイントとなります。

初期の評価関数

コンピュータvsプロ棋士: 名人に勝つ日はいつか (著者: 岡嶋裕史)によると、多くの棋士が「永遠に負けない」「自分の目が黒い内に実現することはない」等と分析していたように、
大局観という経験や勘をプログラムに落とし込む事は極めて困難です。

開発者達が最初に目を付けたのが駒の価値です。
「取る手に悪手なし」「駒得は裏切らない」などの格言があるように将棋では駒の損得は重要な要素の一つで、
強い駒を取れば相手の陣形を弱体化させつつ、こちらの陣形が強化されて有利になります。
歩から王将までの全ての駒に点数を割り振り、わらしべ長者的に駒得を重ねて勝利を目指すアルゴリズムが作られました。

将棋は戦場から王将を遠ざける為に金銀3枚で王将を囲う事が定跡であり、基本的に王将の回りには価値の高い金銀が固まっています。
なので将棋ソフトは駒得を目指すと自然に相手の王将を討ち取る事に繋がります。

駒の交換が中々発生しない序盤が課題となりますが、
棋士の対局の序盤をデータベースに登録して再生することで、 自然に囲いを完成させ、駒が衝突するまでをサポートする仕組みが作られました。

ただし、この2つの軸だけでは序盤早々に定跡データベースに無い手を指されると為す術もありません。
将棋の初心者でもネットや将棋の本で紹介されているマイナー戦法を真似るだけで、一方的に成り込んだ挙句、と金を量産して簡単に勝利する事が可能です。

2006年以前

プログラマ達の努力の甲斐があり、
下記のようなロジックが次々と評価関数に盛り込まれていきます。

  • 定跡を外されても序盤は囲いを整備する
  • 歩・銀・飛車を活かした数の攻めで開戦にこぎつける
  • 駒の利きや移動出来る箇所を重視する
  • 手筋を取り入れて相手の陣形を崩す
  • 一時的には損だが後々得をする手を指す
  • 駒の位置から囲いの堅さを数値化して、攻めるか受けるかを判断する
  • 詰みを拡張して、次に詰みになる詰めろや必死の概念を追加

しかし、これらの概念は将棋の腕が上達するにつれて分かる部分も多く、
将棋が指せるプログラマにしか実装出来ない状況が続きます。

1996年、「コンピュータがプロを負かす日は? 来るとしたらいつ」というアンケートでは、
「棋士と対等になるがトッププロに勝つ事は不可能」「七冠王がプログラミングをする日」「プロ棋士がプログラムを組めるようになった時」という意見もあり、プログラマ自身の棋力が将棋ソフトの棋力に反映される現状を反映しています。

2005年には強豪ソフトの激指やYSSがアマ強豪と対等に戦える程の棋力を叩き出し、
もうすぐ棋士に追いつくだろうと言われ始めるようになります。

2006年以降

2006年、Bonanzaが第16回世界コンピュータ将棋選手権大会に新星の如く登場し、ノートパソコンとUSB扇風機で優勝をさらいます。
Wikipediaの記事によると、Bonanzaの評価関数は様々な要因から算出されていましたが、
最終的には下記のような3つのシンプルなものに落ち着いているようです。

  • 各駒の価値: 13通り
  • 王1つ、他の駒2つの位置: 88,292,106通り
  • 王2つ、他の駒1つの位置: 4,842,018通り

駒の価値と盤上の駒の連結を評価すれば、
攻める方は相手の陣形が乱れる手を評価するし、守る時はこちらの陣形を強固にする手を評価する。
それにプラスして駒得が狙える状況なら駒得も狙う…という風に攻守の判断の材料になるわけですね。

流石にこの何百万、何千万という状況を全て手作業で評価していくと途方もない時間がかかりますので、
Bonanzaはプロの棋士同士の対局結果(棋譜)から勝敗という教師データを元に統計データを取り出し、機械学習を行う事でこの途方もないパターンに個別に点数を付けました。

そしてBonanzaは人間らしい強い手を指すという評価されるようになりました。
将棋の大局観を統計データに落としこみ、AIが将棋を指せるようになったのです。

将棋界に新しい風を吹かせたこの仕組みはボナンザメソッドと呼ばれ、今日の強豪将棋ソフトはほぼ全てが機械学習を採用していますが、
そんなBonanzaですら登場した当初はアマ強豪クラスの強さしかなく、
2007年に渡辺竜王との特別対局した時点では奨励会3段クラスの実力と評価されています。

2016年現在、多数の将棋ソフトの作成者が凌ぎを削り、様々な観点を盛り込んで、より強い将棋ソフトを次々と生み出しています。
その評価関数は既に棋士の大局観を超えつつあり、人間では敵わない境地へ到達しつつあります。
しかし、現在の強い将棋ソフトですら棋士を相手にした場合、序盤で棋士の研究には及ばす不利であり、中終盤の隙のない指し回しで逆転勝ちを収めるという構図であり、まだまだ完璧で正確な大局観に仕上がってはいません。

まとめ

いかがでしたでしょうか?

私自身も機械学習があれば強い将棋ソフトは簡単に作れるだろうと思っていましたが、調べて行くにつれてすぐに勘違いだということに気が付かされました。

その中でもハッとさせられた記述についてご紹介させていただきます。
コンピュータ将棋 – Wikipedia
2015年10月11日、情報処理学会がコンピュータ将棋の実力は2015年の時点でトッププロ棋士に追い付いている(統計的に勝ち越す可能性が高い)という分析結果を出し「コンピュータ将棋プロジェクト」の終了を宣言した。
この宣言に対してponanza開発者の山本一成は「コンピュータ将棋におけるレーティング上昇のプロットは、『われわれ開発者の努力』なんですよ!(中略)……合ってるのかもしれないけど……なんかちょっとカチンとくるんですよね(笑)。何おまえら勝手に線引いてるんだよ、自然現象じゃないんだぞ、みたいな」

機械学習が登場したにも関わらず棋士の棋力に追いつくまでに10年もの年月を要した事実は、
優れたエンジニアがよってたかって作っても、賢いAIをそう簡単には作れない事を意味しています。
これからは様々なAIが登場するかと思いますが、優れた能力を持つAI全てに問題を統計データに落とし込もうと頑張ったエンジニア達の努力とアイデアの結晶が詰まっていることでしょう。

以上、「将棋ソフトにみるAIのアルゴリズム」でした。
最後まで読んでいただきありがとうございました。