2016-05-05

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

追記(5/6) : 有力でかつ少しだけ激しい局面に入った時にその手が抹消される恐るべきバグを見つけてしまったので信頼性が揺らいできました

前回の記事から数か月がたっていた。
tokoharurakugaki.hatenablog.com

まずは、いろいろいじって数か月でわかったことを書いていき、
最近やってみたことの結果などを書いていきます。

そもそも前回やった8手は少なすぎて意味がない。
もっというと15手でもあんまり意味が無さそう
深さ22手くらい読ませないとあんまり意味がないのでは？
- 根拠 : Aperyの局面評価が収束するのが大体そのくらいだから。
- Fail High, Fail Low が起きるのは仕方ないのでそれを除くと22手くらい
やねうら王Classic-tceでは深さ22を読ませたいが、これは局面によって単位時間で読める深さが異なる。
この意味では矢倉が読んでくれやすそうなのでやはりこれを採用する
- つまり開始局面は新矢倉24手組
  - ln3kbnl/1r1sg1g2/p2p2spp/1pp1ppp2/9/2PPP1P2/PPSG1P1PP/2G2S1R1/LNBK3NL b - 25

アルゴリズム（ふんいき）
1. 読ませたノードのうち、一番読ませた方がよさそうなところをいい感じに決める
2. 読ませて少し展開 : ただしここはかなり適当。1~3手程度が展開される。
3. 1へもどる

生成局面数 : 数千

数千、とぼかしているのは、途中で生成順序のミスが見つかったり、細かい調整をしているので無駄な局面を多く生成していると考えられるため、正確な数を書いても意味がないから。

結果

千日手っぽい局面が大量に生成される。

大量に生成されている様子はおまけとして下に書く。

理由を考えると

この探索方法では、例えば激しめの展開の末端局面では評価値が大きく変化してしまう可能性がある
一回大きく変化してしまうと局面探索の優先度が大きく下がってしまう
特に矢倉で消極的な手を選び続けると互いに相手へ攻めていけない状況へは容易に到達してしまう

といった理由が重なってうまくいかなかったと思われる

どうすればいい？

回避策としてまず考えられるのは千日手のスコアを-100にするとかだが、この場合は千日手にできる手が多すぎる可能性が高くうまく機能しない可能性が高い。
適当に飛車を動かすだけで局面数は結構増え得るのに金銀玉なども動かして千日手的状況を保てる可能性が高いからだ。（もちろん千日手を避けた時の評価によるけど、どうせ穏やかな変化ばかり続くと考えるとあんまり期待は持て無さそう？と思ったり。）

したがって、ちょっとやそっと実装を変えたところで結果は大枠変わら無さそうに見えるので、ほとんど手詰まりに見える。

次はどうするか？

念のため千日手の評価を下げた版でもうちょっと眺めてみる。

あとは、どう穏やかに進行しても千日手を避けてくれそうで、深さ22くらいでもぱっぱと読んでくれそうな局面を開始局面にして調べる、ことですかねぇ。何があるんだろう。

おまけ

もちろん内部的には千日手は回避するようにしてますが、それでも厳しいですという意味合いの表です。
最適局面からの離れ具合が小さい局面ベスト300をベタッと貼ります。200局面が評価0になります。
読み方は、不正確な表現ですが、
左から最適局面からの評価の離れ具合、その局面の重要度、その局面のsfenとなっています。千日手かつそれが最適解なら離れ具合は0といった気分です。

2016-02-28

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

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

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

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

やりかた

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

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

今回の状況設定

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

結果

DropBoxにあげました。

www.dropbox.com

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

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

所感

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

2/28 11:39 追記

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

2015-06-20

D進ゲームにおける戦略

イントロダクション

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

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

2015-06-11

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}$

2015-03-30

1:2:1

1:2:1といえば ->

(x+1)^2の係数
パスカルの三角形3段目
競プロでは ... Air Pollution | Aizu Online Judge

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

$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)$ という風に示せるのでなるほど確かに定理は納得できる気もしてくるなぁ、と思ったのでした。

2014-09-15

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)$ でできる

2014-05-10

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の確率で入って綺麗に完成、という感じ
  - これで詰むパターンが多い
- 避けるために
  - 一手読みで対処
  - プレイ中は気持ちのいい同時マージの時の罠に気をつけるようにする
  - 下二段でごにょごにょするときに最下段にできるだけ一つは数字マスがあるように気をつけている

tokoharuの落書き帳

らくがきですよ