USIの時間管理(timeman)やろうぜ(^~^)?

はぶぶぶんぶんぶーん(^~^) ほよー(^~^) 公開下書き

USIの時間管理(timeman)やろうぜ(^~^)?

20210124shogi2a2b1.png
「 時間管理やろうぜ?」

kifuwarabe-futsu.png
「 やる気になったか?」

ohkina-hiyoko-futsu.png
「 時間切れになったら さっさと 思考を中断して欲しいのよ。
時間が切れても ずっと考えっぱなしにされたら 連続対局で もう対局が終わってるのに 手を指して エラー落ちするのよね」

ramen-tabero-futsu2.png
「 ゲームによって 持ち時間 の制度や 文化が けっこう異なるので 復習しておこう。
囲碁だと カナダ式、 将棋だと 秒読み、 チェスだと フィッシャー・クロック とか 何それ? みたいなのが よくある」

将棋の秒読みルール

kifuwarabe-futsu.png
「 あと 20分ー。 残り何分から 秒読みを始めるんだぜ?」

ramen-tabero-futsu2.png
「 残り1分から 10秒刻み、残り 10秒から 1秒刻みで やってくれだぜ」

kifuwarabe-futsu.png
「 あと 1分ー。 50秒ー、 40秒ー、 30秒ー」

ohkina-hiyoko-futsu.png
「 早く指しなさい」

ramen-tabero-futsu2.png
「 将棋の秒読みは 慌てて指さなくていいんだぜ」

kifuwarabe-futsu.png
「 あと 10秒ー。 9ー、 8ー、 7ー」

ramen-tabero-futsu2.png
(ピシッ)

ohkina-hiyoko-futsu.png
「 あと 7秒で どうすんの?」

kifuwarabe-futsu.png
「 あと 1分ー。 50秒ー、 40秒ー、 30秒ー」

ohkina-hiyoko-futsu.png
「 なんで また 1分から カウントダウンが始まってんの?」

ramen-tabero-futsu2.png
「 コンピューター将棋の 秒読み60秒 というルールでは、
持ち時間を使いきったあと に さらに 60秒 使えるんだぜ」

kifuwarabe-futsu.png
「 3ー、 2ー、 1ー、 持ち時間を使い切ったので、これより 1分で指せだぜ」

kifuwarabe-futsu.png
「 50秒ー、 40秒ー」

ohkina-hiyoko-futsu.png
「 早く指しなさいよ」

ramen-tabero-futsu2.png
「 1分以内に指せば、次も 60秒からカウントダウンになるんだぜ」

ramen-tabero-futsu2.png
(ピシッ)

kifuwarabe-futsu.png
「 50秒ー、 40秒ー」

ohkina-hiyoko-futsu.png
「 無限に時間が あらない?」

ramen-tabero-futsu2.png
「 だから コンピューター将棋では 手数制限 というルールがあるんだぜ。
何手の制限かは 大会によって異なるので調べろだぜ。
プロ棋士の対局では 近年、 500手 が上限に定められたな」

ramen-tabero-futsu2.png
「 時間の制限と、手数制限の2つがないと、コンピューターはいつまでも指してしまって、
大会が 時間通りに進行しないから、」

ramen-tabero-futsu2.png
(ピシッ)

ramen-tabero-futsu2.png
「 1日7時間30分ぐらい対局すると見積もって、 1対局は55分の間に終わって欲しいとか逆算して、
そこから さらに 時間の制限と、手数の制限が 逆算して設定されているんだぜ」

ohkina-hiyoko-futsu.png
「 フーン」

将棋の切れ負けルール

kifuwarabe-futsu.png
「 秒読みを 0秒 に設定したものが、切れ負けルールだぜ」

ohkina-hiyoko-futsu.png
「 持ち時間を使い切ったら負けのやつよね。道場とかでよくある時計の頭を叩くやつ」

フィッシャー・クロック・ルール

📖 フィッシャークロックルールについて:規則に優劣はあるか?

kifuwarabe-futsu.png
「 チェスがオリジナルで、 フィッシャー・モード というのが チェスにはある。
これは、持ち時間の他に 1手ごとに 加算時間 というものがあり、
持ち時間を使い切らずに1手を指したら 加算時間を 持ち時間に加えるというものだぜ」

ohkina-hiyoko-futsu.png
「 えっ? 何? もう1回言って」

