フダンの記録 このページをアンテナに追加

2012-07-29

[]趣味の将棋プログラム 18:55 趣味の将棋プログラムを含むブックマーク

最近は研究とは別に、趣味で将棋プログラムの改良をしています。色々遊んでいるので、試したアイデアが成功したら研究へのフィードバックもありえますが、とりあえずは単にバグ出しと適当なパラメータいじりに使用している状況です。メモを兼ねての日記更新なので、あまりまとまっていません。

編集途中に保存するつもりがうっかり公開してしまったので、少しずつ編集しました。

コンピュータ将棋連続対局道場ことfloodgate にvps_mc という名前で投入しています。名前の通り、モンテカルロ法(+UCT) を使う将棋プログラムVPS 上で動いています。OSL/GPS将棋 を利用しており、モンテカルロ法部分では静止探索を行います(詳細は、モンテカルロ木探索将棋プログラムmcts の解説など - フダンの記録 を参照)。

現状ではVPSCPU があまり速くないこともあり、序盤から中盤では毎秒1000~2000 プレイアウトで、終盤では詰将棋を呼ぶ関係でか毎秒400~1500? プレイアウトぐらいになっています。

VPS を借りて遊んでいたのですが、基本的にそんなに負荷のかかるものは動かしておらず、もったいない気分になったため将棋プログラムでも動かそうというのが発端でした。

はじめは、評価関数を使わないmonte carlo を投入しようと思ったのですがそれはあまりに弱いので、評価関数を使うバージョン、それでも詰将棋を呼ばないなどあまり真面目でないプログラムを投入していました。

しかしひどい棋譜を見ているうちに改善したくなり、真面目に改良を施していった結果が現状です。

最初の頃に真面目でない版を投入した結果、元のプログラムバグや潜在バグを見つけたので、元をとれているような気がします、趣味なので元を取るも何もないのですけど。というか今もなおバグがあるので直さないと駄目ですね。

詰将棋なしだと1手詰判定関数が詰と言ったら勝ちで、"詰の手を返さない"ようになっていたので詰を逃して負けるという悲しい出来事がありました。普段はルートで詰将棋探索を呼び、詰むなら詰み手順(の1手目)を返すので大丈夫です。

グラフを見ると、6月10日前後からレーティングが上昇しており、300点ぐらい上がったようです。このあたりは色々と工夫をした成果が出ているので楽しかったですね。時間制御にパニック・タイムを入れるなどの改良をしていました。

7月10日ぐらいからは何もしてないので、また何か工夫を入れてレーティングを上げられればと思いますが、どうなりますかね。

VPS

利用しているVPSsaases のosukini server のLT プランです。月々450円で、メモリは512MB, CPUCore 2 Quad CPU Q8400 @ 2.66GHz の1コア。

しかし、gpsshogi でベンチマークしてみると9万nps でCore 2 Quad 2.33GHz の1コアでも10.5万nps程度出ていることを考えるとCPU 性能は落としてある様子。まあVPS ですし。

VPS の良い点は、電気代がかからないことと、ネットワークも気にしないで良いこと*1、無音で部屋が熱くならないことがあります、札幌もいい加減に暑くなってきましたし最後は重要ですね。

棋譜

最後にいくつか棋譜の紹介を。

激指に勝っていて何があったのかと思えば、激指王手千日手で負けていた棋譜詰将棋との兼ね合いが変なことになっているんでしょうかね。

入玉宣言勝ちをMCTS の中でも確認するようにした直後に宣言勝ちをした棋譜。その後は入玉宣言勝ちは見かけませんからまぐれでしょうね。

*1:一度落ちたけど

トラックバック - http://d.hatena.ne.jp/tawake/20120729

2011-11-23

[][][]モンテカルロ木探索将棋プログラムmcts の解説など 13:20 モンテカルロ木探索将棋プログラムmcts の解説などを含むブックマーク

1年経った今更、floodgate に参加していたmcts*1 について解説。今年のGPW でも、激指でこの手法を使った研究がありました*2

まずは3行で。

  • 評価関数を信用してプレイアウトを打ち切ると得できるのでは
  • 将棋向けに工夫しながら、GPS 将棋を使って実験した
  • 従来のMCTS 将棋よりも強くなったが、アルファベータには敵わない

