なぎなぎブログ
Twitter YouTube

将棋ソフト開発 Week2 ~ USIに対応する! ~

2020-10-29 08:00:00
コンピュータ将棋

将棋ソフト開発 Week2 ~ USIに対応する! ~

プログラミングの勉強がてらに、将棋ソフト開発をしています。前回の1週目では将棋のコア部分について実装しましたが、2週目ではGUIを使えるようにUSIプロとコロルに対応をしていきます。2週目でやったこと、進捗報告、これからやることについて記載してきます。

これまでの記事はこちら
将棋ソフト開発 Week0 ~ 将棋アプリ開発始めます ~ | なぎなぎブログ
将棋ソフト開発 Week1 ~ 将棋のコア部分を作る ~ | なぎなぎブログ

目次

進捗報告

最低限のUSIプロトコルに対応して将棋所や将棋GUIで動くようになりました!

2週目でやったこと

  • sfenの理解
  • USIプロトコルの対応
  • 合法手のみ指すように修正

sfenの理解

sfenとは

SFEN(Shogi Forsyth-Edwards Notation) は将棋における駒の配置や、持ち駒、手番など局面の表記方法です。
もともとFENと言われる、チェスの局面の表記法がありそれの将棋版という感じのようです。

sfenは次のように4つの要素から構成されます
「<盤面の表記> <先手・後手の表記> <持ち駒の表記> <手数>」

例えば平手の初期局面は次のように表されます。
「lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL b - 1」

パット見ですとよくわからない文字列が続いてますね。
表記の仕方について詳しく見ていきます。

駒の種類の表記

先手の駒は大文字で表記、後手の駒は小文字で表記となります。

駒種 先手駒表記 後手駒表記 補足
K k Kingの頭文字
飛車 R r Rookの頭文字
B b Bishopの頭文字
G g Goldの頭文字
S s Silverの頭文字
桂馬 N n kNightより
香車 L l Lanceの頭文字
P p Pawnの頭文字

チェスをやってる方なら、金、銀、香 以外はチェスにも似た駒があるのでわかるかと思います。
金のGだけはGinとかと間違わないように注意ですね!

これに加え成駒の場合は駒の文字種の前に、「+」をつけます。
例えば先手のと金は「+P」と表記されますし、後手の成銀は「+s」といった感じです

盤面の表記

段ごとに表記し、各段は/によって区切られます。

<1段目の表記>/<2段目の表記>/<3段目の表記>/<4段目の表記>/<5段目の表記>/<6段目の表記>/<7段目の表記>/<8段目の表記>/<9段目の表記>

といった感じです。

格段は「駒の種類の表記」の項で説明した表記により、左側のマスから順に駒を表記します。

例えば将棋の平手初期局面のい1段目は「香桂銀金玉金銀桂香」と並ぶので対応する表記をすると「lnsgkgsnl」となります
2段目は「空飛空空空空空角空」と並んでますよね。※空きますを「空」としてます。

空きマスのときはいくつ空きマスがあるかで表現をします。
左から、 1つ空きマス、飛車、5つ空きマス、角、1つ空きマス
これをSFENの表記だと「1r5b1」となります。

3段目は歩が「歩歩歩歩歩歩歩歩歩」と並んでるので「ppppppppp」表される。
4段目は空きマスが9個ならんでいるので「9」と表される。

この具合で9段目まで表すと

「lnsgkgsnl/1r5b1/ppppppppp/9/9/9/PPPPPPPPP/1B5R1/LNSGKGSNL」という表記になります。

先手・後手の表記

先手であれば「b」(Blackの頭文字)
後手であれば「w」(Whiteの頭文字)

持ち駒の表記

持ち駒が先手後手共に何もないときは「-」と表記されます。

持っている駒種の表記は「駒の種類の表記」で説明したとおりですが、複数枚駒を持っているときは「<持っている駒の枚数><駒の種類>」という感じで表記されます。
例えば歩を3枚持っていたら「3P」というかんじですね。ちなみに1枚のときはコマの枚数は省略されてそのまま「P」と表記されます。

