From yesterday, Twitter API behavior is changed, and the posts do
not contain Content-Length are refused by API server.
(Today (10/28 0:00JST), this behavior is fixed and no more treatments are needed. (kimrin))
This issue's workaround is already pull-requested by jschauma and
this code works fine.
In details, see GitHub:
https://github.com/tweepy/tweepy/pull/214/files
Most people who install tweepy is using easy_install, so actual tweepy/binder.py file
is under the egg file.
In my Mac, this file is in /Library/Python/2.6/site-packages/ and begin with tweepy-.
So silly and tentative work around is:
1. extract egg file
2. modify tweepy/binder.py (only add 3 lines)
3. zip'ed and replace with old file (remain old file with renamed)
I hope this treatment is not needed in near the future (we can modify this changes
by using easy_install instructions).
kimrin
2012年10月28日日曜日
2012年10月21日日曜日
blogタイトル及び将棋ソフト名称変更について
思うところあり、blogタイトルと将棋ソフトの名称を変更することにしました。
特に将棋ソフトについてはこれからも変更するかもしれません。
とりあえずblogタイトルを Mechanical Shogi Blog,
将棋ソフト名を、「メカ将棋」とさせていただきます。
これからも変わらぬご愛顧よろしくお願い致します。
（文責 kimrin）
2012年10月20日土曜日
unsupervised learning by using NLTK
そういえばNLTKのnltk.tag.hmmにunsupervised learningがあったなぁと思い、
brown corpus使って簡単なテストをしてみました。
以下ソース。すっごく時間かかるので、10センテンスのうち、1センテンスから
種のhmm taggerを作り、残り9センテンスでunsupervised learning してみました。
unsupervised learningのiterationは5回です。自分のMacで5分くらいかかりますか。
---- baum.py ----
import nltk
import re
from nltk.corpus import brown
from nltk.probability import FreqDist, ConditionalFreqDist, \
ConditionalProbDist, DictionaryProbDist, DictionaryConditionalProbDist, \
LidstoneProbDist, MutableProbDist, MLEProbDist
def cut_corpus(num_sents):
sentences = brown.tagged_sents(categories='news')[:num_sents]
return sentences
def calc_sets(sentences):
tag_re = re.compile(r'[*]|--|[^+*-]+')
tag_set = set()
symbols = set()
cleaned_sentences = []
for sentence in sentences:
for i in range(len(sentence)):
word, tag = sentence[i]
word = word.lower() # normalize
symbols.add(word) # log this word
# Clean up the tag.
tag = tag_re.match(tag).group()
tag_set.add(tag)
sentence[i] = (word, tag) # store cleaned-up tagged token
cleaned_sentences += [sentence]
return cleaned_sentences, list(tag_set), list(symbols)
from nltk.tag.hmm import HiddenMarkovModelTrainer
def baum_demo(sentences,learn_ratio,tagset,symbols):
print "Baum-Welch demo"
#print "tagset = " + str(tagset)
#print "symbols = " + str(symbols)
edge = int(len(sentences) * learn_ratio)
tagged = sentences[:edge]
untagged = sentences[edge:]
trainer = HiddenMarkovModelTrainer(tagset, symbols)
hmm = trainer.train_supervised(tagged,
estimator=lambda fd, bins: LidstoneProbDist(fd, 0.1, bins))
print "generated tagged initial tagger"
trainer2 = HiddenMarkovModelTrainer(tagset, symbols)
training = []
for i in range(len(untagged)):
item = untagged[i]
sent = []
for j in range(len(item)):
sent += [(item[j][0],None)]
training += [sent]
#print training
unsuperv = trainer.train_unsupervised(training, model=hmm,
max_iterations=5)
print '\nunsupervised:\n'
unsuperv.test(sentences[:10], verbose=False)
print '\nsupervised:\n'
trainer3 = HiddenMarkovModelTrainer(tagset, symbols)
hmm2 = trainer.train_supervised(sentences,
estimator=lambda fd, bins: LidstoneProbDist(fd, 0.1, bins))
hmm2.test(sentences[:10], verbose=False)
if __name__ == '__main__':
sentences = cut_corpus(10)
cleaned, tagset, symbols = calc_sets(sentences)
baum_demo(cleaned,0.1,tagset,symbols)
---- end of baum.py ----
結果なのですが、、、
Baum-Welch demo
generated tagged initial tagger
iteration 0 logprob -1834.03048923
iteration 1 logprob -1608.92558988
iteration 2 logprob -1544.94196931
iteration 3 logprob -1432.04010957
iteration 4 logprob -1315.68316984
unsupervised:
accuracy over 284 tokens: 35.21
supervised:
accuracy over 284 tokens: 100.00
元のデータに対してテストして、unsupervised でacc. 35%, supervised で、acc. 100%という結果になりました。
文の数を多くすると、どんどん実行時間が長引きます。
logprobがまだ小さな値なので、多分学習というところまで
いってないのだと思います。
brown corpus使って簡単なテストをしてみました。
以下ソース。すっごく時間かかるので、10センテンスのうち、1センテンスから
種のhmm taggerを作り、残り9センテンスでunsupervised learning してみました。
unsupervised learningのiterationは5回です。自分のMacで5分くらいかかりますか。
---- baum.py ----
import nltk
import re
from nltk.corpus import brown
from nltk.probability import FreqDist, ConditionalFreqDist, \
ConditionalProbDist, DictionaryProbDist, DictionaryConditionalProbDist, \
LidstoneProbDist, MutableProbDist, MLEProbDist
def cut_corpus(num_sents):
sentences = brown.tagged_sents(categories='news')[:num_sents]
return sentences
def calc_sets(sentences):
tag_re = re.compile(r'[*]|--|[^+*-]+')
tag_set = set()
symbols = set()
cleaned_sentences = []
for sentence in sentences:
for i in range(len(sentence)):
word, tag = sentence[i]
word = word.lower() # normalize
symbols.add(word) # log this word
# Clean up the tag.
tag = tag_re.match(tag).group()
tag_set.add(tag)
sentence[i] = (word, tag) # store cleaned-up tagged token
cleaned_sentences += [sentence]
return cleaned_sentences, list(tag_set), list(symbols)
from nltk.tag.hmm import HiddenMarkovModelTrainer
def baum_demo(sentences,learn_ratio,tagset,symbols):
print "Baum-Welch demo"
#print "tagset = " + str(tagset)
#print "symbols = " + str(symbols)
edge = int(len(sentences) * learn_ratio)
tagged = sentences[:edge]
untagged = sentences[edge:]
trainer = HiddenMarkovModelTrainer(tagset, symbols)
hmm = trainer.train_supervised(tagged,
estimator=lambda fd, bins: LidstoneProbDist(fd, 0.1, bins))
print "generated tagged initial tagger"
trainer2 = HiddenMarkovModelTrainer(tagset, symbols)
training = []
for i in range(len(untagged)):
item = untagged[i]
sent = []
for j in range(len(item)):
sent += [(item[j][0],None)]
training += [sent]
#print training
unsuperv = trainer.train_unsupervised(training, model=hmm,
max_iterations=5)
print '\nunsupervised:\n'
unsuperv.test(sentences[:10], verbose=False)
print '\nsupervised:\n'
trainer3 = HiddenMarkovModelTrainer(tagset, symbols)
hmm2 = trainer.train_supervised(sentences,
estimator=lambda fd, bins: LidstoneProbDist(fd, 0.1, bins))
hmm2.test(sentences[:10], verbose=False)
if __name__ == '__main__':
sentences = cut_corpus(10)
cleaned, tagset, symbols = calc_sets(sentences)
baum_demo(cleaned,0.1,tagset,symbols)
---- end of baum.py ----
結果なのですが、、、
Baum-Welch demo
generated tagged initial tagger
iteration 0 logprob -1834.03048923
iteration 1 logprob -1608.92558988
iteration 2 logprob -1544.94196931
iteration 3 logprob -1432.04010957
iteration 4 logprob -1315.68316984
unsupervised:
accuracy over 284 tokens: 35.21
supervised:
accuracy over 284 tokens: 100.00
元のデータに対してテストして、unsupervised でacc. 35%, supervised で、acc. 100%という結果になりました。
文の数を多くすると、どんどん実行時間が長引きます。
logprobがまだ小さな値なので、多分学習というところまで
いってないのだと思います。
2012年9月1日土曜日
あなたの英語が変わる「英英辞典勉強法」
英英辞典勉強法は、英英辞典を毎日読んで英語のreadingの力を付けよう、という勉強法です。
ここまで読んで「無理っす」と思われる方もいらっしゃるかもしれませんが、
もしそうだと思われるなら、このエントリーを読んで明日大きめの本屋さんで
英英辞典を確認されることをお勧めします。品揃えのよい、都市の大きな書店を
お勧めします。きっとあなたの一冊を見つけられると思います。
難しめの辞典でよければ、あなたの電子辞書にはいっている英英辞典でもいいです。
そもそも英英辞典ってなんでしょう。「英語で書かれた英語の辞書」です。
日本人から見ると「なんでそんな回りくどいことを。英和辞典でいいじゃんか」
と思われるかもしれませんが、そもそも英語圏の辞典は英英辞典です。
英和辞典はその英英辞典の発達した和訳なのです！
英英辞典には２種類あります。「ネイティブ向け（Concise Oxford Dictionaryなど）」と、「英語学習者向け（LDOCE, OALD, COBUILDなど）」です。もちろん、
初心者はネイティブ向け辞典を読んではいけません。消化不良を起こします。
大切なのは自分に合ったレベルの学習者向け英英辞典を手に入れて、
それを死蔵しないことです。英英辞典というと「英語がバリバリ出来る人が英和辞典では物足りないときに語義の繊細なニュアンスを確かめるためにたまに参照する辞典だ」
という認識があるかもしれませんが、実はかなり易しい英英辞典が日本でも流通して
います。多分高校生くらいなら十分読み始められると思います。
自分に合った英英辞典をみつけたら、毎日読みます。引くのではなく、読みます。
そのとき、次の約束を守って読み進めてみてください。
- 英和辞典のように「引かない」：普通の本のように「読み」ます
- 知らない単語を最初に引いてはいけません。まずは知っている単語を読みます
- 知ってる単語のエントリを読んだら、また興味の出て来た単語を読みます
- ここで、知らない単語に興味が出たら、そのエントリを読んでみます。そして分からなかったら英和辞典を引きます。電子辞書ならラクだと思います
- 読む単語は知っている単語なら制約はありません。好きな単語を好きなだけ読んでみましょう
- 定義（definition）と例文についての最低限の組版ルールは冒頭に書いてあるので抑えておきましょう。特に文法用語が馴染みがないと思うので、知らない単語があったら英和辞典や文法辞典で軽く確認しておきましょう
- しばらく「読んで」みると、定義より例文の方が難しいことに気がつきます。実は殆どの学習英英辞典は定義で使える単語数を2000単語くらいに制限しています。おそらくその半分の出現頻度は低いでしょうから、1000語知っていれば意味の80%くらいは理解できる計算です。まずは定義に出てくる単語を「馴染みの」単語にして行きましょう。
- しばらく読みを続けて行くとある日限界突破をして、英語が「読める！」とう感覚が生まれます。そうしたらしめたもので、どんどん読みましょう。
- 定義を和訳しようとしないようにしましょう。和訳しなくちゃわかんないと思うかもしれませんが、「訳すより感じろ」的な感じで、言葉のイメージを大切にして直感で単語のイメージと使われ方を感じてください。
大切なのは、英語で英語を定義することです。birdはanimalでflyして、featherとwingを持っていて、[C](可算名詞)でみたいな情報が英単語とリンクしたイメージとして定着します。余裕が出て来たら文法事項についての知識も一緒に獲得しましょう。動詞ならI（Intransitive）とT(Transitive)とその他という種類がありますし、名詞なら複数形でしか使わないとか、色々な決まり事があります。
長くなりましたがつまり、
「学習英英辞典の好きな単語の定義と例文をひたすら読んでみよう」
ということになります。
最後に「どれが自分に合っているか分かんない」という方向けに、英英辞典をいくつかご紹介します。このリスト見ながら選んでみてください。
- Longman Basic: 多分これ以上易しい英英辞典は無いと思います。コンパクトです
- Longman Basicはやさしすぐるし、定義が短くてつまんない、と思った方に、次の３冊を勧めます
- Oxford Word Power（オックスフォード ワードパワー英英辞典 第3版）
- Longman Active Study （ロングマンActive Study英英辞典 ５訂版）
- Cobuildの易しめ米語辞典（コウビルド中級米語辞典--学校用語付き--）
- もっと難しくても大丈夫、という方には次の売れ筋３冊をご紹介します
- OALD (オックスフォード現代英英辞典 第８版)
- LDOCE(ロングマン現代英英辞典 ５訂版)
- COBUILD(米語版) (コウビルド米語辞典)
amazonなどで検索されると同じ辞典の洋書と和書があることに気づかれると思います。
通常は和書が品質がよいですが、英語名を探して、洋書を買ってもいいです。洋書の方が
新しいものや、和書が出ていないものがあります。
最後に、大事なことは、勉強しないこと、です。自分の興味の赴くままに、辞典を自由闊達に読み耽りましょう。ちなみに僕は一番最初の英英辞典は「ケンブリッジ米語辞典（現在は洋書の２版が流通しています）」でした。僕はこの学習英英辞典にとても感謝していて、とてもお気に入りの一冊です。この勉強法は英語をたくさん読むので、TOEICのReading向上にも効果的です。以上。（文責 kimrin）
2012年7月28日土曜日
はじめてのコンピュータ将棋入門(3)
前回、kouryo()関数は実はサボれる、という話をしました。
これは、同じ結果を得られるけれど、新しいやり方はより少ない時間で
回答を見つけられる、という意味でお話しました。
今回は、ほぼすべての将棋ゲームプログラムの基礎となっている、アルファベータ法
という探索アルゴリズムを紹介いたします。
まずはC言語で書かれたkouryo()関数と、AlphaBeta()関数を見てもらいましょう。
int kouryo(int *te, int fukasa)
{
int te2;
int teban = 1; // 先手がCOMPUTER, -1なら後手がCOMPUTER
int val = AlphaBeta(&te2, -10000, 10000, fukasa, teban);
*te = te2;
return val;
}
int AlphaBeta(int *te, int alpha, int beta, int depth, int teban)
{
int kazu;
int hairetsu[1024];
kazu = kanoushu(hairetsu, teban); // hairetsu[0] から hairetsu[kazu-1]に手が入る
if (depth <= 0) { return hyouka(teban);}
int i;
int ret = 0;
for ( i = 0 ; i < kazu ; i++) {
int te, te2;
te = hairetsu[i];
sasu(te);
int a = - AlphaBeta( &te2, -beta, -alpha, depth - 1, (-1)*teban);
modosu(te);
if ( a > alpha) { // alpha update
alpha = a;
ret = te;
}
if ( ban >= beta ) { // beta cut
*te = ret;
return ban;
}
}
*te = ret;
return ban;
}
まずkouryo()関数に探索深さがわたると、その中でAlphaBeta関数を呼び出します。
このとき重要なのがalphaとbetaと呼ばれる二つのパラメータです。
AlphaBeta関数には面白い性質があります。探索の答えの値（評価値）が、
alpha以上beta以下だと、AlphaBeta関数はその答えの値を返します。
もしalphaからbetaの範囲内に答えが無かったら、alphaかbeta（大小による）
を返します。この、alphaからbetaの範囲のことをウィンドウと言いますが、
もしある程度の誤差でAlphaBeta関数の答えをあらかじめ知っていれば、
ウィンドウを狭めて検索することで早く答えを出す事ができます。
AlphaBeta()関数の内部を見て行きましょう。
この前のkouryo()関数と似ていますがいくつか異なる点があります。
まずfukasaをdepthという値に置き換えて、探索が深くなるとdepthが
小さくなるようにしています。hyouka()を返す条件をdepthが0以下と
しました。またhyouka()は手番をとるように変更しました。
また、手番を追加しました。1を先手、-1を後手とします。
同じAlphaBeta関数を中で呼んでいる（これを再帰といいます）
あと、二つの条件文のところにコメントで、
alpha update, beta cutと書いてあります。この二つがとても
重要です。
厳密にはこのアルゴリズムはアルファベータ法ではなく、
ネガマックス法という、より簡略化した手法ですが、同じ正解を
得られます。
ではalpha updateとbeta cutの説明をしましょう。
alpha updateとは、「答えかもしれない良い手に出会いました」
という意味で、alpha updateのときは手と評価値を保存します。
またalphaパラメータを更新して、より大きい値に変更します。
つまりウィンドウを狭める訳です。
beta cutは正確にはbeta cut-offと言います。
これが実はサボりのために必要な部分です。
評価値がbetaを超えた場合、その手はとても良い手なので、
その手で探索を打ち切ります。それより後ろの可能手を
AlphaBeta()関数で調べなくても、最終的な正解は変わらない
という性質を利用しています。
結果、極端な場合には始めの一手でbeta cutが起こると、
その手しか調べません。これが効率がよい秘密です。
このAlphaBeta関数には入っていませんが、可能手を、beta cut-off
しやすい順にならべれば、探索する探索木はより深くまで読める
ような理想型になります。このソート（並べ替え）のことを
ムーブオーダリングと呼び、強い将棋ソフトには必須の機能です。
またこの探索木の理想型のことをoptimal treeと呼んでいます。
Knuth先生という方の論文に、このoptimal treeになったときに
どのくらい局面を探索するか、という値が計算されています。
詳しくはその論文に譲りますが、まじめに全部調べるよりずっと
少ない数になります。
ではねちゃお！
2012年7月22日日曜日
はじめてのコンピュータ将棋入門(2)
今回は将棋の思考ルーチンについてお話したいと思います。
前のブログエントリーで、kouryo()関数になっていたところです。
なぜコンピュータは計算しかできないのにあんなに強い将棋を指せるのか、
という問いに対する簡単な答えを提供できたらな、と思います。
まず思考ルーチンには二つの関数が必要です。
一つは与えられた盤面に対して先手、あるいは後手が動かすことのできる全ての手（可能手といいます）を列挙する関数です。ここではkanoshu()関数という名前とします。
もう一つは与えられた盤面がどの程度先手にとっていいかを数値化してくれる関数（評価関数といいます）です。hyouka()関数という名前だとします。
本当は評価関数としてhabu()みたいな、羽生先生が見て点数を付けたような評価関数が
欲しいところですがw いまのところ無理なので、「ある程度」確からしい評価関数を使う
ことにします。
実は、コンピュータのすごいところは、この評価関数がそれほど正確でなくても何手も
深く読んで強い一手を指せるところにあります。
思考ルーチンの関数kouryo()は、おおむね次のような処理をします。
ここで、kouryo()は、選んだ手（整数）と、その評価値（整数）を返すことに変更します。C言語で書くと書きづらいですが、こんな感じです。
int te;
int hyouka = kouryo(&te, 0);
こうすると、teには選んだ手の整数が、hyoukaには評価値が入ります。
では処理を見て行きましょう！
- 自分が先手なら盤面で先手の指せる手、後手なら後手の指せる手を、まずは全部列挙します。初手で30手くらいでしたでしょうか
- 全ての手の評価値を求めます。これはすべての手について、盤面を一手進めた盤面を作って、kouryo()を計算します。で、評価値はkouryo()の値をマイナス符号を付けた値（-1を掛けた値）になります
- 全ての手の評価値の中で、一番大きい値を持つ手を選んでteとして返します。この手の評価値も一緒に返してあげます
鋭い人は「kouryoがkouryoを呼んで、またkouryoを呼んで、、、終わらなくない？」という問いかけをすると思います。確かに今の仕様ではそうなってしまいます。
それを避けるために、呼び出す深さがN（決められた数値、例えば3とか）になったら、kouryo()の代わりに、hyouka()という、暫定の評価値を返す関数を呼ぶ事にします。
これが最初二つ用意した関数のうちの２番目の評価関数というものです。
C言語で書いてみましょう。
int kouryo(int *te, int fukasa)
{
int kazu;
int hairetsu[1024];
kazu = kanoushu(hairetsu); // hairetsu[0] から hairetsu[kazu-1]に手が入る
if (fukasa > 3) { return hyouka();}
int i;
int ban = -1000000; // とても小さい数
int ret = 0;
for ( i = 0 ; i < kazu ; i++) {
int te, te2;
te = hairetsu[i];
sasu(te);
int a = - kouryo( &te2, fukasa + 1);
if ( a > ban) { // 暫定の最大値とその手を計算する
ban = a;
ret = te;
}
modosu(te);
}
*te = ret;
return ban;
}
hairetsuとは、箱が横にいっぱいならんでいて、hairetsu[10]とすると10個目の箱の値を取り出せる仕組みです。
for文は、ここでは0からkazu-1まで、iを増やしながら {}を繰り返す、の意味です。
*teという記述があります。これはポインタというのですが、外から場所をもらい、
その場所に数字を書くという意味になります。結果として、kouryoの第一引数の指定
された変数（＆が付いている）に、最善の手が入ります。
sasuは前に出てきました。一手進める手です。modosuはその反対の動作をする関数です。つまり一手もとに戻します。
実際にはkouryoはもっとたくさんの引数を必要とします。先手か、後手かなどです。
そして重要なことですが、この関数はかなり遅いです。実は処理をさぼっても同じ結果を得られる方法があります。これについては後日お話します。
まずは計算だけで将棋が指せることを実感してみてください！
ではねちゃお！
2012年7月21日土曜日
はじめてのコンピュータ将棋入門(1)
今回から数回に分けて、コンピュータ将棋プログラムを作りたい人向けに簡単な文章を提供したいと思います。メカウーサー将棋は弱いので、これを読んで強い将棋プログラムを作って下さる方が現れるとうれしいなと思っています。長文すみません。
※分かりやすく書いたら長文で分かりにくくなりました。。。(T_T)
１回目はまず、将棋プログラムとはなんぞや、というところから始めたいと思います。プログラミングの知識のある人にとっては「いらね」という説明が続きますが、そのときはスキップしちゃってください。よろしくお願いします。
まずプログラムとはなんぞやというところから話を始めたいと思います（えーw）
プログラムとはなんぞや、という問いに答えられる人は「※普通はここから読んでください」から読み始めてください。
まず、プログラムは通常機械語と呼ばれる数字の集まりからなるデータの塊です。
で、これを人間がしこしこ書くのは辛いし効率が悪いので、あたまの切れる人が、
「人間に馴染みのある人工言語をつくって、そっから一気に機械語に直すプログラム
を作れば楽勝じゃん？」ということをひらめいて、実際そういうものをつくりました。
この、「人工言語→機械語」の変換プログラムはコンパイラと呼ばれ、あたまのいい
人が作るすごいプログラムの一種です。で、私たちはそれを作らないと変換できない
のではなく、もう出来上がったコンパイラを場合によってはタダで使えます。
素晴らしい世の中です。
多くのエンジニアによってたくさんの人工言語（プログラミング言語といいます）が
発明されてきました。今回はその中でも長い間よく使われて来たC言語という言語
を使って説明していきたいと思います。
※普通はここから読んでください
で、ここでやっと将棋プログラムとはなんぞやという説明に入ります。
将棋には先手と後手があり、その内のどちらかをコンピュータが指すとします。
先手番の場合、第１手を「考えて」指し、後手の手を待って後手が指したら
その手を受け取って、第３手を指し、以下どちらかが投了するまで同じことを
続けます（将棋に詳しい人は話をはしおりすぎると思うかもしれませんが、
まずは千日手や入玉のことは忘れてくださいませ）。
そこで、この手順をC言語（っぽい）プログラミング言語で書いてみたいと思います（図１）。
C言語が分かる人は図１を直接見て察してください。分からない人のために説明を以下に書きました。//はコメントと言って、//のあとの文字は無かった事にするという意味を持ちます。
まず、intは32bitの符号付き整数で、、、つまりプラスとかマイナスになる数ですね。
簡単のため、数を色んな場所で使っていますが、それぞれに約束ごとがあります。
int game(int teban) {...} というのを関数といい、実行する内容をまとめて一つにしたもの
です。最初のintは数字が返ってくることを表し、(int teban)は数字を引数に与える
ことを指します。引数は関数専用の入力だと（ここでは）思ってください。
つまり関数gameは将棋対戦をして自分が負けたら0を、勝ったら1を返す関数です。
{}で囲まれた中が関数の中身です。ここに何をしたいかを書きます。
引数のtebanはintの変数といいます。つまり数字を入れる箱です。
自分が先手の時には0が、後手の時は1が入ります。
関数の一番最初にifというキーワードがあります。これはC言語で決まっている
キーワードと言って、特殊な単語です。この単語は変数の名前には使えません。
ifキーワードはelseキーワードと一緒に使い、「CだったらAを、さもなければBを」
という風に条件により異なる内容を実行します。
if (C) { A} else {B}
という形をしていて、Cを条件式と呼び、Aをthenパート、Bをelseパートと呼びます。
ここで、{}の本当の働きを説明します。{}は、一つ以上の文をまとめたものです。
一つの文は「文;」(;はセミコロンと云います)と書きます。これを続けて書くと
{ 文１;文２; } のようになります。つまり文の最後にはセミコロンが入ります。
プログラムは文を使って構成します。詳しくは後々の例を見て行きましょう。
先手番、後手番、両方ともやる事が似ています。
特に、先手番後手番ともに内容がwhileキーワードによって囲まれています。
while(C) { 文; ...} は、Cだったら {}内を実行し続けます。
ここではCに1（条件一致）を与えているので、常に実行を続け、この文は
永遠に返ってきません！ でもそれでは困るので、脱出する手段をこの{}
内に書きます。これについては後述します。
つまり先手も後手も一定の処理を条件が整うまで繰り返します。
その条件とは「投了」です。
処理の内容を先手番で見てみましょう。
まず、int te = kouryo(); という記述があります。これは関数呼び出し
と言います。つまり関数を実行します。
鋭いひとはkouryo()関数の中身がここでは書かれていないことに気がつく
でしょう。実はそれこそが私たちの欲しい思考ルーチンなのです。
思考ルーチンの説明は後日します。今日は将棋プログラムがどんなものなのか
まずは感覚で感じてください。
ここでも一つ約束をします。teは先手の手で、0が手がない、それ以外が
何らかの手です。つまり全ての可能な将棋の手に番号を付けておいて、その
番号をこのkouryo()関数が返します。
次のif は {} も elseもありませんが、立派な条件分岐です。
teが0だったら、return 0 を実行します。
条件式の中で同じということを判断するには=ではなく==を使うことに
注意してください。
return 0;というものが現れました。これは0をgame()関数の返すものとして、
game()関数を終了する、という意味になります。0は投了だったので、
この場合はもう先手に指せる手が無くて、投了した、ということになります。
ここで、teに入っているのは可能な手であり、関数gameの値として返すのは
勝敗であることに注意してください。本来は型というものを作って区別するの
ですが、まずは簡単のためすべて数で表現しています。
次のsasu(te)は、コンピュータが持っている盤面で、先手の手を進めます。
詳細は略ですが、盤面の表し方には色々あるので、その方法次第で何を
するかが決まります。
printf("%d¥n", te); はプリント文と云って、何かをスクリーンに出力する
関数です。これはコンパイラと一緒にすでに用意されています。
暗号みたいな記号が書かれていますが、いまはteの数字をスクリーンに
出す、と覚えてください。
次にaite=gote();とあります。これは後手が手の数字を入力して、その内容を
aiteに入れる事を指します。詳細は略ですが、コンピュータ将棋選手権などでは、
通信して相手の手をもらいます。
これで相手の手がわかりました。もし相手が投了ならreturn 1をして自分が勝ちで終了です。
コンピュータ将棋プログラムは相手が指すときは何もしないと思うかもしれませんが、
一つだけ仕事があって、それは自分の盤面で相手の手を一手動かすことです。
sasu(aite)が相手の手を指して一つ進めます。
さて、これを先手、後手どちらかが投了するまでつづける、というのがコンピュータが
先手番の場合でした。
後手の説明は簡単にしてしまうと、相手の手を待って投了か判断した後に
相手の手を指し、次に自分の手を考えて投了か判断した後に自分の手を
一手進めます。コンピュータが後手番の場合はこれを投了まで繰り返します。
int game(int teban)
{
if (teban == 0) { // 先手
while (1) { // 無限繰り返し
int te = kouryo(); // 先手の手を「考える」
if (te == 0) return 0; // 先手投了
sasu(te); // 自分の心の中の盤面で先手の手を指す
printf("%d¥n", te); // 先手の手を相手に知らせる
int aite = gote(); // 後手の手を受け取る
if (aite == 0) return 1; // 後手投了
sasu(aite); // 自分の心の中の盤面で後手の手を指す
} // while
} else {
while (1) { // 無限繰り返し
int aite = sente(); // 先手の手を受け取る
if (aite == 0) return 1; // 先手投了
sasu(aite); // 自分の心の中の盤面で先手の手を指す
int te = kouryo(); // 後手の手を「考える」
if (te == 0) return 0; // 後手投了
sasu(te); // 自分の心の中の盤面で後手の手を指す
printf("%d¥n", te); // 後手の手を相手に知らせる
} // while
}
}
ここで中身を書いていないすべての関数に中身を与える必要があります（printf除く）。
特にkouryo()が難しくて、これのことを思考ルーチンと呼びます。
最後に、game()を誰が呼んでいる、という疑問があると思います。mainが呼びます。
int teban = 0; // コンピュータ先手番
int main(int ac, char *av[])
{
return game(teban);
}
だめだー、自分文才なさすぎ。すみません。。。
※分かりやすく書いたら長文で分かりにくくなりました。。。(T_T)
１回目はまず、将棋プログラムとはなんぞや、というところから始めたいと思います。プログラミングの知識のある人にとっては「いらね」という説明が続きますが、そのときはスキップしちゃってください。よろしくお願いします。
まずプログラムとはなんぞやというところから話を始めたいと思います（えーw）
プログラムとはなんぞや、という問いに答えられる人は「※普通はここから読んでください」から読み始めてください。
まず、プログラムは通常機械語と呼ばれる数字の集まりからなるデータの塊です。
で、これを人間がしこしこ書くのは辛いし効率が悪いので、あたまの切れる人が、
「人間に馴染みのある人工言語をつくって、そっから一気に機械語に直すプログラム
を作れば楽勝じゃん？」ということをひらめいて、実際そういうものをつくりました。
この、「人工言語→機械語」の変換プログラムはコンパイラと呼ばれ、あたまのいい
人が作るすごいプログラムの一種です。で、私たちはそれを作らないと変換できない
のではなく、もう出来上がったコンパイラを場合によってはタダで使えます。
素晴らしい世の中です。
多くのエンジニアによってたくさんの人工言語（プログラミング言語といいます）が
発明されてきました。今回はその中でも長い間よく使われて来たC言語という言語
を使って説明していきたいと思います。
※普通はここから読んでください
で、ここでやっと将棋プログラムとはなんぞやという説明に入ります。
将棋には先手と後手があり、その内のどちらかをコンピュータが指すとします。
先手番の場合、第１手を「考えて」指し、後手の手を待って後手が指したら
その手を受け取って、第３手を指し、以下どちらかが投了するまで同じことを
続けます（将棋に詳しい人は話をはしおりすぎると思うかもしれませんが、
まずは千日手や入玉のことは忘れてくださいませ）。
そこで、この手順をC言語（っぽい）プログラミング言語で書いてみたいと思います（図１）。
C言語が分かる人は図１を直接見て察してください。分からない人のために説明を以下に書きました。//はコメントと言って、//のあとの文字は無かった事にするという意味を持ちます。
まず、intは32bitの符号付き整数で、、、つまりプラスとかマイナスになる数ですね。
簡単のため、数を色んな場所で使っていますが、それぞれに約束ごとがあります。
int game(int teban) {...} というのを関数といい、実行する内容をまとめて一つにしたもの
です。最初のintは数字が返ってくることを表し、(int teban)は数字を引数に与える
ことを指します。引数は関数専用の入力だと（ここでは）思ってください。
つまり関数gameは将棋対戦をして自分が負けたら0を、勝ったら1を返す関数です。
{}で囲まれた中が関数の中身です。ここに何をしたいかを書きます。
引数のtebanはintの変数といいます。つまり数字を入れる箱です。
自分が先手の時には0が、後手の時は1が入ります。
関数の一番最初にifというキーワードがあります。これはC言語で決まっている
キーワードと言って、特殊な単語です。この単語は変数の名前には使えません。
ifキーワードはelseキーワードと一緒に使い、「CだったらAを、さもなければBを」
という風に条件により異なる内容を実行します。
if (C) { A} else {B}
という形をしていて、Cを条件式と呼び、Aをthenパート、Bをelseパートと呼びます。
ここで、{}の本当の働きを説明します。{}は、一つ以上の文をまとめたものです。
一つの文は「文;」(;はセミコロンと云います)と書きます。これを続けて書くと
{ 文１;文２; } のようになります。つまり文の最後にはセミコロンが入ります。
プログラムは文を使って構成します。詳しくは後々の例を見て行きましょう。
先手番、後手番、両方ともやる事が似ています。
特に、先手番後手番ともに内容がwhileキーワードによって囲まれています。
while(C) { 文; ...} は、Cだったら {}内を実行し続けます。
ここではCに1（条件一致）を与えているので、常に実行を続け、この文は
永遠に返ってきません！ でもそれでは困るので、脱出する手段をこの{}
内に書きます。これについては後述します。
つまり先手も後手も一定の処理を条件が整うまで繰り返します。
その条件とは「投了」です。
処理の内容を先手番で見てみましょう。
まず、int te = kouryo(); という記述があります。これは関数呼び出し
と言います。つまり関数を実行します。
鋭いひとはkouryo()関数の中身がここでは書かれていないことに気がつく
でしょう。実はそれこそが私たちの欲しい思考ルーチンなのです。
思考ルーチンの説明は後日します。今日は将棋プログラムがどんなものなのか
まずは感覚で感じてください。
ここでも一つ約束をします。teは先手の手で、0が手がない、それ以外が
何らかの手です。つまり全ての可能な将棋の手に番号を付けておいて、その
番号をこのkouryo()関数が返します。
次のif は {} も elseもありませんが、立派な条件分岐です。
teが0だったら、return 0 を実行します。
条件式の中で同じということを判断するには=ではなく==を使うことに
注意してください。
return 0;というものが現れました。これは0をgame()関数の返すものとして、
game()関数を終了する、という意味になります。0は投了だったので、
この場合はもう先手に指せる手が無くて、投了した、ということになります。
ここで、teに入っているのは可能な手であり、関数gameの値として返すのは
勝敗であることに注意してください。本来は型というものを作って区別するの
ですが、まずは簡単のためすべて数で表現しています。
次のsasu(te)は、コンピュータが持っている盤面で、先手の手を進めます。
詳細は略ですが、盤面の表し方には色々あるので、その方法次第で何を
するかが決まります。
printf("%d¥n", te); はプリント文と云って、何かをスクリーンに出力する
関数です。これはコンパイラと一緒にすでに用意されています。
暗号みたいな記号が書かれていますが、いまはteの数字をスクリーンに
出す、と覚えてください。
次にaite=gote();とあります。これは後手が手の数字を入力して、その内容を
aiteに入れる事を指します。詳細は略ですが、コンピュータ将棋選手権などでは、
通信して相手の手をもらいます。
これで相手の手がわかりました。もし相手が投了ならreturn 1をして自分が勝ちで終了です。
コンピュータ将棋プログラムは相手が指すときは何もしないと思うかもしれませんが、
一つだけ仕事があって、それは自分の盤面で相手の手を一手動かすことです。
sasu(aite)が相手の手を指して一つ進めます。
さて、これを先手、後手どちらかが投了するまでつづける、というのがコンピュータが
先手番の場合でした。
後手の説明は簡単にしてしまうと、相手の手を待って投了か判断した後に
相手の手を指し、次に自分の手を考えて投了か判断した後に自分の手を
一手進めます。コンピュータが後手番の場合はこれを投了まで繰り返します。
int game(int teban)
{
if (teban == 0) { // 先手
while (1) { // 無限繰り返し
int te = kouryo(); // 先手の手を「考える」
if (te == 0) return 0; // 先手投了
sasu(te); // 自分の心の中の盤面で先手の手を指す
printf("%d¥n", te); // 先手の手を相手に知らせる
int aite = gote(); // 後手の手を受け取る
if (aite == 0) return 1; // 後手投了
sasu(aite); // 自分の心の中の盤面で後手の手を指す
} // while
} else {
while (1) { // 無限繰り返し
int aite = sente(); // 先手の手を受け取る
if (aite == 0) return 1; // 先手投了
sasu(aite); // 自分の心の中の盤面で先手の手を指す
int te = kouryo(); // 後手の手を「考える」
if (te == 0) return 0; // 後手投了
sasu(te); // 自分の心の中の盤面で後手の手を指す
printf("%d¥n", te); // 後手の手を相手に知らせる
} // while
}
}
ここで中身を書いていないすべての関数に中身を与える必要があります（printf除く）。
特にkouryo()が難しくて、これのことを思考ルーチンと呼びます。
最後に、game()を誰が呼んでいる、という疑問があると思います。mainが呼びます。
int teban = 0; // コンピュータ先手番
int main(int ac, char *av[])
{
return game(teban);
}
だめだー、自分文才なさすぎ。すみません。。。
2012年5月4日金曜日
メカウーサー将棋の歴史と変遷
(注：この記事は名称変更前の記事となります。史事の記述であるため、メカウーサー及びメカウーサー将棋の記述は、メカ将棋と改めず、そのままと致しました。 kimrin)
巷ではコンピュータ将棋選手権の決勝が明日行われますが、メカウーサー将棋的には今年は既に終わっているので（ぉぃ いままでexplicitに書いていなかったメカウーサー将棋の変遷について簡単に触れたいと思います。
巷ではコンピュータ将棋選手権の決勝が明日行われますが、メカウーサー将棋的には今年は既に終わっているので（ぉぃ いままでexplicitに書いていなかったメカウーサー将棋の変遷について簡単に触れたいと思います。
まず、2009年の12月頃からコンピュータ将棋ソフトの作成に取りかかりました。
最初は右も左も分からず、GPGPUで作れば相当のソフトが出来るのではと安直に
考えていました。いま考えてもかなり甘い誤算でした。
2010年5月に出場した「メカウーサー」（メカウーサー将棋の前身）は、100% GPGPU
実装でした。これは当時とても新しかったと思います。強さは皆様ご存知の通りの弱さでしたが。。。
GPGPUのメカウーサーは、最初の２手を２次元格子状に展開します。これだけで後半だと数万コアに異なる局面が行き渡ります。そして、その各々でalpha-beta探索を行いました。
だいたい２手〜３手程度がalpha-betaで探索出来ました。つまり５手程度の探索が可能でした。
GPGPUメカウーサーの問題は、時間配分が拙かった点が一つ、強い将棋ソフトを全く参考に
していない我流のソフトだった点が二つ目、ということで問題山積なのでした。
特に初手からの数手は５手読みをほぼno timeで行っており、早いのですが、あと１手多く読めたのではないかと思います。またmove orderingについてもかなりpoorで、minimal treeにはほど遠い状態だったと思います。
こうして史上初のGPGPU将棋ソフト「メカウーサー」は対無明戦において、伝説の「棒玉」
を指して皆様に失笑されるのでした（しょぼ〜ん）
2010年のアピール文書はこちらです。
2011年に出場した「メカウーサー将棋」は100%CPUのソフトでした。
「GPUで強いソフトを作るにはまずCPUである程度強いソフトが作れないとダメだよね」
という信念のもとCPUのソフトを開発したのですが、これもいかんせん我流なソフトで
弱さと云う名の強さwを兼ね備えたソフトとなりました。
結果としてGPUソフトはその後の2012年でも投入することができませんでした。
2011年のソフトにはいくつかバグがありました。特に定跡ルーチンにバグがあり、
折角定跡を入れたのに特定の条件（定跡上で成る）でソフトが落ちるバグがありました。
これを対Tofu戦で見事に踏んでしまい、あえなく一敗してしまうのでした。
また対さわにゃんRL戦では「これは将棋というゲームではない」と言われるような
お恥ずかしいゲームとなってしまい、作者の方と「あれはひどかったね」と振り返る
のでした。
2011年のアピール文書はこちらです。
2012年のソフトもまたCPUソフトなのですが、実はGPGPUのソフトの初期検討を12月頃から行っていました。これは原稿としてプロシンにも載りました。
最初は簡単なゲームから、ということでHexと呼ばれるゲームの実装から開始したの
ですが、Hexのシーケンシャル版は出来たものの、並列版作成で詰まってしまいました。
いわゆるスランプです。
そのため将棋ソフトも並列版を作るまでに至らず、最終的に去年のソースを引っぱり出して来て、それのUIを新しい枠組みに乗り換えて出場することになりました。
去年のメカウーサー将棋との違いは詰みが少し強くなったことと、定跡のバグが消えていることが違います。
また今年はオペレータを女性に行っていただきました。少しだけ見苦しくなかったのでは
ないかと思いますw
2012年のアピール文書には、GPGPU実装の初期検討資料も含まれています。
アピール文書はこちらになります。
仕事の関係上2012--2013年は将棋ソフトにあまり時間を掛けず、仕事に集中する予定
です。GPGPU実装のメカウーサー将棋を生暖かい目で末永くお待ちいただけると幸いです。
ではねちゃお。
2012年4月29日日曜日
Mechawooser shogi and his UI interface
At first thing, I'll attend WCSC22(The 22nd World Computer Shogi Contest) with NON-GPGPU program. It's not the part of this blog entry, but very, very important thing, so I've mentioned it before starting the today's blog entry.
* * * * * *
Today, I'd like to talk about UI interface of Mechawooser Shogi (Japanese Chess Playing Program) and their unique technologies that be used in this program.
Mechawooser shogi's UI is formed by Titanium Desktop technologies.
Especially for using Python language to communicate UI view and the "Think":
Alpha-beta based AI components.
Titanium Desktop is a kind of pretty little (but sufficient) webkit browser,
and users can be built their UI based program within program's index.html (with Javascript features such as JQuery). In Mechawooser Shogi, most important choice
of programming language that be used within the Titanium Desktop is Python language!
Titanium Desktop environment can be used various programming language at a
same time within unique index.html (and imported program fragments also downloaded simultaneously).
Let's take watching inside structure of Mechawooser Shogi.
1. Communication routines for shogi server (like chess server) was already written by Python by using socket modules.
2. Write the Shogi board to index.html by using table environment, and manipulate
Shogi pieces by JQuery.
3. Communication routines wait for message from shogi server and throw the queue entry to the queue that is always polling in timer thread(interval = 100ms).
4. polling timer thread recognize the aim of queue entry and redraw the shogi board by using JQuery Commands.
5. Communication routines also invoke Think() function within the shared library.
In order to invoke Think() functions, we use ctypes module of Python language.
the ctypes library can invoke C-linkage functions within the Python Environment.
When Think() is returned the result (=the next move), Communication routines tell the next move to shogi server, and shogi server return the emission time, then queue entry of rewriting the shogi board is en-queued, and finally UI appearance is changed.
The start button of the Shogi Game in the index.html is connecting to Javascript handler. But actually these handler is defined in the Python Program fragments.
* * * * * *
Today, I'd like to talk about UI interface of Mechawooser Shogi (Japanese Chess Playing Program) and their unique technologies that be used in this program.
Mechawooser shogi's UI is formed by Titanium Desktop technologies.
Especially for using Python language to communicate UI view and the "Think":
Alpha-beta based AI components.
Titanium Desktop is a kind of pretty little (but sufficient) webkit browser,
and users can be built their UI based program within program's index.html (with Javascript features such as JQuery). In Mechawooser Shogi, most important choice
of programming language that be used within the Titanium Desktop is Python language!
Titanium Desktop environment can be used various programming language at a
same time within unique index.html (and imported program fragments also downloaded simultaneously).
Let's take watching inside structure of Mechawooser Shogi.
1. Communication routines for shogi server (like chess server) was already written by Python by using socket modules.
2. Write the Shogi board to index.html by using table environment, and manipulate
Shogi pieces by JQuery.
3. Communication routines wait for message from shogi server and throw the queue entry to the queue that is always polling in timer thread(interval = 100ms).
4. polling timer thread recognize the aim of queue entry and redraw the shogi board by using JQuery Commands.
5. Communication routines also invoke Think() function within the shared library.
In order to invoke Think() functions, we use ctypes module of Python language.
the ctypes library can invoke C-linkage functions within the Python Environment.
When Think() is returned the result (=the next move), Communication routines tell the next move to shogi server, and shogi server return the emission time, then queue entry of rewriting the shogi board is en-queued, and finally UI appearance is changed.
The start button of the Shogi Game in the index.html is connecting to Javascript handler. But actually these handler is defined in the Python Program fragments.
2012年4月6日金曜日
アピール文書提出しました
今年もアピール文書を提出しました。
今年は少し控えめに作りました。最後に新しい検索手法の素案がありますので、
興味のある方はどうぞ！
http://www.computer-shogi.org/wcsc22/appeal/mechawooser_shogi/MechawooserWCSC22.pdf
- GPGPU実装ではなくCPU実装
- 去年の実装を少し変えた実装で参加予定
- 引き続きGPGPU実装は研究中です
今年は少し控えめに作りました。最後に新しい検索手法の素案がありますので、
興味のある方はどうぞ！
http://www.computer-shogi.org/wcsc22/appeal/mechawooser_shogi/MechawooserWCSC22.pdf
2012年2月23日木曜日
メカウーサー（twitter bot）誕生秘話(2)
だいぶ間が空いてしまいましたが、メカウーサー誕生秘話その２です。
今回は特にメカウーサーの実装についてお話したいと思います。
メカウーサーのエンジンはいわゆる「マルコフ遷移」を使ったタイプのエンジンです。
他にも保存している発言の名詞、動詞などを入れ替える方式がありますが、あえてメカウーサーではマルコフ遷移のエンジンにこだわっています。
初めてマルコフ遷移という言葉を聞いた方に、簡単にその原理を説明します。
ある単語「例：メカウーサー」とその次の単語「例：は」（助詞とします）の間には、共に共起しやすい（一緒に出やすい）２単語もあれば、逆に一緒には出にくい２単語の場合もあります。
そこでメカウーサーコーパス（うーさーさんが用意してくださった、1MBに及ぶ言語資料）から、すべての単語について、その次に出やすい単語の集合を求めます。このとき１回でも一緒に出現した２単語の間には「接続可能性」があるとして、これをPythonのハッシュ内に納めておきます。
{ u'メカウーサー': {u'は', u'の', u'には', ...}}
そして、前件（前の単語）でハッシュを引くと、次にくる単語の集合が得られるようにしておきます。
文章生成のときは、まず、文頭の単語の全集合から任意の単語を抽出し、その単語でハッシュを引いて、次の単語候補を選びます。
次の単語候補の集合が得られたら、その中からランダムに次の単語を選びます。
これを、「。」が来るまで繰り返します。これが初期のメカウーサーのエンジンの仕様です。
実際には一番出やすい単語をスコアを付けて保存するのですが、メカウーサーの初期のバージョンではあえて、接続するもの全てを許して、やや口語っぽい表現も出やすくしていました。また、最近のバージョンではPythonのdictをcPickleしたものを文章生成時に取り出していましたが、昔はBerkeley DBへのバインディングを使ってKey-Value pairのデータベースファイルにアクセスしていました。
実際のメカウーサーでは前件を２単語、後件を１単語からなる「単語トライグラム（trigram）」を使って文章生成を行っていました。また、文長の制御や句読点の密度を調整する関数を使って、丁度よいあんばいになるように、文章の加工を行って出力していました。
ここまでがVer.3.14と呼ばれているバージョンの主な実装になります。
コーパスの文章を単語に分割するのはMeCabと呼ばれる処理系を使いました。実装はPythonで行いました。最終的に python twitterと呼ばれるライブラリでtwitterにポストしていました。
CS4では係り受けの結果を利用しました。具体的には前件、後件に単語ではなく文節をあてて、文章生成を行いました。結果3.14のときよりもさらに日本語らしい文章の生成に成功しました。
より日本語らしい文章になったというコメントをいただいたCS5は、実は単語分割した表層（文字面）しか使っていません。しかしあれだけの精度の高い文章が生成可能です。実はとあるライブラリを使って文章生成を行っています。これはいまのところ、秘密です☆
共起のしやすさも考慮しています。
なお現在ではtwitterへのポストをtweepyと呼ばれるOAuth投稿可能なライブラリに変更しています。
実際の運用はMac Miniで行っています。少し古いですが、Hudsonで投稿の成功／失敗を管理しています。現在４つのタスクがHudsonには登録されていて、その内二つはkimrin専用の「寝坊したらBossにメールするw」アプリが、また残り二つのうち一つがメカウーサーで、もう一つは秘密のメカウーサー試験用アカウントへの投稿を行っています。
以上こんな感じになります。ではちゃお〜（文責：kimrin）
今回は特にメカウーサーの実装についてお話したいと思います。
メカウーサーのエンジンはいわゆる「マルコフ遷移」を使ったタイプのエンジンです。
他にも保存している発言の名詞、動詞などを入れ替える方式がありますが、あえてメカウーサーではマルコフ遷移のエンジンにこだわっています。
初めてマルコフ遷移という言葉を聞いた方に、簡単にその原理を説明します。
ある単語「例：メカウーサー」とその次の単語「例：は」（助詞とします）の間には、共に共起しやすい（一緒に出やすい）２単語もあれば、逆に一緒には出にくい２単語の場合もあります。
そこでメカウーサーコーパス（うーさーさんが用意してくださった、1MBに及ぶ言語資料）から、すべての単語について、その次に出やすい単語の集合を求めます。このとき１回でも一緒に出現した２単語の間には「接続可能性」があるとして、これをPythonのハッシュ内に納めておきます。
{ u'メカウーサー': {u'は', u'の', u'には', ...}}
そして、前件（前の単語）でハッシュを引くと、次にくる単語の集合が得られるようにしておきます。
文章生成のときは、まず、文頭の単語の全集合から任意の単語を抽出し、その単語でハッシュを引いて、次の単語候補を選びます。
次の単語候補の集合が得られたら、その中からランダムに次の単語を選びます。
これを、「。」が来るまで繰り返します。これが初期のメカウーサーのエンジンの仕様です。
実際には一番出やすい単語をスコアを付けて保存するのですが、メカウーサーの初期のバージョンではあえて、接続するもの全てを許して、やや口語っぽい表現も出やすくしていました。また、最近のバージョンではPythonのdictをcPickleしたものを文章生成時に取り出していましたが、昔はBerkeley DBへのバインディングを使ってKey-Value pairのデータベースファイルにアクセスしていました。
実際のメカウーサーでは前件を２単語、後件を１単語からなる「単語トライグラム（trigram）」を使って文章生成を行っていました。また、文長の制御や句読点の密度を調整する関数を使って、丁度よいあんばいになるように、文章の加工を行って出力していました。
ここまでがVer.3.14と呼ばれているバージョンの主な実装になります。
コーパスの文章を単語に分割するのはMeCabと呼ばれる処理系を使いました。実装はPythonで行いました。最終的に python twitterと呼ばれるライブラリでtwitterにポストしていました。
CS4では係り受けの結果を利用しました。具体的には前件、後件に単語ではなく文節をあてて、文章生成を行いました。結果3.14のときよりもさらに日本語らしい文章の生成に成功しました。
より日本語らしい文章になったというコメントをいただいたCS5は、実は単語分割した表層（文字面）しか使っていません。しかしあれだけの精度の高い文章が生成可能です。実はとあるライブラリを使って文章生成を行っています。これはいまのところ、秘密です☆
共起のしやすさも考慮しています。
なお現在ではtwitterへのポストをtweepyと呼ばれるOAuth投稿可能なライブラリに変更しています。
実際の運用はMac Miniで行っています。少し古いですが、Hudsonで投稿の成功／失敗を管理しています。現在４つのタスクがHudsonには登録されていて、その内二つはkimrin専用の「寝坊したらBossにメールするw」アプリが、また残り二つのうち一つがメカウーサーで、もう一つは秘密のメカウーサー試験用アカウントへの投稿を行っています。
以上こんな感じになります。ではちゃお〜（文責：kimrin）
2012年1月29日日曜日
メカウーサー（twitter bot）誕生秘話(1)
秘話というほどではないのですが、メカウーサー自体のいきさつとかを解説したページって、そういえばないなぁ、、、と思ったので、これから2回くらいに分けてメカウーサーの誕生のいきさつと、歴代のバージョンについての簡単な技術解説をしたいと思います。
第１回目はメカウーサー誕生のいきさつです。
皆さんは多分メカウーサーを知っていると思いますので、「うーさーのその日暮らし http://www.saturn.dti.ne.jp/~wooser/」というサイトはもうご存知だと思いますが、自分はかつて（そして今でも）そのサイトのにわかファンでしてw このサイト、宵越しのログは持たない方針でログが無いので自分で毎回ちまちまと更新ごとにフォルダに保存、フォルダに保存、しておりました。
そんなある日（恐らく2007年の12月頃）うーさーさんがサイトで
「誰かこの子に暖かい毛布とボットを」
的な発言をされて、ボット欲しいとおっしゃっていたのを目にして、
「じゃぁ２週間くらいでサクっと作ってみよう」
と自分のところにあるログをかき集めて文章の生成系を作成したのが１月から２月
くらいでしょうか。それが初代のメカウーサーになります。
ただ、その時は軽い遊びのノリでそのまま公開しちゃえばいいやと思っていました。
うーさーさんから大変興味深いとのメールを頂きました。
ただ、まだimproveできる余地があるとのことで、３月の始めの公開まで次の改善を行いました。具体的にはkimrinがプログラムを変えて生成ログをうーさーさんにお渡しし、うーさーさんが改善点を指摘する、kimrinが直すというスタイルでした。
・コーパス（言語資料）はうーさーさんが新たに書き下ろす（！）
・読点のバランスや文の長さについて見直す（主にうーさーさんの観点から）
・文章生成系を改良する（kimrin）
その結果、晴れて2008年3月3日に最初のツイートをすることができました！
（実際には3月２日の18時から３時間ごとに更新を掛けるように設定しました）
実はこの時ライバルとして目指していたのは今はR.I.P.されているkyoujinさんでした。
更新頻度などはうーさーさんと相談して、３時間ごとに、とこの時決めました。
結果としてうーさーさんには多大なるコーパス書き直し作業が発生しました。
作者としては嬉しい反面心配する毎日でした。
最終的には追加したtwitterログなど含め、約1MBのテキストコーパスが完成しました。
これが現在のメカウーサーを支えるメカウーサーコーパスとなります。
（うーさーさん、多謝です！）
開発はWindows上でPythonを使って行いました。
MeCabを使い形態素解析をして言語統計情報を作る部分を作成して、
そこから得られる情報を基に3時間に一回ツイートをする部分を作成しました。
ただWindows上で定期ジョブの管理をするのがやや難しいなどの点から、
その後はMac Mini上で運用するようになりました。
多分メカウーサーを知っている方は「うーさーさんがログをぽーんと渡して、kimrinさんがエンジン繋げただけで出来あがったのでは」とお思いになるかもしれませんが、
実際はうーさーさんとkimrinの共同作業がそれなりの量あったことを忘れないでいただけたらと思います。
その後もメカウーサーは改良を続け、現在ではCS5というバージョンを運用しています。
次回はその文章生成エンジンについて、簡単にお話したいと思います（文責：kimrin）。
第１回目はメカウーサー誕生のいきさつです。
皆さんは多分メカウーサーを知っていると思いますので、「うーさーのその日暮らし http://www.saturn.dti.ne.jp/~wooser/」というサイトはもうご存知だと思いますが、自分はかつて（そして今でも）そのサイトのにわかファンでしてw このサイト、宵越しのログは持たない方針でログが無いので自分で毎回ちまちまと更新ごとにフォルダに保存、フォルダに保存、しておりました。
そんなある日（恐らく2007年の12月頃）うーさーさんがサイトで
「誰かこの子に暖かい毛布とボットを」
的な発言をされて、ボット欲しいとおっしゃっていたのを目にして、
「じゃぁ２週間くらいでサクっと作ってみよう」
と自分のところにあるログをかき集めて文章の生成系を作成したのが１月から２月
くらいでしょうか。それが初代のメカウーサーになります。
ただ、その時は軽い遊びのノリでそのまま公開しちゃえばいいやと思っていました。
うーさーさんから大変興味深いとのメールを頂きました。
ただ、まだimproveできる余地があるとのことで、３月の始めの公開まで次の改善を行いました。具体的にはkimrinがプログラムを変えて生成ログをうーさーさんにお渡しし、うーさーさんが改善点を指摘する、kimrinが直すというスタイルでした。
・コーパス（言語資料）はうーさーさんが新たに書き下ろす（！）
・読点のバランスや文の長さについて見直す（主にうーさーさんの観点から）
・文章生成系を改良する（kimrin）
その結果、晴れて2008年3月3日に最初のツイートをすることができました！
（実際には3月２日の18時から３時間ごとに更新を掛けるように設定しました）
実はこの時ライバルとして目指していたのは今はR.I.P.されているkyoujinさんでした。
更新頻度などはうーさーさんと相談して、３時間ごとに、とこの時決めました。
結果としてうーさーさんには多大なるコーパス書き直し作業が発生しました。
作者としては嬉しい反面心配する毎日でした。
最終的には追加したtwitterログなど含め、約1MBのテキストコーパスが完成しました。
これが現在のメカウーサーを支えるメカウーサーコーパスとなります。
（うーさーさん、多謝です！）
開発はWindows上でPythonを使って行いました。
MeCabを使い形態素解析をして言語統計情報を作る部分を作成して、
そこから得られる情報を基に3時間に一回ツイートをする部分を作成しました。
ただWindows上で定期ジョブの管理をするのがやや難しいなどの点から、
その後はMac Mini上で運用するようになりました。
多分メカウーサーを知っている方は「うーさーさんがログをぽーんと渡して、kimrinさんがエンジン繋げただけで出来あがったのでは」とお思いになるかもしれませんが、
実際はうーさーさんとkimrinの共同作業がそれなりの量あったことを忘れないでいただけたらと思います。
その後もメカウーサーは改良を続け、現在ではCS5というバージョンを運用しています。
次回はその文章生成エンジンについて、簡単にお話したいと思います（文責：kimrin）。
2012年1月22日日曜日
WCSC22 （第２２回世界コンピュータ将棋選手権）
先ほどコンピュータ将棋選手権の出場手続きを取りました。あ、月曜日に郵便局いってきます。
今年は並列（GPGPU）のメカウーサー将棋を出場させたいと思っています。できればボナンザさんのfv.binも使えればと思っています。
目標はYBWCをGPGPU上で動かすこと、並列な可能手生成と評価関数の計算を行うこと、です。
進捗は芳しくなく、まだまだ先は長いですが、ゆっくりと歩を進めていきたいと思います。
Hello, Mechawooser
twitterのアカウントに書くのも良いのですが、長々してしまうとやっぱりちょっと、ということでブログを開設してみました。主にメカウーサー将棋（GPGPUで動作する将棋プログラム）とtwitter botである我らがメカウーサー（http://twitter.com/mechawooser）について中心に書いて行こうと思います。
まだbloggerの使い方がよく分かりませんが、よろしくお願い致します。
まだbloggerの使い方がよく分かりませんが、よろしくお願い致します。
登録:
投稿 (Atom)