俺氏、将棋が二人零和有限確定完全情報ゲームでないことに気づいてしまうwww

このブログをご覧の方は将棋が二人零和有限確定完全情報ゲームであることはご存知でしょう。これは、ゲーム理論や探索アルゴリズムの教科書にでも載っています。「二人零和有限確定完全情報ゲームって何?」って方は、Wikipediaでも見ていただくことにして話を先に進めます。

零和とは?

この「零和」というのは、和が零。英語で言うとゼロサムです。

零和(「ゼロ和」と読むのが一般的だが「レイワ」とも読む):プレイヤー間の利害が完全に対立し、一方のプレイヤーが利得を得ると、それと同量の損害が他方のプレイヤーに降りかかる

https://ja.wikipedia.org/wiki/二人零和有限確定完全情報ゲーム

つまり、自分が勝ちなら、相手は負け。相手が勝ちなら自分は負け。勝ちを+1点、負けを-1点、引き分けを0のように定めるなら、(ゲーム終局後に)自分と相手の点数を足すと0になる。なので、ゼロサムゲームと呼ぶわけです。同時に、(上の引用部に書いてあるように)ゲーム中の利害も完全に対立していて、評価値に関してもゼロサムとなります。

評価値がゼロサム

ゲーム中の評価値eに関しても先手側(先手から見た評価値)が +e なら後手側(後手から見た評価値)は -e となります。

// eの取りうる範囲は、-∞(負け)≦e≦+∞(勝ち) ですが、16bit符号付き整数の範囲に収めたいので、ここでは -32000≦e≦+32000 として、-32000 = 詰まされている局面 , +32000 = 詰ましている局面、0 = 互角の局面 とします。

この定義は、先手が勝ち(e = +32000)のとき、後手は負け(e = -32000)であるので、一見正しいように見えます。

非対称な探索

普通、局面を評価(点数付け)するために評価関数を呼び出すのですが、これは先手から見た評価値を返すように設計されてるのが普通なので、後手番の時は(自分から見た評価値にしたいので)その評価関数から返ってきた値の符号を反転させて用います。

つまり、探索中の先手の局面と後手の局面とで同じ評価関数を用いていることになります。ところが、例えば、相手のプレイヤーが「この局面はこう評価する」ということがわかっている場合は、探索中の相手番の評価関数は、その相手モデル(相手プレイヤーの使っている評価関数)を用いたほうが自分がより有利な局面に誘導することができます。

// この非対称な探索に関して、将棋AIの論文としては、「OM-search」(1994)などがあります。詳しく知りたい人は「OM-search」でググってみてください。

まあ、相手モデルに対して何の仮定もできないことが普通なので、将棋ソフトでは相手も自分と同じ評価関数を用いていると想定して探索します。つまり、この時、自分が勝ちだと思っている局面は、相手にとっては負けなのです。

Contempt

では、千日手に関してはどうでしょうか?

Stockfish(やねうら王が参考にしているチェスのソフト)では、Contemptというエンジンオプションがあります。これは、引き分けを回避する意欲みたいなものです。この値が大きいと引き分けを避けます。例えばこの値が100だと、引き分けの局面の評価値を -100 だと思って探索します。互角の時の評価値が0、歩一枚の価値が100なので、歩一枚の価値に満たない損なら、その損を受け入れてでても千日手を回避しようとします。

// https://www.chessprogramming.org/Contempt_Factor

やねうら王もContemptというエンジンオプションが以前はありました。
// 最近千日手のエンジンオプションを改良したので、Contemptはなくなりましたが。

WCSC29で何故やねうら王はContempt = -200に設定したのか?

千日手にしたい時は、Contemptの値を小さくすれば千日手を選びやすくなります。2年前に開催されたWCSC29(第29回世界コンピュータ将棋選手権)では、最後の試合でやねうら王側はContempt = -200に設定して意図的に千日手を狙い、試合開始早々に狙い通り千日手になったことで、これで優勝を決めました。

// https://yaneuraou.yaneu.com/2019/05/06/wcsc29、やねうら王優勝しました!/

じゃあ、この時、なぜ私はContempt = -∞(-32000)に設定しなかったのかということです。

単純に千日手にしたいなら、千日手を勝ちと思って探索してくれたほうが、千日手を見つけやすくなるのではないのかと。そういう疑問を抱かれる人もおられるでしょう。

大会中に、私は一度 -32000 に設定しようとして、「あれ、これまずいんじゃ…」という考えが頭によぎり、-200に変更したのを覚えています。大会が終わって、そのことはすっかり忘れていたのですが、その思考過程を以下に書いていきます。

Contempt = -32000

に設定した場合、確かに探索開始局面の手番側の局面(仮に先手とします)で千日手に遭遇した時にそれを勝ちとみなすようになります。

しかし、それは同時に後手の局面で千日手に遭遇した時は、(後手の)負けとみなすことになります。

