01 January 2018

    3三将棋

    「3三将棋」について

     以前にも「3三将棋」に関する記事を書きましたが、実際に作ってみました。最初はゲーム開始時の初期盤面をユーザーが自由に編集出来るようなものにしようと考えていたのですが、そこまで開発コストをかけても実際に自分で初期盤面を試行錯誤しながら作って遊んでみようと思うユーザーがそれほどいるとは思えなかったので、とりあえず15パターンの初期盤面を用意しました。今後パターンを増やしていくつもりです。

    ルール

    • 駒の動きは将棋と同じです。
    • 打ち歩詰め、二歩は禁止です。
    • 先手は一段目、後手は三段目に駒を移動すると成ることができます。
    • 同一局面(手番も同じ)が4回現れると千日手でゲーム終了としています。
    • 行き場の無い駒は打てません(桂馬を二段目に打ったり、先手が歩を一段目に打ったり)
    • 王手放置は出来ません(王の自殺手も不可)

    対局画面

    対戦画面

    AI同士の対戦の時だけ局面の評価値を表示するようにしています。左上の数値は手数です。

    閲覧画面

    閲覧画面

    対局が終了するか、対局を中断すると閲覧画面に切り替わって、初手からの手順を確認することが出来ます。 Version0.9.9.0から中断後レベルや対局者を変更して再開することが出来ます

    盤面反転機能追加

     Version1.1.2.0から盤面の反転(先手・後手を上下逆さま)表示機能追加しました。画面右上の回転矢印アイコンをタップすると後手を手前にして将棋盤を表示出来ます。

    盤面反転機能

     この機能追加により今までAndroid4.4以上が動作対象機種でしたが、Android5.0以上が必要になります1

    メニュー

    • 先手・後手

    Version1.0.1.8からAI同士の対戦時も詰みまで指すように変更しました。
    Version0.9.9.0から、中断後にゲームを再開する機能をつけました。

    Menu - 先手・後手

    • AIレベル

    駒に重みを設定してその合計値で局面を評価する評価関数を使い先読みを行う、よくある思考ルーチン(MIN-MAX法+αβ法)です。JavaScript製ということもあり、非常に遅いのであまり深く読めません。今後、候補手を事前に絞るなどして速度アップをしていく予定です。

    Menu - AIレベル

    長考モード:
     Version0.9.3.0から長考モードが使えます。長考モードは4手読みで候補手を上位5手までに絞って、その5手に関して8手読みをするという仕様になっています。思考時間はリリース当初から改善していますが、古い機種では遅くて使用に堪えないかもしれません。

    Version AIレベル(普通) AIレベル(長考)
    0.9.1.2 Version0.9.1.2レベル普通 経過時間:30532ミリ秒 Version0.9.1.2レベル長考 経過時間:153052ミリ秒
    0.9.4.6 Version0.9.4.6レベル普通 経過時間:29258ミリ秒 Version0.9.4.6レベル長考 経過時間:87109ミリ秒
    0.9.8.0 Version0.9.8.0レベル普通 経過時間:25838ミリ秒 Version0.9.8.0レベル長考 経過時間:51774ミリ秒
    1.0.0.8 Version1.0.0.8レベル普通 経過時間:25732ミリ秒 Version1.0.0.8レベル長考 経過時間:49646ミリ秒

    ・長考モードにランダム選択を導入(Version0.9.7.0):
     長考モードは最初に4手読みをした結果から候補手を5手に絞っているので、その候補手を絞る段階で最善手が候補手から漏れてしまうこともあります。特に4手読みの結果上位5位、6位、7位の3手の評価値が全く同じであっても常に6位、7位の手は捨てられるのがもったいないので、評価値が同じだった場合はランダムに指し手を選ぶようにしました。あくまでも4手読み時の評価値が同じだった場合だけなので、指し手に大きな変化はありませんが長考モードに関しては常に同じ手を指すとは限らなくなりました。

    ・パフォーマンス大幅改善(Version0.9.8.0):
     前回のチューニング(Version0.9.4.6)はプログラムコードを速度重視のものに置き換える方法、今回のチューニング(Version0.9.8.0)は局面の枝刈りの無駄を省くアルゴリズムの修正によるものです2

    ・三手以内の詰み3は逃さないように変更(Version1.0.0.0):
     「弱い」モードの時も含めて全てのモードで三手以内の詰みは逃さないようにしました。勝ちを読みきった後でも無駄に手数を伸ばすことがあったので、全てのモードで三手以内の詰みがあるときは常にその手順を選択するように変更しました。
     今までから「瞑想」モードでは五手以内の詰みを逃さないようになっていますが、最初に候補手を絞る段階で好手を逃す可能性があるため、五手詰め以上に関しては絶対逃さないとは言い切れません。

    瞑想モード:
     Version0.9.9.0から瞑想モード追加しました。長考モードより一手深く読みます。

    反復深化探索:
     Version1.0.7.0から探索部が大幅に変わりました。

    AIモード\ Version  1.0.6.2まで    1.0.7.0以降
    弱い 全件探索、4手読み(depth = 3) 全件探索、5手読み(depth = 4)
    普通 全件探索、5手読み(depth = 4) 反復深化部分探索、7手読み(depth = 6)
    長考 候補手選択後、7手読み(depth = 6) 反復深化部分探索、9手読み(depth = 8)
    瞑想 候補手選択後、8手読み(depth = 7) 反復深化部分探索、10手読み(depth = 9)

    ※深くは読めませんが、全件探索の「弱い」モードが最善手を指すケースもありますのでご留意下さい。
    局面を検討するときは、まず「弱い」モードで試してから、他のモードを試してみることをお勧めします。


    駒の重み:

    駒の種類 \ 重み  表(不成)    裏(成り駒)  持ち駒
    玉(王) 9999 (9999) (9999)
    飛  85 110 75
    角  75 100 65
    金  50 (50) 45
    銀  45 50 40
    桂  30 50 25
    香  25 50 20
    歩  10 50 7

    ※対局中に大駒が成れるのに成らないケースがしばしば見られると思いますが、上記表の重みを考慮して、どうせ相手に取られるから成らない(低い重みのまま)でおこうとAIが判断するためです。

    • 初期配置

    作ってみて感じたのですが、3三将棋の場合適当に駒を配置すると将棋の上級者が見るとすぐに勝敗が明白な局面になっていたりして、面白い勝負になりそうな初期配置を探すのが一番難しいかもしれません。とりあえず勝負が楽しめそうな配置で尚且ついろんな種類の駒を使うことを考えて「9マス将棋」なども参考にしながら15種類の局面を用意しました。今後、追加していく予定です。

    Menu - 初期配置

    • 初期配置検索機能

     初期配置パターンが100を超えてきたので、Version1.0.2.6から初期配置検索機能を付けました。

    Menu - 初期配置検索

     駒を選択して検索ボタンを押下すると、持ち駒あるいは盤上にその駒を使用している初期配置がリストアップされます4。駒の選択条件はアンド(&)検索になっているので、例えば「角」と「香」を選んで検索すると「角」も「香」も使用されている初期配置だけが検索結果に表示されます。

    Menu - 初期配置検索結果

    • 駒の動きガイド
       駒の動ける場所と、棋譜の入出力に使用する「駒の略号」を一覧表にしました。

    略号
    動き 裏(成駒) 動き

    OU
    - -

    HI
    |︎

    RY
    |
    |

    KA

    UM

    KI
    - -

    GI

    NG

    KE
     ︎

    NK

    KY
    |︎

    NY

    FU

    TO

    多言語対応

     Version1.0.4.1から多言語対応しました。対応言語は英語、日本語、繁体中国語、スペイン語で、アプリで使用するメッセージが全てAndroidの言語設定で選んだ言語で表示されます。デフォルトは英語です。
     将棋の駒の動かし方を知らない人のために、このページの上部に駒の動きを表示することにしました。アプリ内メニューに駒の動き一覧表を追加しました。

    クリップボードを使った棋譜の入出力対応

     Version1.0.5.0からCSA形式(*.csa)の棋譜の入出力に対応しました。CSA形式(*.csa)では棋譜ファイルのヘッダー部分に駒の配置を定義出来るので、好きなように初期配置を定義して読み込ませれば自分が試してみたい初期配置から対戦が可能です。

    • 棋譜出力

    棋譜出力画面

     左上のチェックマークアイコンをタップすると共有画面(インテント)が表示されるので、クリップボードを選べばテキストファイルを扱えるアプリに棋譜データを貼り付けて保存出来ます。
     CSA形式の棋譜はヘッダ部分に駒の初期配置を定義出来る(駒落ち将棋にも対応している)ので、駒の初期配置パターンを選択出来るこのアプリに都合がいいと思ったので採用しました。但しCSA形式の規約を全て網羅しているわけではなく、必要最小限の部分だけ実装しています。Tで始まる指し手の消費時間や$で始まる棋譜情報は出力されません。以下が出力される棋譜の一例です。

    ' #3三将棋 https://play.google.com/store/apps/details?id=shogi33.io.github.happyclam 
    'No. 52
    '
    V2.2
    N+AI
    N-AI
    P1+OU-KA * 
    P2 *  *  * 
    P3 * +KA-OU
    P+00KE
    P-00KE
    +
    +3121OU
    -1323OU
    +0011KA
    -0013KA
    +0033KE
    -0031KE
    +1122KA
    -1322KA
    
    • 棋譜入力

    棋譜入力画面1

     テキストボックスに棋譜テキストデータを貼り付けて読み込みボタンをタップすれば、棋譜を読み込みます。このアプリ自身が出力した棋譜データは読めますが、他のソフトから出力された棋譜データや自前で作成した棋譜データは読み込みに失敗するかもしれません。エラーが発生した場合はその行数を表示しますので、データを編集して試してください。
     ※カンマ区切りのマルチステートメントには対応していません。
     ※たとえCSA形式(*.csa)の棋譜であっても本将棋(9×9)の棋譜は読めません、3三将棋専用です。

    棋譜入力画面2

     棋譜を読み込んだ後は通常の対局通り、対局者を変更したり局面を戻して途中から指し継いだり出来ます。

    独自の初期配置から対局開始する例

     9マス将棋の答えを知りたい、特定の局面を検討したいと思っていた人に役に立つと思います。
     棋譜ファイルはCSA形式(*.csa)のルールに従ってアルファベット2文字からなる駒の略号を使って記述します。CSA形式(*.csa)の規約を網羅しているわけではないので、必要最小限のデータの例は以下のようになります。

    P1 *  * -OU
    P2 *  *  *
    P3+OU *  *
    P+00KA00FU
    P-00GI00GI
    +
    

     Pに続く盤面データ持ち駒データ、それに続く手番データの3つを記述すれば読み込んで対局可能です。駒の無い升目は * (スペース+アスタリスク+スペースの3バイト)で、持ち駒は00に続けて駒の略号を記述します。駒の略号についてはこのページの「駒の動きガイド」の表かアプリ内にある「駒の動き」メニューを参照してください。

    棋譜入力画面

     必要最小限の上記データを読み込んだ直後の画面です。ここで「再開」ボタンをタップすると通常通りゲームを開始できます。
     誤って「新規対局」ボタンをタップすると読み込んだ棋譜ではなく、現在「初期配置」メニューで選ばれている初期配置から新規対局が始まってしまうので気をつけてください。

    出力される棋譜ファイルの例

    1. 上記の初期盤面からAI同士で対戦した後の出力ファイル例
      ' #3三将棋 https://play.google.com/store/apps/details?id=shogi33.io.github.happyclam 
      '
      '
      V2.2
      N+AI
      N-AI
      P1 *  * -OU
      P2 *  *  *
      P3+OU *  *
      P+00KA00FU
      P-00GI00GI
      +
      +0022KA
      -1121OU
      +0032FU
      -2112OU
      +3231TO
      -0023GI
      +3132TO
      -2332GI
      +3332OU
      -0021GI
      +3231OU
      -2122GI
      +3132OU
      -0021KA
      

       手番データの後に指し手データが続きます。

    2. 初期配置メニューのArrange4を選んでAI同士で対戦した後の出力ファイル例
      ' #3三将棋 https://play.google.com/store/apps/details?id=shogi33.io.github.happyclam 
      'No. 4
      '
      V2.2
      N+AI
      N-AI
      P1 * -KA-OU
      P2 *  *  * 
      P3+OU+KA * 
      P+00HI00FU
      P-00HI00FU
      -
      +0032FU
      -0012FU
      +3231TO
      -1213TO
      +3121TO
      -1121OU
      +0032KA
      -2131OU
      +0021HI
      

       アプリ内のメニューから初期配置を選んで棋譜ファイルを出力した場合は、コメントとして初期配置の番号(No. 4)が出力されます。

    読み込みエラーの意味

     独自に編集した棋譜ファイルを読み込む場合はエラーになる可能性があります。以下の表を参考に棋譜ファイルを編集して再度読み込みを試してみてください。

    エラー番号 エラーの意味、可能性のある原因
    01 盤面データの一行が長すぎるか短すぎます。駒のない場所はスペース+アスタリスク+スペース( * )の3バイトです。
    盤面データは一行ずつ改行する必要があります。
    02 盤面データのアルファベット2文字の駒の略号が間違えている可能性があります。
    03 持ち駒データのアルファベット2文字の駒の略号が間違えている可能性があります。
    04 盤面データの先頭Pの文字の次は、数値か+-です。
    05 指し手データの持ち駒を打つ時の記述が間違えている可能性があります。
    06 指し手データの指し手に誤りがあります。飛車(HI)が成っていないのに斜め後ろに移動している等
    07 P+-'VT%N$以外の文字が行の先頭にあります。
    ちなみにP+-以外の文字は読み飛ばして無視しています。
    08 指し手データのアルファベット2文字の駒の略号が間違えています。
    09 手番データ(+-)は盤面データが記述された後に書かれている必要があります。

    駒に毛筆フォント

     Version1.0.7.3から駒のフォントに毛筆フォントを選べるようになりました。無料フォントの中でも「衡山毛筆フォント」のように再配布可能というものはなかなか無いと思います。

    フォント選択メニュー


    衡山毛筆フォント

    Push通知対応

     Version1.0.9.2からPush通知を受信できます。左上右側にあるアイコンをタップすると受信した最新のメッセージを再度表示します。受信したメッセージがないときは何も表示されません。

    Push通知サンプル

    ソースファイル

     githubでCoffeeScriptのソースファイルを公開しました。GUI部分にはまだバグが潜んでいるかもしれませんが、思考ルーチン部分はほぼ落ち着いていると思っています。実際のアプリの先読みメソッド(思考ルーチン)は、浅い先読みを行い候補手のリストを作成しその候補手リストからさらに深読みするという方法を取っているのですが、混みいったコードになるのでその部分は省いています。リリースしてからバグを発生させていたのはほとんどこの候補手を絞り込む部分に関するもので、基本的なところはリリース当初からほとんど変わっていません。対戦型将棋ソフトを作る上で必要最低限なコードになっていると思います。このコードを元に3三将棋だけでなく9×9の本将棋に移行するのも容易だと思います、というか元々Rubyで作った自作の将棋ソフトのコードをスマホアプリにするためにCoffeeScript(JavaScript)に書き換えたものです。
     今度はMINI-MAX法+αβ法ではなく学習型のAIに挑戦したいと思っています。

    開発資料

    • クラス図

    クラス図

    • テストツール
       mocha + chai でテストケースを書きました。CoffeeScript+mocha+chai=CaffeineJSと誰かが言ってましたが、まさに依存性のあるカフェインのように癖になりそうなぐらい作りやすかったです。いずれgithubでソースもテストスクリプトも公開する予定です。その時はこの記事を更新します。

    • コンソール版

    CUI版

     最初は作り易さもあってコンソール画面でも遊べるCUI版(Gameクラス、Boardクラス)から作っていたのですが、将棋の指し手は複数の駒が動ける可能性がある時に「1一銀右」とか「3二銀引成」とか「3一金直」とかいろんなケースが発生するので、それをコンソール画面でコマンドラインのパラメータとして入力させる処理が非常に面倒になります。だから一通りコンソールでも遊べるようになったところで細かいところは未対応のまま放置してGUI版の開発に移行しました。GUIなら駒をタッチ(クリック)するだけなのでUI(ユーザーインターフェース)が作り易くなるからです。それでもコンソールで作っていたBoardクラスは変更を加える必要がなくそのまま継承してBoardGUIクラスを作るだけで済むのはオブジェクト指向プログラミングの面目躍如と言ったところです。


    1. 他の将棋アプリなら当たり前のように実装されている機能だと思いますが、このアプリは将棋盤をアプリで描画しているのではなく、駒(ベクターデータ、*.svg)やボタンのオブジェクトを配置することで将棋盤を形成しているため簡単ではありませんでした(HTML製のWebページを反転させることを想像していただくと分かり易いと思います)。また、svgファイルを上下左右反転させるためにAndroidのバージョンの必要要件を上げる必要がありました。他のアプリ(5五将棋アプリ7七将棋アプリ禽将棋アプリ歩なし将棋アプリ)も順次変更していく予定です。 

    2. 具体的にはtoString()関数を徹底的に排除して数値のまま処理したことと、末端ノードに達する前に局面の静的評価をして先読み再帰関数の終了条件を増やしたことです。 

    3. 三手詰めと書くと誤解を与えるので「三手以内の詰み」としています。詰将棋のように王手の連続で詰ますわけではなく、相手が指す手がなくなるような状態も含めて三手以内で勝つという意味です。 

    4. 今後初期配置パターンが増えてきたら、持ち駒は含めずに盤上の駒だけを検索するように変更するかもしれません。 



    blog comments powered by Disqus