こんなところ?あとはポスター見るのが早いと思う。

以下、2010年の11月にゲームプログラミングワークショップ (GPW2010) でポスター発表した内容を紹介。

floodgate にいたmcts はこの内容に基づいて作成し、その後工夫を加えたプログラムで、マシンのCPUは、Intel(R) Core(TM)2 Quad CPU Q9650 @ 3.00GHz で1コアだけ使っての参加、並列化していない。

概要

前提

以下の知識は知っているものとして説明しない。

資料

GPW2010 の予稿と発表したポスターは以下からダウンロードできる。

プログラムの中身

OSL とGPS 将棋を利用して作成した。

今回の実装において使った手法パラメータは、ゲーム木探索部分とモンテカルロ部分とでそれぞれ以下のとおり。

  • ゲーム木探索部分
    • UCT (UCB1)
    • 1手詰関数
    • MCTS Solver[4] (MCTS において詰みを扱う)
    • ノードを作る訪問回数の閾値 : 1
    • Progressive Bias (手の選択の際に、実現確率に応じて重み付けする)
    • First Play Urgency : 0.9
  • プレイアウト部分 (モンテカルロ部分)
    • 1手詰関数
    • 実現確率上位5手からランダムに選択
    • 評価関数/静止探索ベースの勝敗判定 (ここが肝)

先行研究

MCTS 将棋

MCTS将棋へと応用した内容を、棋理の開発者佐藤さんが発表している[5][6]。様々な工夫があるが、本研究ではプレイアウト部分の改良がメインであったこともあり、当時は採用していなかった。

    • ゲーム木探索部分で静止探索を行い、評価が悪くなる手の勝率を下げる
    • Killer-Move, History Heuristic
評価関数の利用

Amazons, Lines of Action (LOA) では、評価関数を用いたMCTS が成功しており、それぞれアルファベータを上回るか同程度の結果を得ている。 (Arimaa でも行われたがあまり成功していない) 。

Amazons, LOA で成功した手法は、評価関数が正確という前提のもと、プレイアウトの勝敗判定に評価関数を利用する手法

違いはその判定の仕方、評価関数の使い方であり、それぞれ

  • LOA (EF-Cutoff @ ポスター)
    • 評価値が勝ちの点数以上ならそのプレイアウトは勝ちとする
      • 負けの点数以下なら負け
  • Amazons (EF-Leaf @ ポスター)
    • ある深さまでプレイアウトして、そこでの評価値/評価値の正負を返す

となっている。

なお、LOA ではプレイアウトの指し手の選択にも評価関数を使っているが、今回は省く*3。詳細は文献[1]を参照。

提案手法など

まず、従来のMCTS 将棋における問題点を考える。

  • 従来手法の問題点
    1. 探索が必要な局面は不得意
    2. 優勢な局面において最善手を逃す傾向/緩い手を選びがちになる
    3. プレイアウトが終局しにくい

評価関数の利用で問題点3 は改善する見込みなので、残りの問題点を解決するように以下の手法を提案した。

  • 静止探索の利用
    • 問題点1 に対応
    • 評価値を将棋で使う以上、静止探索の利用は自然な発想
    • 探索コストがかかるため、採用すべきかは自明ではない
  • ルート局面の評価値との差を利用
    • 問題点2に対応
    • ルート局面と評価値を比較することで、ルート局面よりも良くなる手を選ぶようになることが期待される

両方をEF-Leaf, EF-Cutoff に採用した手法が、ポスターの提案手法 (4,5) が該当し、それぞれQS-Leaf-Diff, QS-Cutoff-Diff と呼ぶ。

実験

実装し、実験した。問題集の正答数の比較や自己対戦によって性能評価を行った。

自己対戦のまとめ

が確認された。

静止探索の利用は探索コストと評価値の正確さのトレードオフがあるが、メリットが上回ったと思われる。

レーティング

QS-Cutoff-Difffloodgate に投入し、レーティングを計測した (~2010/9/12)。

2週間レーティングは1821 となった (当時のMCTS将棋プログラムでは最高のレーティングのはず) 。