これは本記事の冒頭に書いたようにゼロサムゲームであるなら、自分と相手の利害は対立しており、先手の勝ち = 後手の負け なのですから、これは一見、自然な挙動のように思えます。

// このようにゼロサムゲームでは利害は対立しており、探索には先後に対称性があります。

しかし実戦では、後手はそこまで全力で千日手を回避してくるとは限らないのです。実際、この時の対局相手である白ビールチームは、Contemptをデフォルト設定のままにされていたはずです。(白ビールチームは千日手引き分けになるとソルコフの関係上、優勝を逃してしまうことに気づいていなかったため。) このように相手の探索モデルがわかっている場合は、上で紹介したOM-searchのように先後非対称な探索が有効になります。

具体的には、

1)
先手の局面 = 千日手の評価値を勝ち(+32000)
後手の局面 = 千日手の評価値を引き分け(+0)

と思って探索させれば、

2)
先手の局面 = 千日手の評価値を勝ち(+32000)
後手の局面 = 千日手の評価値を負け(-32000)

と思って探索するよりも高い確率で千日手局面に誘導できます。

ところが、やねうら王には1) のように非対称な千日手スコアを設定する機能がないので、

3)
先手の局面 = 千日手の評価値をやや有利(+200)
後手の局面 = 千日手の評価値をやや不利(-200)

のように設定したということです。3)のほうが、2)よりはマシ(高い確率で千日手局面に誘導できそう)だと私は判断しました。

こと千日手のスコアに限っては、1)のように、先手と後手とで+eと-eのようにゼロサムになるとは限らないのです。

両者千日手を狙いたい場合

また、大会では、「この試合は両者引き分けになるほうが得だ」というケースがたまにあります。

// 例えば、相手チームにも上位8チームに入賞して予選を通過させたいとお互いに思っているような場合、両者意図的に引き分けを狙いたいです。

この場合、両プレイヤーとも

4)
先手の局面 = 千日手の評価値を勝ち(+32000)
後手の局面 = 千日手の評価値を勝ち(+32000)

と設定して探索させたいです。(この時、先後の利害が対立していないのでゼロサムではなく、先後に関して非対称な探索だと言えます。)

// こういう探索であれば、58玉、52玉、59玉、51玉のような手順を繰り返して開始速攻で千日手になるかもしれませんね。

千日手のスコアに対して先後非対称な探索について

しかし、4)のような先後、非対称な探索を行わせるのは、わりと難しいです。

例えば、dlshogiには、draw_value_black , draw_value_whiteという、探索中にleaf node(末端の局面)で千日手の局面に遭遇した時に、その局面のスコアをどうみなすかの設定があります。先手の手番の局面であれば、draw_value_blackの値が採用され、後手の手番の局面であれば、draw_value_whiteの値が用いられます。

「じゃあ、draw_value_black = draw_value_white = 1.0(勝ち)」に設定すれば、上の4)に相当する探索になるのではないか」と思われるでしょう。

