将棋プログラム
注 探索手数の考察が間違ってたので、修正しました。(2010/5/1)
コンピュータと女流棋士による戦争が勃発する。
情報処理学会が将棋連盟に挑戦状 米長会長、「いい度胸」と受けて立つ - ITmedia NEWS
情報処理学会の白鳥会長 「漸くにして名人に伍する力ありと情報処理学会が認める迄に強いコンピューター将棋を完成致しました」
将棋連盟の米長会長 「いい度胸をしているとその不遜な態度に感服仕った次第」
清水市代・女流王位が受けて立つ。
将棋のプログラムについては一時期興味があって調べたり、既存のプログラムに手を加えてみたりしたことがある。比較的に新しい本である以下の本を読めば大体の様子はわかる。
「俺の邪悪なメモ」跡地にあるようにボナンザの登場による衝撃は大きかった。ボナンザは物理化学者の保木邦仁氏が趣味で作ったプログラムだ。
ボナンザとか。 - 渡辺明ブログを読むとボナンザは登場した初期のころからプロの間で評判は良かったことが分かる。
戸辺と将棋ソフトのボナンザとやらが対戦して戸辺が３局目で負けたらしいんです。本人は「油断して一発食ったんですよーー」と言い訳していましたが、負けは負け。
そんなバカなと思ったのですが見ているとこれが意外に強いので驚き。既にプロ棋士が数名平手で餌食になったとか奨励会有段者もコロコロ負けているらしいんです
対局を終えた某棋士が対戦。「いつか負けるとは思ったけどこんなに早くコンピューターに負ける日が来るとは・・・」と言っていました。見た感じでは出来不出来がかなり激しいのですが、安定して力を出すようになったら・・・。
そして渡辺竜王との決戦を迎える。
大和証券杯特別対局ボナンザ戦。その２(当日編) - 渡辺明ブログ
まだまだ下と思っていましたがプロの足元まで来ているということを認めざるを得ません。今後、プロがコンピューターと指すというのは避けては通れない道になるでしょう。次の機会は更に注目が集まるのではないかと思います。
ボナンザ戦の時の日記
前半2007年3月のブログ記事一覧(2ページ目)-渡辺明ブログ
後半2007年3月のブログ記事一覧(3ページ目)-渡辺明ブログ
将棋は手の広いゲームだ。そしてどんな将棋プログラムも以下のように動いている。
１ 手を探索：大体20手前後先まで読む。
２ 手の評価：評価関数を使って最終曲面を点数化。
３ 手の実行：点数の高い手を実際に指す。
それと探索深度に応じて冪(80^n)で探索範囲が拡大する。大体18手で10^34くらいパターンがある。
ボナンザ(2005年)以前はコンピュータの処理能力の限界もあって、評価関数を手の探索時に挟んで点数の低い手の探索を打ち切るなどの方法が行われていた。
この方法のメリットとデメリットを言うと、
メリット 手が絞れるので、探索手を少なくできる。
デメリット サブルーチンが複雑になるので一手あたりの計算量が増える。手の見逃しがおきる。
ボナンザは評価関数を探索の途中で挟むことをやめて、すべてのパターンを読み最終局面のみを評価した(全幅探索)。コンピュータの性能が向上したから可能になったことえもある。
適当な方法で80^n局面の探索を見落としなく、0.24(2.23)^nに減らすことが可能。
ボナンザ作者による解説
メリット 一手あたりの計算量が減る。手の見逃しがなくなる。
デメリット 探索範囲が膨大
強い将棋プログラムを作ろうとしたら、以下の二つをしなくてはならない。
１ 探索深度を深める。
２ 評価関数をより良いものにする。
１ 探索深度を深める。
これは計算機の処理能力に依存している。一秒間に50万局面。(適当なテクニックを使って、探索を深めることは可能)
２ 評価関数を良いものにする。
ボナンザ以前は評価関数は設計者の感性や動かしてみてからのチューニングなどで作られていた。ボナンザの新しところは、棋譜から評価関数を自動生成したところとチューニングを自動化したところにある。
さてこの強いボナンザだけれど、渡辺竜王と保木邦仁氏の対談本が出ている。
プロの思考と将棋プログラムの手の探索について対比させた面白い本だ。後半が保木邦仁氏によるボナンザの解説になっている。
ゲームによる人の思考とプログラムの思考ルーチンについて考えてみたい。ちなみに僕のゲームの腕前だけど、将棋は初段くらいでオセロはたぶん３段くらい。
人の思考
１ 手を絞って考える。
２ 手の流れがあれば探索深度を深める。
これらは過去の経験に負うことが多い。将棋は大して強くないのでどういう思考ルーチンかは言えないが、オセロだったら少しは言える。
参考 オセロの場合
オセロは相手を手詰まりにさせるゲームである。これを前提に話すと
初盤 ある程度定石に従っている。不確定要素が多くて評価できない。
中盤 手詰まりに持っていくためのテクニックを組み合わせる。
終盤 数を数える。終盤のテクニックを使う。
さてテクニックを使うだけなら、コンピュータでもできるではないかとなるが、ここは人間ならでは思考がある。
僕の場合は、中盤の段階で終盤のせめぎあいのときに有利になるように持っていく。そこは結局僕の持っているイメージになる。
例えば、「このままだと終盤の絵はこうなるから、こういう手はまずいなぁ。」って感じだ。イメージはおぼろげなんだけど結局は部分部分の組み合わせをイメージとして検証している。
コンピュータの思考
上に話したように基本は点数で評価する。
参考 オセロの場合
オセロも評価関数を使っているが、オセロの場合、手が少ないし終盤は数を数えるだけなので、力任せな探索と評価関数が終盤は数を数えるだけなので、プログラムにし易い。オセロに関していえば、コンピュータのほうが人よりも圧倒的に強い。世界チャンピオンでさえも勝つことは不可能。オセロでは強豪がオセロのプログラムWzebraを相手に研究することが多い。つまり人がコンピュータの答えを学ぶようになっているのだ。
将棋も近い将来そうなるときが来ると思う。
人は強くなればなるほど、手を捨てていくのだ。そうすることで思考を省略し探索を深めることができる。手を捨てていく過程には、経験に基づいた無数の変数がある。強い人が、何を考えるのかというとその無数の変数について一つづつ検証しているに他ならない。
変数が多くなると式で評価するのは難しくなる。どんなに計算機の能力があがっても、その無数の変数を扱うのは難しいだろう。結局は限られた変数の中で盤面を評価することになる。ただ、全幅探索で探索深度をどこまでも深くできるのならば、わかりやすい局面(駒の数などの少数のパラメータで評価可能な局面)で評価することができ、実質変数は少なくてすむ。
それはもはや人の思考とは異なるものだ。思考するための原理はそこに存在しなく、ただ解がそこに存在するだけ。そういう異質性をオセロのプログラムは既に身につけているが、ボナンザをはじめとする将棋プログラムも備えようとしている。
渡辺竜王はそれをボナンザとの戦いで感じたのではないだろうか。
大和証券杯特別対局ボナンザ戦。その２(当日編) - 渡辺明ブログ
５１手目▲６六角は見たことがない類の手ですがなかなかの手。僕らでは浮かばない手で、コンピュータが将棋の技術向上に一役買ったと言えると思います。今後も、このような斬新な手を見せてくれるのでしょうね。それによって新手法、新手筋が増えていく可能性もあるのではないでしょうか。
ボナンザに勝つ方針について。
ボナンザの気力はアマチュア4段以上と言われるが、ボナンザに勝つ方法は残されている。
ボナンザは、手の効果が超手数後に効いてくる手については評価できない。つまり、ゆっくりと優位を築いていくような手を選べばボナンザに勝ちやすくなる。
渡辺竜王とボナンザの思考についての比較
大和証券杯特別対局ボナンザ戦。その２(当日編) - 渡辺明ブログより引用
実はここまで予定通り。後手陣は凝っていますが色々と試した結果、この組み方が最も安全という結論に達していたので迷わずに進めました。うちのボナンザは図から▲６五歩△５三銀▲３三角成△同金直に▲７一角と打ってきます。
△７二飛で角銀交換になるので後手必勝。これを期待していたのですが今日のボナンザはやってきませんでした。後で聞いたところ、ボナンザは参考図の▲７一角を読んでいたものの、思いとどまったそうです(笑)
▲７一角をやってこなかったので「今日のボナンザはちょっと違うな」と感じました。
探索深度がおそらく上がっていると思われる。
ここです。次の▲６四歩。見た瞬間、思わず「なんだそれ？(なんだその緩手は)」と声が出ました。▲９一馬の利きが止まるし、▲６三歩成としても穴熊には響きません。「これはもらった」と思い熟考に沈みました。
数分後。「・・・実は▲６四歩は好手？」▲６四歩に対して△同歩は▲８一馬と桂と取られて図で単に▲８一馬とするのに比べると一手早く▲５四馬と引くことができます。よって△同歩とは取れません。
取れない以上、攻めるしかないのですが有効な攻めが見当たりません。本譜の△３五銀は▲６三歩成を期待したもの。▲６三歩成ならば△２五歩で後手優勢になります。と金を作るのは点数が高いと思い、誘ったのですがノータイムで▲３六歩と正解を指されてしまいました。
ボナンザは「▲６四歩と突いたら相手は攻めてくるしかない。それならば受け切れる」という読みで▲６四歩を選んだのです。人間なら「▲６四歩は馬道が止まって怖いから」という感覚的理由で考えない手です。
一連の手順を見て「今までのボナンザとは別人のように強い」ということが分かりました。
ボナンザは探索深度の中で最終局面の点数が一番高い手を返す。探索深度の中で受ける手で悪い局面がなかったので、▲６四歩を選んだと思われる。
勝負の分かれ目はここでした。▲２四歩からの攻め合いは僕が勝ちだと読んでいたところへ▲２四歩がきました。
相手が人間ならば「この人△３九竜を見落としているんだろうなぁ」と思うところですがボナンザの終盤は信用しているので「△３九竜でこっちが勝つはずなのにくるってことは何かすごい手があるのだろうか・・・」となります。
同じ局面でも相手が人間かコンピューターかで感じ方が違うのです。
結論から言えばボナンザは△３九竜を軽視していたようです。コンピューターにもうっかりがあるのですね。コンピューターの終盤戦は完璧だと思っていたので少し安心しました(笑)
戻って、△１五金(図)には▲２七香△２六金▲同香△２七歩▲３八金打△２八歩成▲同馬(参考図)とされるのが嫌でした。
この手順は「飛を渡して銀も歩で取られるけど馬を引き付けて相手が歩切れだから良し」というかなり高度な手順なので指せないとは思いました。
８９手目▲２四歩が敗着ということになりました。やはり、穴熊戦の距離感は苦手のようですね。
終盤では詰みがあるので手を絞れて探索深度を深めることができるが、当時のボナンザは終盤用の思考ルーチンを積んでなかったので、一連の手筋が探索深度の外にあったので読めなかったと思われる。
渡辺竜王のこの記事からはプロが手を捨てて超手数後まで局面を読んでいるに対し、ボナンザが比較的に短い手数の中であらゆるパターンをしらみ潰しに調べていることが分かる。
追記：オセロの本について
プログラムについて 探索方法は将棋と変わりません。評価関数がオセロようになっているだけです。
勝つ方法について 僕は定石や手筋を実践で覚えましたが、本にまとめている人がいるのでそういうものを読むだけで、かなりの棋力の向上が期待できると思います。
一応、僕が読んだことある本としては、それぞれ以下の本があります。
id:hirataraさんの情報より
http://shogi.yaneu.com/index.php?%A4%E4%A4%CD%A4%A6%A4%E9%A4%AA%BE%AD%B4%FD%B3%D0%BD%F1
この記事おもしろいですね。
衰弱堂雑記: あなたが知らない（かもしれない）コンピュータ将棋の世界