主要な対戦成績

  • YSS-1S (レーティング(以下Rと表記) 2008) : 19勝33敗
  • gps_normal (R 2150) : 5勝22敗
  • Blunder (R 2378) : 1勝13敗

ただし、同じ評価関数を使っているgps_l はレーティング 2464 であり、従来のアルファベータ探索を行うプログラムには及んでいない。

まとめ

参考文献

[1] Winands Mark H. Bj\"{o}rnsson Yngvi, "Evaluation Function Based Monte-Carlo LOA", Advances in Computer Games 2009

[2] Julien Kloetzer, Hiroyuki Iida, Bruno Bouzy, "The Monte-Carlo Approach in Amazons", Computer Game Workshop 2007

[3] Lorentz Richard J., "Amazons Discover Monte-Carlo", Computers and Games 2008

[4] Winands Mark H., Bj\"{o}rnsson Yngvi, Saito Jahn-Takeshi, "Monte-Carlo Tree Search Solver", Computers and Games 2008

[5] 佐藤 佳州, 高橋 大介,"モンテカルロ木探索によるコンピュータ将棋",13回ゲームプログラミング ワークショップ

[6] Y. Sato, D. Takahashi, and R. Grimbergen: A Shogi Program Based on Monte-Carlo Tree Search, ICGA Journal, Vol.33, No.2, pp.80--92 (2010).

-----

GPW 後の進捗など

  • 自己対戦数を増やした
  • パラメータを多少調整
  • [5][6] の手法の採用
    • ゲーム木探索パートで静止探索
    • Killer-Move, History Heuristic など
  • ルート付近で詰将棋探索
    • 訪問回数が閾値を超えたら軽く呼ぶとか

Misc

  • 評価関数に静止探索まで使ってモンテカルロと呼べるのか
    • 先人がそう呼んでいるし、プレイアウトは行なっているし、良いのでは?
  • プレイアウトしないで評価関数なり静止探索すれば良いのでは
    • 当時、実験したが、深さ2までプレイアウトする方が強かった
  • 読みにくい
    • そんな人のために3行を用意しました。あとはポスター見れば良いと思う

mcts のデータ

mcts (プログラム) のデータを調べたら2011/06/14 までfloodgate にいたらしい。

  • 1手3秒だかで、Bonanza Feliz と100戦した結果: 2勝98敗

Todo

