読者です 読者をやめる 読者になる 読者になる

tokoharuの落書き帳

らくがきですよ

将棋AIで定跡を作れるか試してみた

UPD : 2016.12.16 : この記事の情報は古いのでより新しい情報をご覧ください

最近はやねうら王nano, nano-plus

github.com
が登場しており、自分のようにまじめに開発する気はそこまでないけどいじってみたい人には非常にうれしい状況です。
ということで定跡っぽいものを生成できないか試すことにしました

やりかた

細かいことを説明するのは面倒なので雑に言います

  1. 下準備としてfloodgateから100局くらいそれっぽいのを持ってくる
  2. 定跡としてよさそうなところを定跡として、その各局面をやねうら王nanoに評価させる。(具体的には初手から30手までで数回以上出現した局面を抽出
  3. 指定局面から定跡をたどったりたどらなかったりしつついろんな局面を読む
  4. 新しく得られた局面とその評価値を定跡に書き込む, を繰り返す

今回の状況設定

  1. nanoさんには各局面で8手読んでもらう
  2. よく出現する局面は12手くらいまで読んでもらうように調節する
  3. 初期局面を新矢倉24手組とする(つまり6手より先は完全に未知)
  4. 30000局面くらいを調べてもらう

結果

DropBoxにあげました。

www.dropbox.com

この結果は今回生成した定跡(のような何か)の一部をピックアップしたものです。変化は評価値が僅差のものを恣意的に選んで打ち込みました。初手6八角は気力が途切れていたので打ち込んでいません(評価は-90くらいだと主張しています)。

追記(2/28 11:45)
肝心の評価値が分かりづらいので概要をここに書きます。
初手1六歩で +15点, 3七桂で-32点, 3七銀で-69点となっています。それ以外はこれ以下です

所感

  1. 定跡もどきは生成できた。うれしい。でも果たしてこの定跡はどの程度よさそうなのかがわからない。
  2. 主な結果について
    1. : この結果のままでいくと基本矢倉先手不利ということになってしまうけどほんまか?(特に定跡でよくある形がそこまでよくない結果に.)
    2. : 初手1六歩はまだまだサンプルが少ない雰囲気があるのでもう少し上下する可能性はありそう。
    3. 手元にあるBonanza6.0でこの局面を適当に調べさせるとまずは6四角がサジェストされる。定跡生成中にこの手もよく検討されていたが、現在の評価は-100点くらいに落ちてしまっている。
  3. 定跡の終わりについて : 定跡の終わりになるにしたがってその評価への信頼がなくなってくるので根元で最適といわれている変化でも最後のほうは割と怪しい手を指していそう。
  4. 調べた局面数について : 30000局面とか書いてるけど途中でアルゴリズムをガンガン変えているのでいろいろ怪しい。
  5. 今後その1 : 今はnano-plusに乗り換えてもう一度はじめから作ってもらってます。今回は探索深さを12手以上に設定してみました。この結果から、読む手数が増えた時に定跡と比較してどう異なるのかを見たいと考えています。例えばnanoが作った変化を確認するのにどの程度の時間がかかったのか、とか、そんな手は読まずに新たな方向へ旅立っている、とか。
  6. 今後その2 : ある程度いい感じのアルゴリズムに仕上がったと感じたらApery級のAIで同じようなことを試してみたい。
  7. ソースファイル : ローカルにgitで管理しているのですが、よく見るとコミットに人に見せちゃいけないものが入っていたので公開したくなくなりました。気が向いたらごにょごにょ直しますが、今のところ気は向いていません。
  8. ツッコミ募集!!! : 私は将棋倶楽部24で15級とかそんなもんの初級者です。正直何も分かりません。この変化入れるとどうなるの?とか普通に考えるとここでこの変化へいかないのはおかしい、などの意見があれば是非いただきたいです。誰か詳しい方は教えてください!


2/28 11:39 追記

ひとつ思い出したので追記します。初手からの探索も実は少しやっていたのですが、よくわからない方向へ旅立ってしまうのと、相掛り方面で5手爆弾に見事に引っかかってしまい、評価が悪く相掛りはまったく調べられなくなっていたりしました。読む深さがどうしても小さいためこういう問題はよく発生しているのではないかなと思います。

D進ゲームにおける戦略

イントロダクション

D進ゲームとは、 Thisnor氏による D進,それは苦しい という博士課程シミュレーションゲームのことである。このゲームは4つのコマンドをベースに博士学生を育て、D論提出を目標にするゲームである。
本記事では6/19終わり時点における、とりあえずクリアするためにとるべき戦略と、クリア後に他プレイヤー(博士)と戦うことができる「学会発表」でよい成績をとるための戦略を紹介する。
また、その成果として現在のプレイヤーのレベルを紹介し、最後にまとめと感想を述べる。

したがって、この記事にはある種のネタバレを含むので注意されたい。

続きを読む

Fekete's lemma

一つ前の記事と似てるような似てないような、なので書いておく

xを数列とする。任意の k,l \geq 1に対して
 x_{k+l} \geq x_k + x_l(優加法性) を満たすならば、
 \lim_{k \to \infty} x_k / k = \sup_{k} x_k / kを満たす


直感的には、とりあえず x_k / kが(どこかから)非減少列であることを示せてしまえればよさそうに見える。
しかし、この方針では厳しい。たとえば、
 x = (1,2,11,12,21,22,...)のように x_{2a+1} = 10a+1, x_{2a+2} = 10a+2ととれば優加法性を満たし、かつ
 aを大きくとることによって  x_{2a+1}/(2a+1)>x_{2a+2}/(2a+2)となる。

ということで、別の方針で示す必要がある。証明はCombinatorial Optimization (Schrijver)の2章の証明に説明を少し追加したものである。


 i,j,k \geq 1とする
優加法性から x_{jk+i} \geq j x_k + x_i
 i,kを固定して
 \liminf_{j \to \infty} x_{jk+i}/(jk+i) \geq \liminf_{j \to \infty} \frac{jx_k + x_i}{jk+i}
= \liminf_{j \to \infty} \frac{x_k}{k} \frac{jk}{jk+i} + \frac{x_i}{jk+i}
= \frac{x_k}{k}
最後の式はlimを飛ばして(無限大にもなりうるが)収束するのでliminfでも大丈夫。
また、この変形の最後でiを含まなかったので次のようにできる
 \liminf_{n \to \infty} \frac{x_n}{n} = \inf_i \liminf_{j \to \infty} \frac{x_{jk+i}}{jk+i} \geq \frac{x_k}{k}
よって、
 \liminf_{n \to \infty} \frac{x_n}{n} \geq \sup_k \frac{x_k}{k}とできる。

liminfとlimsupの定義から、
 \liminf_{n \to \infty} \frac{x_n}{n} \leq \limsup_{n \to \infty} \frac{x_n}{n} \leq \sup_n \frac{x_n}{n}なので、先ほどの式とあわせることで、これらには等式が成り立つことがわかる。

結局、liminfとlimsupが一致したので、limが存在することがわかり、 \lim_{n \to \infty} \frac{x_n}{n} = \sup_n \frac{x_n}{n}

1:2:1

1:2:1といえば ->

という感じですが次の性質が成り立つんですね

 A_0 = 0,\\ 2 A_i \geq A_{i-1} + A_{i+1} (i \geq 1)
ならば  i\geq 1 に対して  \frac{A_i}{i}は非増加列である.
言い換えると i\geq 1に対して  \frac{A_i}{i} \geq \frac{A_{i+1}}{i+1}が成立する.

証)
数学的帰納法による.
素数が2以下の場合,つまり \frac{A_1}{1}, \frac{A_2}{2}のみの時は 2A_1 \geq A_0 + A_2より非増加列.
 \frac{A_1}{1} ,\dots, \frac{A_n}{n} の数列が非増加だったとする.
