« 2010年11月 | トップページ | 2011年1月 »

2010/12/31

引き続き将棋世界2月号の連載記事「コンピュータは7冠の夢を見るか」より

文化的な面だけでなくアルゴリズム的な面でもバックギャモンの話は面白かった。

山本(東京大学の先生でコンピュータ将棋の開発者でもある人)
<<省略>>構造としては評価関数が重要な位置を占め、探索はチェスや将棋に比べると、 あまり重視されてはいません。 <<中略>> 探索は4手くらいでしょうか。もしくはロールアウトです。 <<中略>> あらゆる出目を想定して探索するとコンピュータでも4手がせいぜいといったところです。

将棋のようなmin-max法をベースに探索して答えを出すゲームは、αβ法という「単純(?)、高速、安全」と三拍子そろった後方枝刈りが強烈に効く。αβが強烈に効くがゆえに、コンピュータ将棋/チェスの世界では、ほかのテクニックもいかにαβを効率的に利用するかを主眼に置いているように思える。たとえば、反復深化法、NULL-MOVE、ヌルウィンドウサーチ、キラームーブなどがまさにそうだ。

しかし、バックギャモンや麻雀のように確率に支配されるゲームの場合、αβ法は使えない。
(余談だけれど、そのため、論文読み解く教養がないのに、麻雀ゲームに生かす目的でインターネットで見つけたチェスや将棋の論文を必死に読み解いていると、論文の主旨を理解できた瞬間に、麻雀では使えないことが分かってがっかりするというケースがとても多い。)

麻雀には、安全に刈れる後方枝刈りの技法がないので、全幅探索で読みを深めると指数関数的爆発の影響をもろに被る結果となる。そのため、麻雀の探索は、将棋やチェスと比較すると、不完全情報ゲームのプログラムをやったことがない人には理解してもらいにくいくらい、探索できる深さが浅くなるのだが、バックギャモンも似たような感じらしい。

計算量の爆発を抑えるために、私は仕方なく人間の経験を生かした前方枝刈りしているけれど、その結果、まったり麻雀はやたらとリーチが早くて愚形が多い、いわゆる棒テン即リータイプの雀風となってしまっている。

バックギャモンの場合は枝刈りに力を入れずに、結果をフィードバックして機械学習する手法など、評価関数に力を入れることで読みの浅さをカバーできているようだ。

麻雀の場合、スタートの局面が一定ではないため定跡が使えず、ゴールの目標も局単位でみると複雑になりがちで、リスクとリターンが表裏一体であるゲームでもあるため、機械学習がやりにくい。さらに、無駄にルールが複雑なこともあり評価関数の数値算出自体が探索処理をともなってしまうこともある。そのため、確率的な局面の推移と親和性がとれ、かつ、演算速度が速い局面評価関数を作るのはとても難しい。

まったり麻雀の評価関数はかなり雑で、ゲームアルゴリズムを専門にやっている人の前で評価関数と呼ぶのも恥ずかしいレベルなのが現実の姿。
麻雀の場合、無駄ツモさえなければ、ゴールまでの距離は短いことと、序盤は19字牌を整理してれば何とかなることが多いので、それでもゲームになるのだけど、改善しないといけない問題であることは間違いない。

いままで、まったり麻雀のAIに生かせるものはないかと将棋や囲碁の思考ルーチンのノウハウを学んできたが、バックギャモンのAIは強化学習のような教師なしの機械学習を使ってるという程度の知識しかなく未知だった。これからはバックギャモンのノウハウも学んだ方が麻雀に生かせるのかもしれない。そのためには、まずはバックギャモンのルールを覚えてゲーム固有の特性をつかむとという、AI以前の部分から始めなければいけないが……

| | コメント (0) | トラックバック (0)

コンピュータが強くなると、ゲームはどうなるか

将棋世界2月号の連載記事「コンピュータは7冠の夢を見るか」。今回は別のジャンルのゲームの話。そのなかで、バックギャモンの世界ランク1位の望月さんの話が結構が興味深かったので引用。



望月
ところで、将棋関係のいろいろな記事を読むと、将棋界の方はコンピュータに対して「うぶ」というか、「負けてはいけない」というアレルギーがあるのかなと思います。
でもコンピュータが強くなると、人間のレベルはどんどん上がると思いますよ。
<<中略>>
望月
コンピュータが導入されたことで、バックギャモンが持つ「ミステリー」の部分が減りました。そのためギャンブルとしてバックギャモンをとらえている人たちは離れていきました。しかし逆に、純粋にゲームとしてとらえる人はとても増えたと思います。

なるほどという感じがする。麻雀もコンピュータが人間のトップを超えたとき同じようなことが起こるかもしれない。

将棋世界 2011年 02月号 [雑誌]
将棋世界 2011年 02月号 [雑誌]
毎日コミュニケーションズ 2010-12-29
売り上げランキング :


Amazonで詳しく見る
by G-Tools

| | コメント (0) | トラックバック (0)

2010年度天鳳成績

2010年の成績の天鳳特東の成績。
Photo_2


東風荘も含めると、まったり麻雀の開発を始めた2004年から6年連続で前年度成績を上回ることができた。元がへたくそで成長が遅いだけかもしれないが、素直にうれしい。
来年こそは何とか、鳳凰卓に定着したい。

まったり麻雀の方は、Ver0.8公開以降で初めてまったく新規リリースがない年となってしまった。2011年もはたしてリリースできるかどうかは微妙だけれど、あせらずゆっくりVer0.9を作っていきたい。

| | コメント (0) | トラックバック (0)

赤ドラ対応ほぼ完了

ゲーム進行部、GUI部の赤ドラ関連の修正が終了。
この作業の過程で多くのバグを見つけてちょっと不安になったんで、次はバグや内部矛盾チェックの作業をやることにする。
それが終わったら、いよいよ、思考アルゴリズムの組み込み作業に取り掛かる。

| | コメント (0) | トラックバック (0)

2010/12/26

赤ドラ対応中

赤ドラ対応でバグ多数発見。ある意味先にやってよかったのかもしれないな、赤ドラ対応。

あとUI部分で残っている作業は加槓の処理ぐらい。
ただUI以外にも役判定部分などもまだ変えないといけない。

| | コメント (0) | トラックバック (0)

2010/12/15

コメントできない

なぜか自分のブログに自分のパソコンからコメントができない。
しかたなくiPhoneからコメントしたけれど……
どうなってんだ?>ココログの中の人

| | コメント (0) | トラックバック (0)

2010/12/11

バグだらけ

赤ドラ対応中だけれども、バグがたくさん見つかってなかなか進まない。
赤5をチーすると赤5三枚のポンの状態で画面に表示されるとか、AI部に渡している4人に共通に見える情報とゲームマスターが保持している情報が一致していないとか、チャンカンと一発の複合関係とかもうボロボロ。

赤ドラ対応はほぼ全面的にソースを見直すはめになるのである意味バグだしにはいい機会なんだと、無理やり前向きにとらえることにする。

| | コメント (2) | トラックバック (0)

2010/12/04

UI部分はほぼ完成

影の描画、立直後のオートツモ、右クリックでの鳴きキャンセルを実装し、ダイアログにシバ棒と供託立直棒を表示するようにした。

Photo


2


これで大体GUI部分は完了。
次は、AI部の予定だったけど、先に赤ドラ対応をやることにする。

| | コメント (2) | トラックバック (0)

« 2010年11月 | トップページ | 2011年1月 »