« 詰将棋メモ(2015年4月24日) | トップページ | 詰将棋メモ(2015年4月25日) »

詰将棋創作プログラミング 11 ランダムに自動創作

[2015年4月25日最終更新]

詰将棋創作プログラミング 11 ランダムに自動創作

1) ランダムな駒配置で詰将棋になっている確率は?

これまでの創作プログラミングでは、ある条件を満たす図をすべて生成して完全作を見つけてきた。しかし、すべて生成して完全作かどうかチェックできる数は、せいぜい1日あたり数千から数万といったところで、かなり狭い条件にしなければ全検は現実的ではない。例えば、詰将棋創作プログラミング 8 実戦型簡素図式を作るで、11香21桂22玉+詰方1枚の盤面4枚、持駒5枚以内の条件で調べたが、通常は盤面4枚というのはかなり少ない方で、4枚から10枚ぐらい配置されている作品が多い。間をとって7枚以内としても、とても全検できるような組み合わせ数ではない。

全検できないとしたら、その条件を満たす範囲でランダムに盤面、持駒を生成して完全作かどうかチェックすることが考えられる。これまでの将棋ソフトでも、そのような方式の「詰将棋自動生成」機能を搭載しているソフトがあったが、まともな詰将棋はほとんど生成できなかったような記憶がある。

レベル0 ランダムに盤面、持駒を生成した局面
レベル1 合法的な局面
レベル2 とにかく詰む局面
レベル3 駒余りなく詰む局面
レベル4 余詰なし (ここまでくれば、一応完全作)
レベル5 ちょっとはいい手があり、詰将棋といえる
レベル6 入選レベル
レベル7 受賞級

ちょっと考えただけでも、良い詰将棋を生成するのは何段階もハードルがあり、単純なランダム生成では確率はほとんどゼロに近そうだ。各段階で効率的に絞り込む技術が必要になるだろう。

2) とにかく試行してみよう

どんな技術が必要か、やってみなければわからないので、前述の「盤面後手11香21桂22玉を含む7枚以内、持駒5枚以内」で実際に試行してみた。

最初に考えたのは「何についてランダムにするか」ということ。駒の枚数、先手後手の比率、駒種、駒位置など、いろいろな要素があり、生成の方式を決めないと先に進めない。

例えば、香桂玉以外の4枚の駒の置き場所を81マスからランダムに選ぶとしたら、ほとんどの場合詰まないであろうことは容易に予想できる。

3) 詰将棋データベースの活用

同じ条件の詰将棋を調べてマネをすれば、確率を上げられるのではないか。詰将棋データベースは決められた条件での検索しかできないので、まず、柿木将棋に付属している詰将棋データベース形式のktkファイルを読み込んで検索するプログラムを作ることにした。詰将棋データは全詰連の詰将棋データベース収録の作品など20数万作あるので、ある程度は高速に処理したい。

いずれは手順や詰上り図も検索できるようにしたいところだが、第一段階として、データベースに登録されている書誌事項と図面だけ読み込む部分を開発した。高速化のため、1回実行したら全局の図面だけ収録したテキストファイルを作成し、2回目以降はそれを利用することで個別のkifファイルへのアクセスを不要にした。

プログラムに読み込んでしまえば、「11は後手の香、21は後手の桂、22は後手の玉、盤駒は7枚以内、持駒は5枚以内」と判定するif文を書くだけで簡単に検索できる。

検索結果はまたktkファイルにして出力できるようにした。こうしておけば、人間が利用するときも便利だし、プログラムで再度分析したりすることもできる。柿木将棋と柿木詰将棋データベースは非常によい機能、ユーザインターフェースを提供しているので、可能なところはこれらを活用し、自分で作る分は最小限にする方針だ。

実際に「盤面後手11香21桂22玉を含む7枚以内、持駒5枚以内」の条件でプログラムで検索してみたら、1009作の詰将棋が見つかった。

4) 既存作品から自動生成

この1009作を切り張りして新たな局面を生成することを考えた。具体的には、次のようにしてみた。

  • 1009作の中から10作ランダムに選び、1作目から1筋、2作目から2筋、・・・、9作目から9筋、10作目から持駒をコピーして新たな局面を作る。

この方法の利点は、非合法な局面がかなり排除できる(チェックが省略できる)こと、実際の詰将棋からもってきているのでランダム配置にくらべずっと詰みやすいことである。

