コンピュータ5五将棋の紹介と強化学習に関して

# はじめに

　Qiitaでははじめまして。コンピュータ将棋ソフト「GA将」開発者の森岡と申します。[コンピュータ将棋 Advent Calendar 2016](http://www.adventar.org/calendars/1457)の13日目として、本記事を投稿させて頂きます。


# コンピュータ将棋界のお隣

　最初にお断りしておきますが、本記事は厳密には「コンピュータ将棋」の話題では**ありません**。

　一般的に「コンピュータ将棋」と言えば、本将棋を指すソフトの事を指します。今日はそんな「コンピュータ将棋界」のお隣の「コンピュータ5五将棋界」について書かせて貰います。


# 5五将棋とは

　5五将棋とは、5×5マスの将棋盤を使って指す、本将棋のバリエーションです。初期配置は下図の通りで、ご覧の通り桂馬・香車は使用しません。

![5五将棋の初期局面](http://minerva.cs.uec.ac.jp/~uec55shogi/wiki.cgi?page=5%B8%DE%BE%AD%B4%FD%A4%C8%A4%CF%A1%A9&file=syokihaiti%2Ejpg&action=ATTACH)
※ UEC杯5五将棋大会のページから引用。

　本将棋とのルールの差異は、下記の通りです。

- 駒が成れるのは敵陣1段目のみ。
- 千日手は先手の負け（ただし、連続王手の千日手に関しては、本将棋と同じく王手側の負け）。

　それ以外のルール（駒の動きや、二歩・行き所の無い駒の禁止等）は本将棋と同じです。

　ルール詳細に関しては、下記のページをご参照下さい。

　　[5五将棋のルール](http://minerva.cs.uec.ac.jp/~uec55shogi/wiki.cgi?page=5%B8%DE%BE%AD%B4%FD%A4%CE%A5%EB%A1%BC%A5%EB)


# コンピュータ5五将棋の特徴

## 定跡・プロ棋士の棋譜が存在しない

　5五将棋にはプロ組織が存在しません。また、私の知る限りでは定跡の整備もされていない様です。

　よって、コンピュータ将棋で猛威を奮っている[Bonanza Mehtod](https://ja.wikipedia.org/wiki/Bonanza#.E6.80.9D.E8.80.83.E3.83.AB.E3.83.BC.E3.83.81.E3.83.B3)は、そのままではほぼ利用不可能です。

　その為、評価関数のパラメータ学習や定跡の自動構築等、新しいアイデアを実験する場として適していると思います。


## 短手数で決着がつく事が多い

　GA将同士で自己対局すると、大体30～40手程度で終局します。

　本将棋と比較すると、いきなり中盤の終わりから始まる様な感覚ですので、非常にスピーディーに進行する感じです。


## 短時間でも深く読める

　本将棋と比べて、下記2点の理由から同一思考時間で比較すると、より深く読める様になります。

1. 駒・マスの数が少ない為、合法手数が少ない。
2. 駒の数が少ない為、評価関数の処理が軽くなる。

　2.に関しては、特にBonanza系の三駒関係の評価関数を用いた際に、顕著にNPSが向上します（本将棋と比較して、同一プログラムで2～3倍程度）。

　参考までに、GA将では典型的な中盤局面で、10秒かけて15手前後（全幅探索部分のみ）の先読みが可能です。


## 学習ルーチン

### K55の学習ルーチン

　正式名称が不明なのですが、世界コンピュータ将棋選手権の常連の柿木さんによる学習ルーチンです。

　　[５五将棋における評価関数の自動学習](http://minerva.cs.uec.ac.jp/~ito/entcog/contents/lecture/date/5-kakinoki.pdf)

　大雑把に書くと、自己対局とその棋譜を用いたBonanza Methodを交互に行う方法です。「深く探索した自分（ソフト）自身を教師とした、Bonanza Method」とでも言えばいいのでしょうか。

　対局時の思考時間制御を工夫したり、乱数を用いたりする事で、様々なバリエーションの棋譜を生成するのが成功の為のポイントだそうです。

　K55は[第2回UEC杯5五将棋大会COM部門で優勝](http://www.computer-shogi.org/blog/uec55_2008_result/)する等、目覚ましい成果を挙げられています。

　（個人的には、最近の大会には出られていないので、直接対局がかなわないのが残念です。）


### Bishop Learning

　世界コンピュータ将棋選手権にも参加されている、「技巧」の出村さんによる学習ルーチンです。

　　[技巧ミニアピール文書](http://minerva.cs.uec.ac.jp/~uec55shogi/wiki.cgi?page=%C2%E86%B2%F3UEC%C7%D5+5%B8%DE%BE%AD%B4%FD%C2%E7%B2%F1&file=%A1%D6%B5%BB%B9%AA%A5%DF%A5%CB%A1%D7%A5%A2%A5%D4%A1%BC%A5%EB%CA%B8%BD%F12%2Epdf&action=ATTACH)

　ランダムに生成した局面から、適当な深さでαβ探索を行い、その結果を元に評価関数パラメータを調整する手法です。

　技巧ミニは[第6回UEC杯5五将棋大会](http://minerva.cs.uec.ac.jp/~uec55shogi/wiki.cgi?page=%C2%E86%B2%F3UEC%C7%D5+5%B8%DE%BE%AD%B4%FD%C2%E7%B2%F1)で2位に入り、独創賞を受賞されています。


### 強化学習

　GA将が使用している学習ルーチンです。

　「強化学習」は機械学習の一分野の呼称で、コンピュータ5五将棋では[TDLeaf(λ)](https://arxiv.org/abs/cs/9901001)や[PGLeaf](https://ipsj.ixsq.nii.ac.jp/ej/index.php?active_action=repository_view_main_item_detail&page_id=13&block_id=8&item_id=91354&item_no=1)等のアルゴリズムが有効である事を確認しました。

　強化学習で検索すると「環境との相互作用」「マルコフ決定過程」やら「ベルマン方程式」といった小難しい単語が出てきますが、そういうのは置いといてザックリと解説したいと思います。

　大雑把に書くと、強化学習というのはソフト自体の「経験」をベースに学習を進める事が出来ます。将棋の場合で言えば、対局ですね。

　例えば、GA将では自己対局の結果から学習していますし、あるいは他のソフト相手に対局してその結果から学習する事も可能です。

　以下、TDLeaf(λ)とPGLeafの簡単な解説をしたいと思います。厳密なアルゴリズムの解説ではなく「大体こんな感じ」という説明ですので、詳細に関しては上記の論文をご参照下さい。

　（割とややこしい話になりますので、「よく現れる戦型」まで読み飛ばして貰っても結構です。）

#### TD法

　TDLeaf(λ)を含む「TD法」ですが、これは対局中に現れた局面と、それ以降の局面の評価値を手がかりに学習する方式です。

　例えば対局中にAという局面が現れて、その後最善手を指すと評価値が＋200点の局面になったとします。

　この時、局面Aの「真の」評価値は何点でしょうか？

　答えは「分からない」ですが、「多分、＋200点に近いだろう」という推測は成り立ちます。

　よって、局面Aの評価値を＋200点に近付ければ（近付く様に評価関数のパラメータを修正していけば）、評価関数の精度が少し上がります。

　ただ、これだけでは学習の手がかりが少なすぎるので、終局時の評価値を例えば＋1000点（勝った場合）や－1000点（負けた場合）とかの適当な値にしてやれば、終局時に関しては「真の」評価値を学習に使えます。

　この処理を、対局→パラメータ修正→対局→…と無限に繰り返して行けば、段々精度の高い（強い）評価関数になっていきます。


#### 方策勾配法

　PGLeafは「方策勾配法」と呼ばれるアルゴリズムの一種です。

　これは、対局中に現れた局面での、全合法手の評価値と勝敗を基準に学習を進めます。

　例えば、初期局面で４四金と指して勝った場合を考えます。この時、「４四金は多分良い手だった」という推測が出来ますので、４四金の評価値を高く、他の手の評価値を低くする方向に評価関数のパラメータを修正します。

　逆に、３四金で負けた場合を考えると、勝った時とは逆に３四金の評価値を低く、他の手の評価値を高くする方向にパラメータ修正を行います。

　この時、パラメータの修正幅をどうするか、という所にポイントが有り、「絶対の一手」の場合（駒交換の途中など）は修正幅を狭くし、「良さそうな手が色々ある」場合は良さそうな手に関しては修正幅を広くします。

　先程の３四金で負けた場合ですが、人間なら「じゃぁ次は１二飛車を指してみよう」とは思いませんよね。飛車と歩の交換で、明らかに先手の損なので。

　という訳で、３四金で負けた場合は「他の良さそうな手」に関しては評価値を大きく修正し、「明らかに悪そうな手」に関しては評価値の修正幅を小さくします。

　まとめると、PGLeafは「試行錯誤と反省」の繰り返しを行うイメージです。実際に対局してみて、勝敗に応じて良さそうな手・悪そうな手を判断し、評価値を修正していくのが主な目的になります。


# よく現れる戦型

　これまでGA将が参加した大会で、比較的よく見た戦型を紹介したいと思います。本将棋と違い、詳細な定跡が無く戦型の分類も（私の知る限り）ありませんので、名称については参考程度に。

## 飛車先を攻める

　初期配置から金銀のいずれか一枚を攻めに、もう一枚を守りに使い、飛車先突破を目指す指し方。

　比較的短手数で決着がつきやすい印象です。

　ただ、初期配置では飛車が右に、角が左に利いているので、飛車角の連携が難しそうです。早々に角交換する形になれば、手番を持った方が有利になるかと思います。


## 持久戦模様

　初期配置から４四金・２四銀・３四角とした形。

　後手も同様の陣形をとると、千日手になりやすく先手やや不利かな、という印象です。

　無理攻めすると一気に負けやすく、比較的手数が長くなりそうです。


## ３三の位取り

　金銀のいずれかを３三まで進出させる形。

　個人的には、一番有力な形かと思っています。

　利点としては、３三の位を取ると相手玉の移動可能な範囲が極端に狭くなり、攻める形が作りやすい事があります。

　まぁ、この形に持って行くのがかなり大変なのですが。


# 5五将棋の大会

　国内で開かれている大きな大会は、下記のものです。いずれも、電気通信大学 情報理工学研究科 伊藤毅志研究室が主催されています。

## UEC杯5五将棋大会・GAT杯5五将棋大会

　過去の大会へのリンクは[こちら](http://minerva.cs.uec.ac.jp/~uec55shogi/wiki.cgi?page=%B2%E1%B5%EE%A4%CE%C2%E7%B2%F1)です。

　電気通信大学で開催される大会で、GPW杯より多数の参加者が集まります。


## GPW杯5五将棋大会

　2016年の大会へのリンクは[こちら](http://minerva.cs.uec.ac.jp/~uec55shogi/wiki.cgi?page=GPW%C7%D5%A5%B3%A5%F3%A5%D4%A5%E5%A1%BC%A5%BF%A3%B5%B8%DE%BE%AD%B4%FD%C2%E7%B2%F12016)です。

　GPW(Game Programming Workshop)のイベントとして開かれている大会です。

　参加者は比較的少なく、上位入賞を狙うならこちらの方が狙い目です。


# 観戦の仕方

　残念ながら、上記のいずれの大会もリアルタイムでの棋譜中継はありません。その為、後日棋譜をダウンロードして観戦する事になります。

　まず、[こちら](http://www.geocities.jp/shogi_depot/PetitShogi.htm)のサイトから「プチ将棋」をダウンロード・インストールしておきます。

　次に、大会のページから棋譜のZIPファイルをダウンロード・解凍します。拡張子mskのファイルが出来るはずですので、後はそれをプチ将棋で開けば棋譜が閲覧可能です。


# 開発の仕方

　コンピュータ5五将棋用のGUIとしては、上述のプチ将棋を使用するのが一番簡単かと思います。プロトコル自体は、本将棋用のUSIがそのまま使えますので、これに対応すればOKです。

　注意点としては、本将棋と違い「千日手は先手の負け」ですので、これにちゃんと対応しないと痛い目を見ます（と言うか、私が痛い目にあいました）。


# GA将の戦績

- GPW2012 5五将棋大会 ： 2勝2敗で3位。確か、参加チーム数は5チームだったと思います。
- 第9回UEC杯5五将棋大会 ： 8勝1敗でShokidokiとのプレーオフになり、惨敗して2位入賞。
- GPW2016 5五将棋大会 ： 3チームの総当りで、2連勝して1位入賞。

　過去3回大会に参加し、3位→2位→1位と順調に順位を上げています。

　…となると、次はオーバーフローして最下位になるんじゃないかとビクビクしています。

　ちなみに、GPW2012の大会では「千日手は先手の負け」のルールの実装を忘れていて、勝てたかもしれない将棋を落としています。ルールの確認は大切ですね。


# 他のソフトの紹介

## ssp

　プチ将棋付属のエンジンで、一番手軽に使えるソフトだと思います。

　使い方は、上述したサイトからプチ将棋をダウンロードし、「ツール」→「開始局面編集」で5五を選べば対局可能です。

　サンプルのエンジンですが、結構強いです。


## 海外勢

　UEC杯5五将棋大会等では、割と海外勢の活躍が目立ちます。Mullarさんという方が[こちら](http://hgm.nubati.net/miniShogi.html)のサイトで5五将棋対応のエンジンをGUIに同梱して配布されていますので、インストールすれば簡単に使えます。

　ちなみに、第9回UEC杯5五将棋大会優勝のShokidokiも含まれていますので、頂点を見てみたい人は一度指してみると良いかと思います。


# 最後に

　簡単にではありますが、コンピュータ5五将棋に関して紹介させて頂きました。

　本記事が、観戦・開発等のきっかけになれば嬉しいです。