表記する際の順序ですが、まず先手の持ち駒が先に記載されます。
駒の種類にも順番が決まっています。

飛車、角、金、銀、桂、歩の順で記載されることになっています。

例として下記の持ち駒を表してみましょう
先手持ち駒: 飛車1枚、 歩3枚、銀1枚
後手持ち駒: 角1枚 歩2枚

「R3PSb2p」と表記されることとなります。

手数の表記

手数は何手目かを表しています。

さらにSFENの原案によると、次の手が何手目かという数字も表記する必要があります。ただし、任意局面から開始する場合など、次の手が何手目かという情報に意味がないので、これが必要なものかどうかよくわかりません。将棋所の場合、この数字は必ず1にしています。
将棋所:USIプロトコルとは より引用

ただ将棋所などGUIソフトによっては特に対応せず固定値を返すこともあるようです。

USIの対応

USI(Universal Shogi Interface)とは?

将棋所:USIプロトコルとは より引用

USI(Universal Shogi Interface)プロトコルとは、将棋GUIソフトと思考エンジンが通信をするために、Tord Romstad氏によって考案された通信プロトコルです。USIの原案は、以下で読むことができます。

将棋ソフトと将棋のGUIソフトとの間で通信(会話)するためののものです。具体的には こんな感じです

> usi
< id name naginagi_shogi
< id author NagiNagisa
< usiok 
> isready
< readyok
> usinewgame
> position startpos moves 7g7f
> go btime 0 wtime 0 byoyomi 3000
< bestmove 3c3d
> position startpos moves 7g7f 3c3d 6g6f
・
・
・

ちょっと何言ってるかわからない、って感じだと思うので、日本語での会話風にするとこんな感じです

GUIソフト> usi    // 起動したよー!
将棋ソフト> id name naginagi_shogi  // 私は将棋エンジン naginagi_shogi
将棋ソフト> id author NagiNagisa  // 作者はNagiNagisaだよ!
将棋ソフト> usiok // 自己紹介終わったよ どうぞ(無線会話風)

GUIソフト> isready  // 準備は出来てる?
将棋ソフト> readyok // 準備OKです!

GUIソフト> usinewgame // 対局を開始します

GUIソフト> position startpos moves 7g7f  // 平手初期局面(startpos)からの指し手は 7g7f(76歩)です
GUIソフト> go btime 0 wtime 0 byoyomi 3000  // 先手持ち時間0秒(btime)、後手持ち時間0秒(wtime) 秒読み 3秒(3000ミリ秒) で考えて指してください

将棋ソフト> bestmove 3c3d // 最善手は3c3d(34歩)です

GUIソフト> position startpos moves 7g7f 3c3d 6g6f // 平手初期局面(startpos)からの指し手は 7g7f(76歩) 3c3d(34歩) 6g6f(66歩) です。
GUIソフト> go btime 0 wtime 0 byoyomi 3000  // 先手持ち時間0秒(btime)、後手持ち時間0秒(wtime) 秒読み 3秒(3000ミリ秒) で考えて指してください
・
・
・
// 以下対局が終わるまで続く

最低限将棋ソフトがこの会話をできるようになれば、将棋所や将棋GUIなどの将棋GUIソフトで自分で作った将棋ソフトが動くようになります。

今回使うコマンドをもうちょっとだけ詳しく説明していきます。

usi コマンド

エンジン(将棋ソフト)起動時に最初に送られるコマンド。
GUIが将棋ソフトを登録するときにもこのコマンドで帰ってきた情報を使って登録されます。

このコマンド受け取ったときに、エンジンはidコマンドを返します。

id name <将棋ソフト名>
id author <作者名>

その後最後に エンジンはusiok を返します。

この手続きだけで将棋ソフトの登録だけはできちゃうんですよね。