10000回生成させてみたところ、次の結果となった。

  • 盤駒8枚以上または使用駒がおかしい 2614図
  • 残りの7386図に対して柿木将棋を呼んで解図
  • うち、駒余りなしで詰み(1手、3手は除外) 376図
  • この376図に対して柿木将棋を呼んで検討
  • うち、完全作(非限定などもなし) 52図

実行時間は5748秒。完全作1作あたりだと111秒。完全作といっても、大部分は詰む将棋であることを考えると、もっと時間を短縮したい。また52図も人間(私)がチェックするのは大変なので、ここも何とかしたい。

5) 高速化、詰む率の向上 その1 既存作品での出現数

時間的に一番かかるのが柿木将棋の呼び出し部分なので、この回数をできるだけ減らしたいのだが、完全作のときまで減らしては元も子もない。

最初に考えたのは、先手の各盤駒について既存1009作での出現数の合計値が一定以上のときだけ柿木将棋を呼ぶ方法。これは呼び出しはかなり削減できたが、完全作も減ってしまい、完全作1作あたりの時間はほとんど改善できなかったので失敗。

  • 先手後手両方の盤駒の既存作品での出現数の合計
  • 先手2駒の組み合わせの既存作品での出現数の合計
  • 先手の駒と後手の駒の組み合わせの既存作品での出現数の合計
  • 先手2駒、後手1駒、持駒1駒の組み合わせの既存作品での出現数の合計

など、いろいろ試してみたが、期待ほど短縮されなかった。

6) 高速化、詰む率の向上 その2 評価値(詰将棋ポイント)

次に考えたのが、コンピュータ将棋では局面の評価値を計算しているが、同じように何らかの方法で局面の評価値を求めて、これが一定の範囲内のときだけ柿木将棋を呼ぶ方法。詰将棋は先手後手の勢力比(後手持駒を除く)が少しだけ先手が良いと予想される。これ以下では詰まないし、これ以上だと詰みすぎる、というように評価値を求める評価関数を設計できれば、駒余りなしで詰む確率を上げられるはずだ。

将棋では3駒間やソフトによっては4駒間の位置の組み合わせを使って評価値を求めているが、教師となるデータが1000作ぐらいしかないので、複雑な評価関数では学習できない。そこで、以下の3つの和を評価値としてみた。

  • 先手の各駒の点数、後手の各駒の点数(盤駒ポイント)
  • 先手持駒の各駒の1枚目の点数、2枚目以降の点数(持駒ポイント)
  • 先手、後手の各駒について、81マスの各マスの点数(位置ポイント)

詰将棋ポイント = 盤駒ポイント + 持駒ポイント + 位置ポイント

「少しだけ先手が良い」のを仮に100点として、90点から110点のあいだに1009作のうちなるべく多くの作がはいるように、各ポイントを自動調整させたところ、837作まではいる組み合わせが生成できた。

90点から110点のときだけ柿木将棋を呼ぶようにするわけだが、ここで一工夫して、盤面を9個の作品から生成したあと、持駒を生成するときに、詰将棋ポイントが90点から110点にはいるまで10回までリトライするようにしてみた。

10000回生成させた結果は下記の通り。

  • 盤駒8枚以上、使用駒がおかしい、詰将棋ポイントが範囲外 4970図
  • 残りの5030図に対して柿木将棋を呼んで解図
  • うち、駒余りなしで詰み(1手、3手は除外) 534図
  • この534図に対して柿木将棋を呼んで検討
  • うち、完全作(非限定などもなし) 71図

実行時間は4518秒。完全作1作あたりだと64秒で、4割以上短縮できたことになる。

7) 生成した作品の評価

人間が何十作も見て評価するのは大変なので、ある程度自動で評価したい。しかし、まだ手順を処理するところは未着手なので、暫定的に以下の簡易フィルターをかけてみた。

  • 後手の同x1回につき1点
  • 先手の同x1回につき-1点

合計で2点以上(概ね捨駒2回以上)のときだけ棋譜出力する。

実際にやってみたら10000回の生成で出力された棋譜は6作。このぐらいなら人間が見てチェックすることができる。実行時の状況はこんな感じで、解図から検討までいくのはかなり少ないことがわかる(クリックで拡大)。