ところが、親ノード(親局面)では、子ノードと手番が反転するので、期待勝率も反転するものとして、dlshogiのUctSearch()では、次のように期待勝率を反転させて返しています。(このように親ノードに対しては評価値(or 期待勝率)を反転させて返すのが普通です。

// 期待勝率は、0.0なら0%(負け)、1.0なら100%(勝ち)なので、期待勝利に関して「反転」と言う場合は、1.0から引き算することを意味するこことに注意しましょう。
// 子ノードでの期待勝率0%なら親ノードはその子ノードへ至る指し手を選んだ時の期待勝率は100%、子ノードでの期待勝率100%なら親ノードはその子ノードへ至る指し手を選んだ時の期待勝率は0%。なので、親ノードに対して子ノードはこのように、反転した期待勝率を返しています。

なので、子ノードがこの指し手で勝ち(期待勝率=1.0)だとして親ノードにその情報を返すと、親ノードからはその子ノードに至る指し手の期待勝率は負け(期待勝率0%)に見えるので全力でこの指し手を回避する挙動となってしまいます。実際は引き分けだから勝ち扱いだというのに…。

// よって引き分けに関しては、期待勝率を返すのではなく、引き分けであるという情報自体を返すのが正しい実装なのですが、そういう風に実装されている探索部のほうが稀というか、そんな非対称な探索を行うことを想定していないのが普通というか…。

結論的には、現状のdlshogiでは「draw_value_black = draw_value_white = 1.0(勝ち)」のように設定した場合、意図通りの挙動にはならなくて、千日手は狙ってくれないということになります。なので、このオプションの設計はおかしくて、leaf node(探索の末端の局面)で先手の千日手のスコアがdraw_value_black だとしたら、その時の後手の千日手のスコアは 1.0 – draw_value_black になっているのが自然です。

// この問題に関しては、dlshogiのissueに私が投稿してます。 → https://github.com/TadaoYamaoka/DeepLearningShogi/issues/36

それとは別に大会では、先手番の時は千日手を回避したくて、後手番の時は千日手を狙いたいというようなことが多いので、root node(探索開始局面)の手番が先手の時と、後手の時とで異なる千日手のスコアを設定したいのです。

つまり、
・root nodeが先手の時、leaf nodeが千日手の局面であれば、それが先手の局面であれば、draw_value_black , 後手の局面であれば、 1 – draw_value_black
・root nodeが後手の時、leaf nodeが千日手の局面であれば、それが後手の局面であれば、draw_value_white , 先手の局面であれば、 1 – draw_value_white
のようになっていたほうが使い勝手が良いと思われます。

そんなこともあって、最近、やねうら王・ふかうら王で千日手のエンジンオプションをそのような仕様に変更しました。

千日手エンジンオプションの変更(やねうら王のGitHub) : https://github.com/yaneurao/YaneuraOu/commit/aca35b5aa644d3d837ce2a134693f680f7285d7f

まとめ

両方のプレイヤーが千日手を勝ちだと思っている場合、利害が対立せず、ゼロサムとは言えない。利害が対立するのが「二人零和有限確定完全情報ゲーム」の「零和」の意味するところであるなら、この場合、将棋は二人零和有限確定完全情報ゲームとは言えない。

俺氏、将棋が二人零和有限確定完全情報ゲームでないことに気づいてしまうwww」への15件のフィードバック

  1. うーん、何て言えばいいのでしょうかね。

    リーグ戦での成績を考えると両者引き分けを狙いたい
    ってなった時、それはそもそも「将棋の戦い」ではないと思います。
    あえて言うなら「リーグ戦の戦い」ですよね。

    なので将棋としてはやっぱり勝ちは勝ちで負けは負けで引き分けは引き分けなんですよ。
    よって将棋はあいも変わらず二人零和有限確定完全情報ゲームだと思います。

    まあ専門家ではないので何の確証もありません、はい。

    • お互いに引き分けを勝利だと思っている時、将棋というゲーム内で利害が完全には対立しませんので、ゼロサムの定義から、これはゼロサムゲームではないです。
      // この時の将棋を本来の将棋と言えるかは別として…。

      • 勝てば優勝はもちろんのこと、引き分けでも優勝、といったことは、将棋(に限定されませんが)というゲームとは関係のない状況ですよね。
        そんな盤外の事情を持ち出してきて「ほら、零和じゃないよ~」って、私、釈然としないんです。なんか違くね?って。

        一方で実際問題として、同量な利害の対立を大前提とした実装では対応できないケースがありえることが示されたわけで、「ほら、零和じゃないよ~」っていわれてそれなりに説得力も感じています。

        将棋は二人零和有限確定完全情報ゲームに分類されていますが、その前提として暗黙的に「勝利することが目標である」という条件付けがあるような気がします。
        「必ずしも常に勝利を目指すとは限らない、引き分けも勝利と等価と見なす」という条件を明示したがために二人零和有限確定完全情報ゲームから外れたのかな?

  2. リーグ戦の場合は二人ではなく、リーグ戦参加者全員でゼロサムってだけでは?

  3. サッカーで勝利の勝点3になったとき、2分けより1勝1敗の方が双方にとって望ましくなり、ゼロサムではなくなりました。現実には先勝したら敢えて負けることはないので、ゲームとしては面白くなって正解だったと思うようになりましたが。

  4. 今回の記事にある変更で、やねうら王は千日手スコアに関して先後非対称な探索ができるようになったということですか?
    wcsc29のくだりを例とすれば
    DrawValueBlack: 32000
    DrawValueWhite: 0
    とすることで(1)のような非対称探索ができるということです?(勘違いしてたらすみません)

    • 先後、非対称な探索はできないです。
      > DrawValueBlack: 32000
      これはroot color(探索開始局面の手番)が先手の時の引き分けのスコアです。
      root colorが、先手番なら引き分けを回避して、後手番なら引き分けを狙うみたいなことはできます。

      • ストックフィッシュベースの探索部のままでは、こちらの手番と相手番で基準を変えるのは難しいということでしたか。

        このオプションについては、例えばFloodgateとかで先手番スタートならひたすら千日手を狙って、後手番スタートならひたすら千日手を拒否するみたいな極端な設定なら
        DrawValueBlack: 32000
        DrawValueWhite: -32000
        のようにしておけばいいというわけですか、手番が事前にわからない大会とかだと高成績に重要そうですね。

        • > 先手番スタートならひたすら千日手を狙って

          その場合、相手もひたすら千日手を回避してくる想定なので(実際は相手はそんな設定にはなっていないと思われる)、ponderが当たらない問題がありますが。

  5. 現在の状況に応じて、毎回探索条件を設定しなければならないのですから、それも含めてゲームとすればやはりゼロサムのような気がします。

    ただしそれは将棋という競技で勝ち抜くゲームの戦略でしょうか。

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です