例えばjavaなら下記の感じで書けばおそらくGUIソフト側に登録するだけなら可能です。

ちなみにUSIのやりとりは標準入出力でやり取りを行います。
javaでいえば、ScannerInputStreamReaderを使って標準入力を受け取り、System.out.print などで標準出力を行うことになります。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Sample {
	public static void main(String[] args) {
    boolean running = true;
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    while(running) {
      try {
        Optional<String> OptionalInputstring = Optional.ofNullable(reader.readLine());
        if (OptionalInputstring.isEmpty()) {
            continue;
        }

        String inputString = OptionalInputstring.get().trim();
        String[] command =  inputString.split(" ");

        switch (command[0]) {
            case "usi" -> {
                System.out.println("id name naginagi_shogi");
                System.out.println("id author NagiNagisa");
                System.out.println("usiok");
            }
            case "quit" -> {
                running = false;
            }
        }
      } catch (IOException e) {
        e.printStackTrace();
      }
    }
	}
}

isready

対局開始前にGUI側から送られるコマンドです。
なにかエンジン側で対局する準備の処理があればここで行うのでしょうけど、特になければ何もせずに単に"readyok"と返せばよいだけです。

実際今回作ったプログラムも今のとこはここでは何もしていません。

usinewgame

対局開始時にGUI側から送られます。
なにかエンジン側で対局開始時の処理があればここで行えます
特になければ何もせずに単に"usinewgame"と返せばよいだけです。

実際今回作ったプログラムも今のとこはここでは何もしていません。

position

これがとても大事なコマンド。 思考開始局面をエンジン側に知らせるためのコマンド。

思考開始局面をエンジンに知らせるためのコマンドです。エンジンに思考を開始させる場合、positionコマンドで思考開始局面を送り、それに続けてgoコマンドを送って思考開始を命令することになります。

position <sfen文字列 または startpos> moves <1手目の指して> <2手目の指して> .... <N手目の指して>

初期平手局面についてのみ、sfen文字列の代わりに「startpos」が使われます。

sfenに関しては前述のとおりなのでそちらを参照してください。

moves 以降は sfenで指定した局面からの指し手です。

指し手が進むたびにmovesの指しても増えていくので、ここはどんどん長くなっていきます。

ステートレスなリクエストになっていますね。

指し手の読み方

例えば初期局面から7六歩と動かす場合は 「7g7f」 と表記されます。

7gの地点にある駒を7fに移動するという意味になります。

数字の部分は筋を表してアルファベットのところは段を表し下記のように対応付けられています。

1段目: a
2段目: b
3段目: c
4段目: d
5段目: e
6段目: f
7段目: g
8段目: h
9段目: 1

go

goコマンドが送られると、positionコマンドで指定された局面から思考を開始します。

このgoコマンドの後に続くオプションで、思考時間などのオプションも突くのですが、一旦即時レスポンスを返すようにしているので、最低限の実装では、goコマンドが来たら、
指し手を即時返すようにしておけば動きます。

指し手を返すのはbestmove コマンドでエンジン側からGUIに返却します

bestmove

エンジン側からGUIに向けて返すコマンドです。

探索を終了して、この局面で最適な指し手を返却します。

bestmove <指して表記>

bestmove 3c3d

基本的にgoコマンドに対応したコマンドで、探索終了したときにこのコマンドを送ります。

実装

前回も紹介したこちらのクリーンアーキテクチャの図に近い形で実装しています。
実際には、今回はThreadつかったり、非同期にしないといけない場面があったりするのでイベントでやり取りするようにしています。
ちなみに、今回はイベントでのやり取りをやりやすくしたり、DIなど効率的な開発をするためにプレゼンテーション層とアプリケーション層ではSpringBootを使っています。

クリーンアーキテクチャ

画像は Clean Coder Blog より引用

InputPortの役割のGameManagerはこんな感じの定義