このとき 2A_n \geq A_{n-1} + A_{n+1} \geq \frac{n-1}{n} A_{n} + A_{n+1}より
 \frac{A_n}{n} \geq \frac{A_{n+1}}{n+1}を得るため証明終わり.


この性質が何だという話ですが、これは劣モジュラ性について扱っている本を眺めていて副次的に出てきたものです。

劣モジュラ性とは,(素人なので嘘書いてる可能性がありますが)
素数 nの有限集合 Sの冪集合 2^S 上の分配束(集合の和積で閉じている)であるような部分集合 \mathcal{D}をとる.
この \mathcal{D}から実数への写像 fが劣モジュラであるとは \forall A, B \in \mathcal{D}に対して f(A)+f(B) \geq f(A \cap B) + f(A \cup B)を満たすことである.また通常 f(\phi) = 0としておく.

さらに劣モジュラ多面体というものを考えます。

まず, x \in \mathbb{R}^Sとする.この xを拡張して \forall A \in \mathcal{D},  y(A) = \sum_{a \in A} x(a)とする.
この時, \mathcal{D},劣モジュラfによる劣モジュラ多面体とは \forall A, \in \mathcal{D}, y(A) \leq f(A)となるような xの集合のことである.

定理
劣モジュラ多面体では y(S)= f(S) を満たす xが必ず存在する(証明略).