Tst11a

見つかった6作を見てみたところ、残念ながら詰パラ入選級はなさそう。まあ、1回であたるほど確率が高いとは思えないので、何回も見つかるまで繰り返して実行する必要があるだろう。だとすると、もっと精度の高いフィルターがほしいところで、やはり手順の分析に取り掛からなければいけないかな。

せっかくなので、出力された6作から一つサンプルにあげておこう。

Tst024 詰将棋創作プログラミング 作品24 eureka

  • 43角|11香13歩21桂22玉24歩|飛角 13手

形は良いが紛れ不足。どこかで見たような手順で、新作とはいいにくい。

8) 次の目標は

今回開発したテクニックを使っていろいろ試すこともできそうだが、やはり手順が検索、分析できないと苦しいので、柿木将棋の棋譜からの手順の取り込みと検索の手法を開発していきたい。これができれば、詰上り図も生成できて、煙詰とか四金詰など詰上りが関係する詰将棋も検索できるようになる。

|

« 詰将棋メモ(2015年4月24日) | トップページ | 詰将棋メモ(2015年4月25日) »

コンピュータ詰将棋」カテゴリの記事

コメント

もしよろしければ、局面生成プログラムを公開、もしくは頂けないでしょうか...。
最近このサイトを知り、感心することばかりだったのですが、特にこのカテゴリのこの内容には心を奪われてしまいました...(笑)
私も詰将棋作家の端くれとして、とても魅力的なツールで自分自身とても気になる内容です。

ぜひ検討して頂ければ幸いです。

投稿: 山野 | 2016.03.28 16:49

山野さん、興味を持っていただきありがとうございます。
創作プログラミングで作成しているプログラムはツールとして開発してなく、必要になるつどその目的のためだけに使い捨てで次々作っています。もう100本以上作っていて過去のプログラムは私自身でも余り把握してないので、公開や提供は難しいですね。すみません。
局面は柿木将棋kif形式のテキストファイルで、もし山野さんがプログラミングできる方なら生成は簡単だと思いますのでトライしてみてはいかがですか。

投稿: TETSU | 2016.03.28 20:20

TETSUさん返信ありがとうございます。
そうでしたか。それはとても残念です。

が、私もプログラムに挑戦してみることにしました。(昔々少しだけ触ったことがあるので)
ツールとしてではなくとも、プログラミングの参考のためにも詰将棋生成プログラムの一部だけでも頂けると幸いなんですが...。
といいますのも、ランダムに駒を配置するために乱数を使うのはいいのですが、その座標をどう保持して、どうファイルに書き込もうかとても迷っています。
プログラム、もしくはヒントを頂けると幸いです。どうかご検討くださいますようお願いします。

投稿: 山野 | 2016.03.29 12:53

単純ランダムでは詰将棋になる可能性はほとんどゼロなので、どういう方式で生成するか、どこをランダムににするか検討する必要があります。私の方法は創作プログラミングの11と12で説明していますので参考にしてください。ただ、詰将棋データベースを利用する方法なので、お持ちでないと使えない方法ですが。

投稿: TETSU | 2016.03.29 17:09

あと、盤面や駒の表し方は、池さんの「コンピュータ将棋のアルゴリズム」を参考にしました。
http://usapyon.game.coocan.jp/ComShogi/index.html
「将棋のルール」の章を読めばソースコードも説明されているので参考になると思います。

投稿: TETSU | 2016.03.29 17:25

返信ありがとうございます。
とりあえずプログラムは完成できたので、どう配置するかの試行錯誤をしたいと思います。
詰将棋データベースというのは、柿木将棋の付属品のことですか?
それなら手元にあるのでこちらのサイトの記事を参考にしたいと思います。

今回はわざわざ本当にありがとうございました。

投稿: 山野 | 2016.03.29 18:27

詰将棋データベース、プログラムは柿木将棋付属のものです。それに、過去に発表された詰将棋20数万作を登録して利用しています。

投稿: TETSU | 2016.03.29 19:17

コメントを書く



(ウェブ上には掲載しません)




トラックバック


この記事へのトラックバック一覧です: 詰将棋創作プログラミング 11 ランダムに自動創作:

« 詰将棋メモ(2015年4月24日) | トップページ | 詰将棋メモ(2015年4月25日) »