kifuwarabe-futsu.png
「 1手指したら 加算時間をくれるんだぜ」

ohkina-hiyoko-futsu.png
「 分かった」

kifuwarabe-futsu.png
「 その他に、 コンピューター将棋協会(CSA)が WCSC(世界コンピュータ将棋選手権)で採用している
フィッシャー・クロック・ルール というものがあるぜ。
これは 手番が回ってきたら 加算時間をくれるんだぜ」

ohkina-hiyoko-futsu.png
「 何が違うの?」

kifuwarabe-futsu.png
「 1手を指したあとに 加算時間をくれるのが チェスの フィッシャー・モード。
1手を指す前に 加算時間をくれるのが コンピューター将棋の フィッシャー・クロック・ルール」

ohkina-hiyoko-futsu.png
「 分かった」

USIプロトコル

📖 USIプロトコルとは

go btime 60000 wtime 50000 byoyomi 10000

ramen-tabero-futsu2.png
「 👆 コンピューター将棋では、将棋所を使っていると、手番が回ってきたときに、上記のようなメッセージを将棋所が送ってくるので、
黒番は持ち時間残り 60,000ミリ秒、 白番は持ち時間残り 50,000ミリ秒、秒読みは両者 10,000ミリ秒 と分かるわけだぜ」

go btime 40000 wtime 50000 binc 10000 winc 10000

ramen-tabero-futsu2.png
「 👆 フィッシャー・クロック・ルールの場合、
黒手番の加算時間は binc、白手番の加算時間は winc で送られてくるぜ。
binc 10000 なら、黒手番の加算時間は 10,000ミリ秒だな」

kifuwarabe-futsu.png
「じゃあ さっさと実装してくれだぜ」

20210715shogi139.png

ramen-tabero-futsu2.png
「 👆 こうやって並べてみると、添え字が 5 のところが byoyomi か、 binc のどちらかかで
秒読みか、フィッシャー・クロック・ルールか 見分けられそうだな」

20210715shogi140.png

ramen-tabero-futsu2.png
「 👆 いくつの添え字で 何のデータが取れるか 前もって 調べておこうぜ」

実装編

tokens = input().split()

if tokens[0] == 'go':
  btime = int(tokens[2])
  wtime = int(tokens[4])
  byoyomi = 0
  binc = 0
  winc = 0
  if tokens[5] == 'binc':
      binc = int(tokens[6])
      winc = int(tokens[8])
  else:
      byoyomi = int(tokens[6])

  if phase == 1: # 先手
      time = btime + byoyomi + binc
  else:
      time = wtime + byoyomi + winc

ramen-tabero-futsu2.png
「 👆 これを このままコピーしても動かないけど、雰囲気はこんな感じだよな。感じろだぜ」

持ち時間の配分計画

kifuwarabe-futsu.png
「 持ち時間は どう使うのがいいんだぜ?
持ち時間10分、秒読み30秒の対局もあれば、持ち時間1分、加算時間2秒の対局もあるだろ?」

ramen-tabero-futsu2.png
「 序盤、中盤、終盤を区別せず、全ての手に 均等に時間を分けて、
チェックメイトしたり、されたりしたときに ちょうど時間を残さず使っているのが
一番 無難 だと思うぜ」

kifuwarabe-futsu.png
「 しかし、何手目にチェックメイトするとか、されるとか、対局を開始したときは 分からないじゃないか?」

ramen-tabero-futsu2.png
「 人間の将棋の手数は だいたい 130手前後らしいし、ざっくり 持ち時間を 130 で割って
1つずつ使うというのも 考え方だよな」

kifuwarabe-futsu.png
「 1分は 60秒しかないぜ?」

ohkina-hiyoko-futsu.png
「 1分将棋じゃ きふわらべちゃん 不利じゃないの。1手指すのに数秒 考え込むんだから」

ramen-tabero-futsu2.png
「 最低でも 1秒以上 使えだぜ。 0.5秒指しとか できないものとして 諦めろだぜ。
3手読みなら 1秒で指せるだろ」

time_sec = (btime + byoyomi + binc) / 1000 # 先手の場合

# 対局開始時に計算して記憶しておく
# 1手に割り当てる消費時間
# one_move_sec = time_sec / 130

# 2手目以降
think_sec = min(one_move_sec, time_sec)

# 最低でも 1秒は使おう
if think_sec < 1:
    think_sec = 1