明日から本気出(ry

*1:名前は真面目に考えてつけるべき

*2http://id.nii.ac.jp/1001/00078263/

*3:実装してみたけど、手を進めて戻す必要があるので重い。SEE で代用してみたが振るわず

*4403 Forbidden に日付ごとのレーティングが保存されています、便利ですね

2010-07-27

[][]モンテカルロ木探索将棋プログラム 20:06 モンテカルロ木探索将棋プログラムを含むブックマーク

モンテカルロ木探索プログラムでgps_normal に勝ちました。normal 倒したMCTS 将棋プログラムは初めてだと思います。

このMCTS 将棋プログラム(mcts_qcde, mcts_qcdem) は、GPS将棋/OSL をベースとして実現確率や評価関数などを使ったものです。floodgate へ投入しており、レーティングはyowai_gps より強いぐらいになっているようです。なお、プログラムの詳細についてはGPW にて発表する予定です。

トラックバック - http://d.hatena.ne.jp/tawake/20100727

2009-05-09

[]世界コンピュータ将棋選手権 23:49 世界コンピュータ将棋選手権を含むブックマーク

GPS将棋が優勝しました、何だか実感がありません*1。会場では多くの方に応援、コメントしていただき、ありがとうございました。

選手権中一番の仕事は勝又先生に「友達なくすよう手を指すにようになったね、どうしたの?」と聞かれた時に「友達の評価が低くなったのでは」と答えたことです。友達より駒得!

選手権の棋譜にGPS将棋の読み筋と評価値がついており、floodgate みたいに評価値グラフなどが見られるようになっています (世界コンピュータ将棋選手権/第19回 - PukiWiki)。指し手を見ても読み筋を見ても自分の棋力では何でこうなるのかわからないのですが、どうすれば。

GPS将棋ついては、shogi programming journal (2009-05-07) で詳しく書かれています。公式サイトは GPSshogi - PukiWiki です。

選手権マシンでGPS将棋がfloodgate に投入されています。gps_l がOpteron 280 (1thread)Opteron 248 (1thread) (5/10 訂正しました) で中身は一緒なことを考えると、gps_l にはそう簡単に負けずレーティングが大きめに出すぎるような気がします。(マシンスペック参考: shogi programming journal (2008-05-20))

バイナリが公開されております。Linux 環境のある人はお試しになられてはいかがでしょうか。

Q&A *2

経験者によると滅茶苦茶疲れるそうです。しかも1局終わったと思うとすぐに次の対局が!

*1:あまり貢献していないせいでしょうか

*2:冗談です

t-tsu3t-tsu3 2009/05/10 02:31 つちまつです。おめでとー!なんかwikiには書き込めないので
こっちに書くよ。僕も負けずにがんばります。論文論文。
夏からは駒場にいるからちょくちょく飲みましょう。

ktanakaktanaka 2009/05/10 07:46 gps_normalは「Opteron 280」なのだと思いますが,gps_lが動いているマシンは「 Opteron 248」が正しようです.クロック速度 2.4GHz -> 2.2GHz 程度の違いしかないので,金子さんは「ほぼ同等のマシン」と説明しているのでしょう.一応訂正をお願いします.

tawaketawake 2009/05/10 10:59 > つちまつ君
ありがとうございます!お互い論文頑張りましょう。
是非飲みに行きましょう。

> 田中先生
ご指摘ありがとうございます、訂正しました。
動いているマシンが違うことを忘れていました。

兄です。兄です。 2009/05/11 15:04 久しぶり。おめでとう。以上。いつか弊社のPCにプリインストールして出荷させてください。

tawaketawake 2009/05/11 23:16 ありがとう。
そちらは協賛ということで副賞のノートPC を贈られましたよ。

tawaketawake 2009/07/26 23:16 スパム削除。どうにかならないかな。

トラックバック - http://d.hatena.ne.jp/tawake/20090509

2009-01-29

せっかく書いておいた日記の下書きが消えていたので、適当に。

[]Bonanza ソース公開 13:07 Bonanza ソース公開を含むブックマーク

  • ダウンロードに10時間かかったよ
    • 「あと20分」と出てから4時間ぐらい待ったよ
  • パッと見た感じではCrafty に良く似ている印象
    • いじりやすそう
    • 枝刈の実験とかで使える
      • GPS将棋は実現確率探索なので入れにくい
  • オリジナリティはどうやって判定するんでしょう、というのが目下の疑問
    • ライブラリなので選手権でも利用可能な件について
    • Bonanza に少し変更入れたものが乱立したらつまらなさそう
  • いつかあとでちゃんと読む

[]近況 13:07 近況を含むブックマーク

適当に元気に生きています。

  • 高校の友人の結婚式に出席
    • 昨年は、知り合いが10人くらい結婚というラッシュっぷり
  • 情報処理学会の山下記念研究賞を受賞
    • 表彰は3月の全国大会、多分行かない
  • サザンが活動休止
  • 情報科学若手の会に幹事として参加
  • 最中限が流行
  • 昨秋から実家/地元へ引っ越したので片道2時間通学
  • GPW(箱根)へ参加、発表
    • 今年も楽しく過ごさせていただきました
  • CIG(パース、オーストラリア) へ参加、発表
    • 時差はないけど、季節が真逆
    • Pub Quiz などイベントが多くて楽しかった
    • 機内で見た中国語「格林威治」(グリニッジ)
      • 民明書房っぽい
  • 学振(DC-2)に内定
  • 春からは一人暮らしを
    • できれば片道30分以内
    • GPS将棋の人から「早稲田が良いよ」という声が
      • 選手権のためだけ?

豆知識: 夏の昼間、屋根に登ると超暑い。

[]42 13:07 42を含むブックマーク

銀河ヒッチハイクガイドシリーズを全巻読みました。面白くってしかたがないです、マーヴィンとかアグラジャグとか。「生命、宇宙、そして万物についての答え」を知っていたので、作品中で出てきた時に「知らなければもっと楽しめたのに!」と悔しく思ったものの、知っていたからその本を読みだしたというジレンマみたいな何かが。