public interface GameManager {
    void init(InitEvent initEvent);
    void readyGame(ReadyGameEvent readyGameEvent);
    void startGame(StartGameEvent startGameEvent);
    void stopGame(StopGameEvent stopGameEvent);
    void startSearch(StartSearchEvent startSearchEvent);
    void stopSearch(StopSearchEvent stopSearchEvent);
    void setBoard(SetBoardEvent setBoardEvent);
}

InputPortの実装はアプリケーション層の方で実装を書きます。ここが図でいうInteractorの役割になります。

実装はこうなります。

@Service
public class GameManagerImpl implements GameManager {
    private final GameEventPublisher gameEventPublisher;
    private SearchService searchService;

    public GameManagerImpl(GameEventPublisher gameEventPublisher) {
        this.gameEventPublisher = gameEventPublisher;
    }

    @Override
    @EventListener
    public void init(InitEvent initEvent) {
        // 初期化処理を行う
        // 現状は特に何もなし
        gameEventPublisher.publishDoneInitEvent();
    }

    @Override
    @EventListener
    public void readyGame(ReadyGameEvent event) {
        // ゲームの準備の処理を行う
        // 現状は特に何もなし
        gameEventPublisher.publishDoneReadyGameEvent();
    }

    /**
     * ゲームを開始する(初期化をする)
     */
    @Override
    @EventListener
    public void startGame(StartGameEvent startGameEvent) {
        // ゲーム開始の処理をする
        // 現状は特に何も処理は無し
        gameEventPublisher.publishDoneStartGameEvent();

    }

    /**
     * ゲームを終了する
     */
    @Override
    @EventListener
    public void stopGame(StopGameEvent stopGameEvent) {
        // ゲーム終了の処理をする
        // 現状は特に何も処理は無し
        gameEventPublisher.publishDoneStopGameEvent();
    }

    /**
     * 探索を行うスレッド開始する
     */
    @Override
    @EventListener
    public void startSearch(StartSearchEvent event) {
        searchService = new SearchServiceImpl(board, gameEventPublisher);
        searchService.start();
        gameEventPublisher.publishDoneStartSearchEvent();
    }

    /**
     * 探索を終了する
     */
    @Override
    @EventListener
    public void stopSearch(StopSearchEvent event) {
        searchService.stopSearch();
        try {
            searchService.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        gameEventPublisher.publishDoneStopSearchEvent();
    }

    /**
     * ボードの初期化を行う
     */
    @Override
    @EventListener
    public void setBoard(SetBoardEvent event) {
        this.board = event.getBoard();
        gameEventPublisher.publishDoneSetBoardEvent();
    }
}

OutputPortの役割のOutputPresenterはこんな感じの定義

public interface OutputPresenter {
    void init(DoneInitEvent doneInitEvent);
    void startGame(DoneStartGameEvent doneStartGameEvent);
    void readyGame(DoneReadyGameEvent doneReadyGameEvent);
    void search(DoneSearchEvent doneComleteSearchEvent);
    void startSearch(DoneStartSearchEvent doneStartSearchEvent);
    void stopSearch(DoneStopSearchEvent doneStopSearchEvent);
    void setBoard(DoneSetBoardEvent doneSetBoardEvent);
}

OutputPortの実装はプレゼンテーション層に書きます。

@Component
public class OutputPresenterImpl implements OutputPresenter {

    @Override
    @EventListener
    public void init(DoneInitEvent doneInitEvent) {
        System.out.println("id name naginagi_shogi");
        System.out.println("id author NagiNagisa");
        System.out.println("usiok");
    }

    @Override
    @EventListener
    public void startGame(DoneStartGameEvent doneStartGameEvent) {
    }

    @Override
    @EventListener
    public void readyGame(DoneReadyGameEvent doneReadyGameEvent) {
        System.out.println("readyok");
    }