ramen-tabero-futsu2.png
「 👆 雰囲気はこうかな」

kifuwarabe-futsu.png
「 それだと、加算時間を使いこなせないぜ」

time_sec = (btime + byoyomi + binc) / 1000 # 先手の場合
inc_sec = binc / 1000 # 先手の場合

# 対局開始時に計算して記憶しておく
# 1手に割り当てる消費時間
# one_move_sec = time_sec / 130

# 2手目以降
think_sec = min(one_move_sec, time_sec)

if 0 < inc_sec: # フィッシャー・クロック・ルール:
    # 最低でも (加算時間-1秒)は使おう
    if 1 < inc_sec && think_sec < inc_sec - 1
        think_sec = (inc_sec - 1)
else:
    # 最低でも 1秒は使おう
    if think_sec < 1:
        think_sec = 1

ramen-tabero-futsu2.png
「 👆 binc か winc に数字が入っていれば フィッシャー・クロック・ルールなんで、
最低でも 加算時間-1秒 は使うようにしようぜ」

反復深化探索

kifuwarabe-futsu.png
「 反復深化探索をやってないと、時間管理できないけどな」

ramen-tabero-futsu2.png
「 何だぜ それ?」

ohkina-hiyoko-futsu.png
「 反復深化探索だけで 1記事 書けるから、別記事でやりましょう!」

📖 反復深化深さ優先探索(IDDFS;Iterative deepening depth-first search)やろうぜ(^~^)?

kifuwarabe-futsu.png
「 👆 上の記事を読めだぜ」

ストップ・ウォッチを作ろうぜ?

ramen-tabero-futsu2.png
「 ストップ・ウォッチの考え方は 単純だぜ」

type Stopwatch struct {
    startTime Time
}

ramen-tabero-futsu2.png
「 👆 開始時刻 というデータだけ記憶するとしようぜ」

impl Stopwatch:
    func start( ):
        startTime = now( )    

    func elapsedSeconds( )
        return now( ) - startTime # ここで秒に変換しろだぜ

ramen-tabero-futsu2.png
「 👆 計測を開始する start という機能が欲しいだろ。
現在時刻を記憶しろだぜ」

ramen-tabero-futsu2.png
「 そして 経過時間を秒で取得する elapsedSeconds という機能も用意しようぜ。
現在時刻から startTime を引けだぜ。 どうやって 秒 に変換するかは、お前が 何とかしろ」

func go( ):
    stopwatch.start( ) // なる早

    // 反復深化探索、する
    iterative_deepening_search( )

ramen-tabero-futsu2.png
「 👆 将棋所から USIプロトコルの go コマンドを受け取ったら、他の初期化処理とか始める前の なるべく早くに、
現在時刻を 記憶しろだぜ」

var max_depth = 4

func iterative_deepening_search( 略 ):
    var best_value = -VALUE_INFINITE
    var best_move = Move(Resign)

    for depth in 1..max_depth + 1:
        // 探索しろ
        let (value, move) = search( depth )
        if is_time_up:
            // タイムアップしてたら、探索結果を使わず、ループを抜けろだぜ(^~^)
            break

        // タイムアップしてなかったら、探索結果を使えだぜ(^~^)
        best_value = value
        best_move = move

    return best_move

ramen-tabero-futsu2.png
「 👆 反復深化探索を書けだぜ」

// 探索部
func search( 略 ):
    // 中略
    for m in move_list:
        // 指すぞ
        // その前に
        if stopwatch.elapsed( ) >= 3:
            // タイムアップした探索結果は使わないぜ(^~^)
            return (Value(0), Move(Resign))

ramen-tabero-futsu2.png
「 👆 探索部のどこで タイムアップを判定すればいいのかは分からないが、お前がなんとかしろだぜ」

何度でもクリック!→

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位

光速のアカウント凍結されちゃったんで……。ゲームプログラムを独習中なんだぜ☆電王戦IIに出た棋士もコンピューターもみんな好きだぜ☆▲(パソコン将棋)WCSC29一次予選36位、SDT5予選42位▲(パソコン囲碁)AI竜星戦予選16位

Crieitは個人で開発中です。 興味がある方は是非記事の投稿をお願いします! どんな軽い内容でも嬉しいです。
なぜCrieitを作ろうと思ったか

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください!

ボードとは?

むずでょ@きふわらべ第29回世界コンピューター将棋選手権一次予選36位 の最近の記事