(ここからは \mathcal{D}=2^Sとする.)
先ほどの定理は大雑把な書き方をすると A \neq S, y(A) \leq f(A)なる複数の平面で切った後に y(S) \leq f(S)でまだ切れる余地がある(もしくは接する,かする)ことを意味している。(しかしすぐに証明できる気がしないし本当にそんなうまいこといってるのか?と思うわけなので具体的なことを考えていこうという方向です。)

さて、この定理が成り立つということは、例えば s_1,\dots,s_n \in Sとして  y({s_1}) \leq f({s_1}), y({s_2}) \leq  f({s_2}), \dots y({s_n}) \leq f({s_n})を満たす多面体 Pに対して \max_{x \in P}\sum y({s_i}) \geq f(S)が成り立つはずである。
ということは、 \sum f({s_i}) \geq f(S)が成立するはずである。
さらに言えば、 y({s_i}) y({s_i, \dots , s_{i+j-1}})として巡回的な制約を満たす多面体 P_jに関しても同様なことが成り立ち、
  \sum f({s_i, \dots, s_{i+j-1}}) / j \geq f(S)が成り立つはずである。(なお、 m \geq 0, s_{n+m} = s_{m}としておく)

ここで数列 A A_j = \sum_{i} f({s_{i}, \dots s_{i+j-1}}) , A_0 = 0, A_n = n f(S)とすれば劣モジュラ性の式を足しこむことによって冒頭の1:2:1な式が出てくるという話なのでした(背景説明が長い)。

そんで、ここで冒頭の性質が成り立つので、さっき出てきた式を  \sum f({s_i, \dots s_{i+j-1}}) / j = \frac{A_j}{j} \geq  \frac{A_n}{n} =  f(S) という風に示せるのでなるほど確かに定理は納得できる気もしてくるなぁ、と思ったのでした。

D問題(速報)

・なにこれ ->
D: 夕食 - Japan Alumni Group Summer Camp 2014 Day 4 | AtCoder

・解法の一例

自炊定数を Pとして初期自炊力(自炊のうまさ)をQとしておく。
日数は0-indexedとしておく。
 j日目の食堂幸福度を C_jとしておく。
さて、 K個食堂から選ぶこととする。
このとき 自炊幸福度を(足す分だけ)考えると  (N-K)*(N-K-1)/2 + Q(N-K)とできる。
 a_i日目( 0 \leq i \leq K-1)に食堂にいったとして
 a_i日目の幸福度は,
先ほどの自炊幸福度で差し引かなかった食堂に行ったことから来る幸福度の損失を含めて考えることで、
 a_i日目の時にできる幸福度は (N-K-(a_i-i))*(-1)*P + C_{a_i} と解釈できる。
