将棋が強くなるために必要なたった一つのこと(笑)

将棋クエスト(http://wars.fm/shogi10)の10分の棋譜を使って、レーティング区分と40手目までの各駒の移動回数との関係を調べてみました。
40手目までなので片方のプレイヤーが20手指します。
予想通り、レーティングが低い人ほど玉の移動が少なく、1400未満の区分では1.19回と、1900以上の区分の2.39回の半分しか玉を移動しないという結果になりました。
その他の駒については玉ほど顕著ではないですが、角の移動がレーティング上昇と共に着実に減っている、銀移動が1400〜1600で多いのは棒銀の影響？、最上位が玉、香車の移動が多いのはおそらく穴熊の影響、などといったことが見てとれます。

結論：強くなるには玉を囲いましょう。
まあ玉を囲うからレーティングが高いというよりはレーティングが高いから玉を囲うという因果関係のような気もしますが・・。
私も将棋を覚えたばかりの中学生の時は、玉を囲うと攻められるので囲ってる暇がない、という感覚でした。

	歩	香	桂	銀	金	角	飛	玉
〜1400	7.65	0.26	0.49	4.13	2.12	2	2.12	1.19
1400〜1500	7.4	0.15	0.59	4.39	1.96	1.85	1.96	1.66
1500〜1600	7.5	0.17	0.53	4.42	1.98	1.72	1.82	1.92
1600〜1700	7.35	0.16	0.5	4.15	1.79	1.72	2.11	2.18
1700〜1900	7.19	0.22	0.55	4.1	1.9	1.7	2.1	2.19
1900〜	7.28	0.26	0.48	4.21	1.83	1.47	2.04	2.39

囲碁クエスト、将棋クエストなどのレーティング計算方法について

囲碁クエスト、将棋クエストのレーティングシステムについてよく聞かれるので説明しておきます。

ベースはごく普通のELOレーティングそのものです。
スタートは1500点、なんですが、表示は1000点にしています。あくまでも表面上で内部的には1500点です。
そして、40試合かけて1試合あたり(1500 - 1000)/40=12.5点を勝とうが負けようが表面レーティングに加えていきます。
つまり40試合プレーした段階で表面レーティング＝真のレーティングとなります。
そのため、例えば1局目で負けて真のレーティングが-10点だったとしても+12.5点があるので、表面上は+2.5点の増加ということになり「負けてもレーティングが上がった」という状況が生じることになります。
あくまでも表面上の話なので、負ければ真のレーティングは必ず下がります。

例えば、20試合/1250点と40試合/1500点の人は内部レーティングは同じです。前者はまだ12.5x20=250点の表面レーティングの上昇分を使い切っていないので。

わざわざこうした方式を取っている理由ですが、実力1200点の人が1500点スタートにしてしまうと、せっかく記録している最高レーティングが1局も対戦しない状態といったことになってつまらないと思ったからです。

以上が基本的な話で、あとはレーティングの更新の重み(ELOレーティングのKの値)を状況によって変えています。
まず、新人は早く実力通りのレーティングに近づくようKを大きく。対局を重ねるに連れてだんだんと小さくなっていきます。
逆に、新人と対戦する相手側の変動は小さくしています。
例えばレーティングが追い付いていない(表面レーティングではなく真のレーティングも追い付いていない)新人の強豪にごっそりとレーティングを奪われる、という状況を緩和するためです。
あとはハンディキャップ戦(置碁、駒落ち)と、対bot戦の変動も若干小さくしています。
ハンディなしの人間同士の戦いがレーティング形成の中心になるのがいいだろう、という判断です。

「将棋クエスト」Android版を公開しました

「将棋クエスト」Android版を公開しました。
https://play.google.com/store/apps/details?id=fm.wars.shogiquest&hl=ja
前回ここに記事を書いたのが６月９日で、その数日前くらいに着手したので、３週間ちょっとかかりました。
本当はiPhoneの審査にかかる１週間の間にAndroid版を完成させて同時リリースと目論んでいたのですが、なかなか計画通りにはいかないですね。
Androidはすぐにアップデートを出せるので、しばらく結構なペースで細かい修正を出していくと思います。

この３週間の間、サーバーの方も色々ありました。
例えば、botがたまに止まってしまったりとか。
botのエンジンは2007年ころの棚瀬将棋を引っ張り出してきて使ってるのですが、こいつが落ちる局面があるようで、一度エンジンが落ちてしまうとbotも全員死んでしまっていたので、そういう場合でも復活出来るようにしました。
あと、特に初級ユーザーの将棋も観戦して、botの強さの段階も充実させました。
今度また詳しく書くかもしれないですが、１手読みと２手読みの間にすさまじい差があるんですね。
これはレーティング差としてはっきりと出ました。
そこで、深さ1と2の間のレベルを深さ1.1手読み、1.2手読みという具合に作ってやったりしました。
これは以前YSSの山下さんに教えてもらった方法です。

まだ私が将棋クエストでやりたいことの5分の1も出来ていないですが、iPhone版はアーリーアダプターの方々のおかげで、公開当初から誰もいないという状態にはならず、その後も毎日着実にユーザーが増えているので、そこにAndroidからのプレーヤーが合流することで、より盛り上がってくれると嬉しいです。

「将棋クエスト」iPhone版を公開しました

かねてより作っていた通常将棋のオンライン対戦アプリ「将棋クエスト」のiOS版を公開しました。
https://itunes.apple.com/jp/app/id884971827

Appleの審査は提出してから審査が開始するまでいつもきっかり1週間かかっていたのですが、今回は4日目にふとサーバーの様子を見てみると、iPhoneから将棋の対戦待ちをしている人を発見。
自分以外にiOS版を持ってる人はいないはずなので、つまりAppleの人が審査のために対戦待ちしているということです。
その時点ではまだbotの用意をしてなかったので慌てて私自身が対戦待ちにして、見事Appleの人との対戦が組まれ、無事に審査も通りました。
あの時私が気づかなかったらどうなってたんですかね。
「対戦出来ないぞこら」と言って落とされていたのかどうか。
工夫した点など、色々書きたいこともあるのですが、またの機会に。
まずはAndroid版を急いで作らないといけないです。

「ついたて将棋オンライン」公開しました

YSSと彩の掲示板に投稿したものと同じ内容ですが・・

オンライン上でついたて将棋の対戦が出来るサーバーを作りました。
WEB、またはAndroidアプリ、Kindleアプリから対戦出来ます。
※iPhone/iPad版も作りました。
10回反則、持ち時間10分を使い切る、または普通に詰まされると負けです。
是非一度遊んでみてください。
WEB http://wars.fm/tsuitate?lang=ja
Android https://play.google.com/store/apps/details?id=fm.wars.tsuitate
Kindle http://www.amazon.co.jp/dp/B00HV6NE40
iOS https://itunes.apple.com/jp/app/tsuitate-shogi-online/id836504687

※Android版は将棋クエスト(https://play.google.com/store/apps/details?id=fm.wars.shogiquest)に統合しました。

技術的なこととしては、サーバーはnode.jsでWEBクライアントではbackbone.js使ってます。
Androidアプリは普通にJavaのSDKでこれもbackbone.js風に作っています。

コンピュータ将棋選手権にもクラウドが

決勝を観戦してきた。
今年はリモートが多かった。
中でもGPS将棋はクラウド(AmazonEC2)を利用。
ついに選手権にもクラウド時代到来なのか。
1.6$/hのインスタンス×40×10時間≒5万円くらいをメンバーで負担したとのこと。
選手権のために高いマシンを購入していたことを思えば安いかもしれない。
ただ、クラスタのオーバーヘッドがあるので１手１分は欲しいとの田中先生の弁もあった。

クラスタで数十コアというような話を聞いていると、今後のコンピュータ将棋において、細かい最適化にエネルギーを使うのはあまり意味がないんじゃないかと思った。
プログラミングコンテストで定数倍の最適化をほとんどしないのと同じように。

余談だが、優勝した伊藤さんが私の出身学科の先輩だったとは驚いた。

ShuffledPlaylist (SRM443 Div1 Hard)

だいぶ前にtopoderの王者petr氏のブログで言及されていた問題を勉強した。
http://petr-mitrichev.blogspot.com/2009/06/srm-443.html

The hard problem for the round is a reasonably complex example how matrix multiplication can chime in to speed up DP. If you want to learn the more advanced DP techniques, this problem might give you a level-up :)

こう書かれてはやらずにはおれない、と読んだときに思ったはずなのに早１年以上、ついに昨日やってみた。

問題は、
「色々な曲(最大数百曲くらい)が与えられていて、それぞれの曲にジャンル(最大9通り)と曲の長さ(1〜9)が設定されている。
これらの曲をそれぞれどういう順番で何回使ってもよいという条件のもと、minLength(1..10億)以上、maxLength(minLength..10億)以下の長さのアルバムを作る方法は何通りあるか？
ただしジャンル間には連続してはいけないものがあり、それは(最大)9x9のテーブルで与えられている」

minLength,maxLenghtが最大10億という条件から、行列の累乗に帰着というのは常識。
A^n = (A^(n/2))^2という再帰によりlog(n)のオーダーになるから。
しかしどんな行列？
あっさりあきらめて解説読んだ。

まず、グラフを考える。
各ノードは、ジャンルと現在演奏中の曲の残り時間(g,l)
これが81通り。
それにsourceとsinkを加える。
エッジをたどるのが1秒消費に相当する。
求めるものは、sourceからスタートしてこのグラフをぐるぐるとめぐりめぐってL秒以下でsinkまで行く場合の数。
隣接行列のL乗がノード間をL歩でいく場合の数になる、という事実を知っていると(解説を読んで知りました^^;)、上のグラフのエッジに適切な値を設定してL乗すればいいことが分かる。
エッジはどう設定するか。
・まず、sourceから各曲のジャンルg、長さlの(g,l)を接続。
　複数曲が同じ(g,l)に行く場合があるので、その場合は重みをつけて。
・l>1の場合は(g,l)から(g,l-1)へは重み1のエッジ。
・(g,1)から各曲の(g',l)へこれも曲数の重みつきエッジを設定。ただし、g=>g'が接続してよいジャンルの場合だけ。
・全ての(g,1)からsinkへ重み1のエッジ。

これで83x83の行列が出来たので、L乗すればよいようだが、それだとちょうどL秒のアルバムの総数になる。
いや、最初のsourceからスタートする最初の1秒は本当はないものなのでL-1秒。
いずれにしても、「ちょうど・・秒」で「・・秒以下」にならない。
これはもう一つエッジを加えることで簡単に解決する。
・sinkからsinkへのエッジ
うまいなあ。

以下に私が書いたコードを載せておく。
行列の演算ライブラリと引数の処理以外は行列の設定がほとんど全て。
ちなみに、行列の積で、tmp > 1000000000000000000LL と書いているのは余分なmodを減らすため。
これ入れないと最悪ケースで2秒以内で終わるか微妙なところだった。

#include 

#include 

#include 

#include 

#include 

#include 

using namespace std;
#define MOD 600921647

typedef long long ll;
template

class MyMatrix {

    vector< vector > elements;

    int mod;
public:

    MyMatrix( int n, int mod_ ) : elements( n, vector( n ) ), mod(mod_) {}

    static MyMatrix identity( int n, int mod ) {

        MyMatrix m( n, mod );

        for ( int i = 0; i < n; i ++ )

            m( i, i ) = 1;

        return m;

    }

    

    T operator()( int i, int j ) const {

        return elements[i][j];

    }

    T& operator()( int i, int j ) {

        return elements[i][j];

    }
    MyMatrix operator*( const MyMatrix& m ) const {

        MyMatrix res( elements.size(), mod );

        for ( int i = 0; i < (int)elements.size(); i ++ ) {

            for ( int j = 0; j < (int)elements.size(); j ++ ) {

                T tmp = 0;

                for ( int k = 0; k < (int)elements.size(); k ++ ) {

                    tmp += elements[i][k] * m( k, j );

                    if ( mod && tmp > 1000000000000000000LL ) {

                        tmp %= mod;

                    }

                }

                if ( mod ) tmp %= mod;

                res( i, j ) = tmp;

            }

        }

        return res;

    }
    MyMatrix pow( int n ) {

        if ( n == 0 )

            return MyMatrix::identity( elements.size(), mod );

        if ( n == 1 )

            return *this;

        if ( n & 1 )

            return (*this) * pow( n - 1 );

        MyMatrix m = pow( n / 2 );

        return m * m;

    }

};
int node( int g, int l )

{

    return g * 9 + l + 1;

}
class ShuffledPlaylist {

public:

int count(vector songs, vector transitions, int minLength, int maxLength)

{

    int nGenres = transitions.size();

    string s = accumulate( songs.begin(), songs.end(), string("") );

    for ( int i = 0; i < s.size(); i ++ ) if ( s[i] == ',' ) s[i] = ' ';

    stringstream ss( s );

    vector genres, lengths;

    for ( int t; ss >> t; ) {

        int u; ss >> u;

        genres.push_back( t );

        lengths.push_back( u - 1 );

    }
    int nSongs = genres.size();

    int weight[83] = { 0 };

    MyMatrix A( 83, MOD );

    

    for ( int i = 0; i < nSongs; i ++ )

        weight[node( genres[i], lengths[i] )] ++;

    for ( int i = 1; i < 82; i ++ )

        A( 0, i ) = weight[i];

    for ( int g = 0; g < nGenres; g ++ )

        for ( int l = 1; l < 9; l ++ )

            A( node( g, l ), node( g, l - 1 ) ) = 1;

    for ( int g = 0; g < nGenres; g ++ )

        for ( int i = 0; i < nSongs; i ++ ) {

            if ( transitions[g][genres[i]] == 'Y' )

                A( node( g, 0 ), node( genres[i], lengths[i] ) ) = weight[node( genres[i], lengths[i] )];

        }

    for ( int g = 0; g < nGenres; g ++ )

        A( node( g, 0 ), 82 ) = 1;

    A( 82, 82 ) = 1;
    MyMatrix mh = A.pow( maxLength + 1 );

    MyMatrix ml = A.pow( minLength );
    return ( ( mh( 0, 82 ) - ml( 0, 82 ) ) % MOD + MOD ) % MOD;

}

};