    @Override
    @EventListener
    public void search(DoneSearchEvent doneComleteSearchEvent) {
        Sashite bestSashite = doneComleteSearchEvent.getBestSashite();
        System.out.println("bestmove " + bestSashite.toUsiMoveString());
    }

    @Override
    @EventListener
    public void startSearch(DoneStartSearchEvent doneStartSearchEvent) {
    }

    @Override
    @EventListener
    public void stopSearch(DoneStopSearchEvent doneStopSearchEvent) {
    }

    @Override
    @EventListener
    public void setBoard(DoneSetBoardEvent doneSetBoardEvent) {
    }
}

標準入力から、イベントを発行するスレッドを定義します

@Component
public class InputControllerThread extends Thread {
    private boolean runnning = true;

    private InputStreamReader in;
    private BufferedReader bufferRead;
    private final GameEventPublisher gameEventPublisher;

    private InputControllerThread(GameEventPublisher gameEventPublisher) {
        this.gameEventPublisher = gameEventPublisher;
    }

    @PostConstruct
    private void init(){
        in = new InputStreamReader(System.in);
        bufferRead = new BufferedReader(in);
    }

    @Override
    public void run() {
        while(runnning) {
            try {
                Optional<String> OptionalInputstring = Optional.ofNullable(bufferRead.readLine());
                if (OptionalInputstring.isEmpty()) {
                    continue;
                }
                String inputString = OptionalInputstring.get().trim();
                String[] command =  inputString.split(" ");

                switch (command[0]) {
                    case "usi" -> {
                        gameEventPublisher.publishInitEvent();
                    }
                    case "isready" -> {
                        gameEventPublisher.publishReadyGameEvent();
                    }
                    case "usinewgame" -> {
                        // System.out.println("対局開始");
                        gameEventPublisher.publishStartGameEvent();
                    }
                    case "position" -> {
                        String[] moves;
                        int movesIndex;
                        Board board;
                        BoardBuilder boardBuilder = new BoardBuilder();
                        if (command[1].equals("sfen")) {
                            movesIndex = 6;
                        } else if (command[1].equals("startpos")) {
                            movesIndex = 2;
                            boardBuilder.setHiratePiece();

                        } else {
                            System.out.println("invalid position command");
                            continue;
                        }
                        board = boardBuilder.build();
                        // movesが存在しないときは初期配置を表すので、初期配置の盤をセットする
                        if (command.length == movesIndex) {

                            gameEventPublisher.publishSetBoardEvent(board);
                            continue;
                        }
                        if (!command[movesIndex].equals("moves")) {
                            System.out.println("invalid position command. moves not exists");
                            continue;
                        }
                        movesIndex++;
                        // usiStringからたどって現局面の盤を生成
                        for (; movesIndex < command.length; movesIndex++) {
                            Sashite sashite = SashiteFactory.create(command[movesIndex]);
                            board = sashite.execute(board);
                        }
                        // 現在の局面をセットするイベントを発行
                        gameEventPublisher.publishSetBoardEvent(board);
                    }
                    case "go" -> {
                        boolean ponder = false;
                        int btime = 0;
                        int wtime = 0;
                        int byoyomi = 0;
                        int binc = 0;
                        int winc = 0;
                        boolean infinite = false;
                        for (int i = 1; i < command.length ; i++) {
                            switch (command[i]) {
                                case "ponder" -> {
                                    ponder = true;
                                }
                                case "btime" -> {
                                    btime = Integer.valueOf(command[++i]);
                                }
                                case "wtime" -> {
                                    wtime = Integer.valueOf(command[++i]);
                                }
                                case "byoyomi" -> {
                                    byoyomi = Integer.valueOf(command[++i]);
                                }
                                case "binc" -> {
                                    binc = Integer.valueOf(command[++i]);
                                }
                                case "winc" -> {
                                    winc = Integer.valueOf(command[++i]);
                                }
                                case "infinite" -> {
                                    infinite = true;
                                }
                                default -> {
                                    System.out.println("invalid go option.");
                                }
                            }

                        }
                        // 時間管理のインスタンスを生成し渡す
                        // 時間間利用の別スレッドを作るアプローチもあるかもしれない
                        Time time = Time.of(btime, wtime, byoyomi, binc, winc, infinite);
                        gameEventPublisher.publishStartSearchEvent(time);
                    }
                    case "stop" -> {
                        // 探索を停止して指してを返すイベントを発火
                        gameEventPublisher.publishStopSearchEvent();
                    }
                    case "ponderhit" -> {
                        // 一旦使わないので処理は無し
                    }
                    case "quit" -> {
                        runnning = false;
                        System.out.println("quit shogi engine");
                        // 停止イベント発行
                        gameEventPublisher.publishStopSearchEvent();
                        gameEventPublisher.publishStopGameEvent();
                    }
                    case "gameover" -> {
                        // 対局結果
                        if (command[1].equals("win")) {
                            System.out.println("勝利");
                        }
                        if (command[1].equals("lose")) {
                            System.out.println("敗退");
                        }
                        if (command[1].equals("draw")) {
                            System.out.println("引き分け");
                        }
                        runnning = false;
                        System.out.println("quit shogi engine");
                        // 停止イベント発行
                        gameEventPublisher.publishStopSearchEvent();
                        gameEventPublisher.publishStopGameEvent();
                    }
                }

            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}

処理の流れのシーケンス図っぽいものを書くことこんな感じです。
赤いところはThreadのループだと思ってください。
シーケンス図

合法手のみ指すように修正

指し手を反則手を指さなくしました。
今まで王手放置などをしていて対局が終わっていたのですが、これで今回はちゃんと詰みまで指すようになってだいぶそれっぽい動きになってきましたね。

この実装は結構簡単で、反則手を含む候補手のなかから1手動かしてみて、
その局面で王手がかかっているかどうかを見て、王手がかかっていたら王手放置などの反則手なので、候補手からこの手を取り除く。
ということをやればよいわけです。

    public Sashite search(Board board) {
        Sashite bestMove;

        List<Sashite> candidateMoveList = board.candidateMoveList(); // 反則手を含む候補手の取得
        List<Sashite> legalMoveList = new ArrayList<>();  // 合法手をこのリストに入れていく

        // 反則手になる手があったら省く
        for (Sashite sashite: candidateMoveList) {
            Board nextBoard = sashite.execute(board);   // 1手先の局面を作る
            if (nextBoard.isCheck(nextBoard.nextTeban())) {  // 王手がかかってる状態だったらその手は反則手
                continue;
            }
            legalMoveList.add(sashite);  // 王手がかかっていない状態ならその手は合法手として加える
        }

        if (legalMoveList.isEmpty()) {
            // 合法手が存在しない、投了の手を返す
            return Resign.of();
        }

        // 合法手の中からランダムで指し手を選択して返す
        int randomIndex = new Random().nextInt(legalMoveList.size());
        bestMove = legalMoveList.get(randomIndex);

        return bestMove;
    }

探索部でやらずに、局面を見て、この駒はピンされてるからこっちにしか動けない、とか、効きがあるから玉はこっちに動けないとか考えることもできますが、
王手チェックの処理だけ書けばいいこっちの実装のほうが楽ではありますね。

計算量的には不利かもしれませんが、高速な強いソフトを目指しているわけではないので、シンプルな方を選んで作っていってます。

ピンのチェックとか後々必要になるかもしれませんが、それはその時に作ります。

これから取り組むこと

これから3週間目(week3)で取り組むことについて

  • 評価関数の作成

探索部を作るのを先にしようかと思いましたが、評価関数がないと困るので先に評価関数を作ることにします!
探索部と、評価関数が一番難しそうな気がするので、この辺は時間かかるかもしれませんが、じっくりやっていきたいと思います

参考リンク

参考にしたサイト