(それまでに a_i-i回自炊をした。つまり、これ以降で自炊は N-K-(a_i-i) 回行うので,先程足した分から引く必要がある。

この評価で計算してみると
 PQ(N-K) + P\frac{(N-K)(N-K-1)}{2} + \sum_{i=0}^{K-1} -P(N-K-a_i+i)+C_{a_i}

Sumの外に出せるものを出すと
 PQ(N-K) + P\frac{(N-K)(N-K-1)}{2} - P\frac{K(K-1)}{2} -PK(N-K) + \sum_{i=0}^{K-1}  P a_i +C_{a_i}

 = PQ(N-K) + P(N-K)(N-K-1) - P\frac{N(N-1)}{2} + \sum_{i=0}^{K-1} P a_i + C_{a_i}

(最後の変形は別解から考えると出てくる式なのでイコールで結んでおいた。 以後の議論では必要ない変形)となる。
足し算の中身が a_iのみに依存している形になるので、これの最大値は
 b_i = Pi + C_iを定義してこれの大きい方から K個選択すれば良い。
しかも Kにも依存しないので b_iを始めに定義しておいて、 Kの値を0から順番に試していき最大値を出せば良い。 
したがってネックはソートのみ。時間計算量 O(N log N)でできる

2048をやるときに考えること

マス目の番号は
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
とする。

  • 安置場所
    • 自分の場合は上になるほど大きく、右上の隅に一番大きいセルを置く
    • つまり4の場所に2048をおいたりしている
  • 基本戦略
    • 隅に寄せる
      • いろんな所で言われてること
    • 大きな数字を下に作り残さないようにする
      • すぐにマージしないテクニックでその後を優位に進める
        • 例えば5の場所に16,9の場所に16, 10の場所に32,11の場所に16, 12の場所に8,13の場所に2があったとする
        • このときすぐに上を押したくなるけど, そうすると9の場所に2が入ってしまってその後そこに32をつくらないといけなくてこの場合だとかなり死にそう
        • そこで一旦右に動かして2をどかして(新しく入るのを考えると確率2/3ですが死ぬよりはまし)から上を押してほぼ連続で16, 32をマージする
      • 個人的な印象だけど最下段の8はできるだけ取り除くように注意する
        • 8が最下段真ん中で浮くと非常に辛くなる
  • 大事な数字を固定する
    • 大事な数字が隅から動いてしまったときに隅に新しい数字が生成されると一気につらくなる
    • これを阻止するため、固定状態を保つ
    • そのテクニック
      • 最上段へのマージの際にはできた後にすべての数字が異なるようにするのがベスト
      • 例えば32 64 128 512 ができていたら2段目以下で128を作るなど
    • 固定されていないとき
      • 大きな数字を作った直後はやはり非固定の状態になりやすい
      • 運頼みではあるができる限り粘る
        • 余裕手があればそれを保つ
        • 単に右マージする前に上をできる限り打つとか
  • 一方向しか動かせない事態の阻止
    • 割とよく発生する事象
      • 1/5の確率で入って綺麗に完成、という感じ
      • これで詰むパターンが多い
    • 避けるために
      • 一手読みで対処
      • プレイ中は気持ちのいい同時マージの時の罠に気をつけるようにする
      • 下二段でごにょごにょするときに最下段にできるだけ一つは数字マスがあるように気をつけている

なにかのもんだい

(略解ですが省きまくってる(というか雑)ので頑張って補完するかリプ飛ばしてください)

方針としては、一点を(x,y)に固定して、そのとき、もう一点をどこに置くかを考えます。
もう一点おける候補の場所の面積は1で、条件を満たす置き方の領域ををf(x,y)とします。
結局f(x,y)が平均どのくらいとれてるかをみればよいので、x,yで重積分してやれば良いという事になります。
ただ、f(x,y)をひとつの式で表すのが難しいので多少の工夫を加えます。
1つ目の工夫は最初に一点固定する領域を限定すること
2つ目は縦方向に交わるような点集合と横方向に交わる点集合を別々に計算してやること、です

1つ目の工夫ではタテ・ヨコ・ナナメに線を引いて正方形を8つの部分にわけると楽だと思います。

残りは立式をしてwolfram alpha先生に計算させた結果です


(途中で途切れてるけどコピペしてぶちこんでください)

http://www.wolframalpha.com/input/?i=Integral_0^%281%2F2%29+%28+Integral_0^x++++%28y%2F%281-x%29*x+%2By%2Fx*%281-x%29%29%2F2++dy+++%29+dx

www.wolframalpha.com/input/?i=Integral_0^(1%2F2)+(+Integral_(1-x)^1++++(y-1%2B1%2F(2y))++dy+++)+dx

以上の2つを足して8をかければ2/3になってこれが答え。

数値計算しても0.6666...くらいが出てきます

この問題作ったときは充分大丈夫そうな問題だと思っていたけど、
今見ると無限の元から1つの元を取り出す操作が大変怪しく感じますがどうなんでしょう。
まぁロープ切断問題も無限個から複数の点とってるしいいのかなぁ