【勉強会メモ】コンピュータ将棋【歌舞伎座tech】

1 Star2 Stars3 Stars4 Stars5 Stars (まだ評価されていません)
Loading...

kabukizatech.png

勉強会情報

会場

株式会社ドワンゴ 歌舞伎座タワーF14セミナールーム

時間

2014/6/21 19:00-21:30

詳細

connpass – 歌舞伎座.tech#4「コンピュータ将棋プログラミング」

配信

ニコ生 – 歌舞伎座.tech#4「コンピュータ将棋プログラミング」

「コンピュータ将棋の歴史と基本アルゴリズム」 ー 瀧澤 武信(コンピュータ将棋協会会長)

これまでの戦績の説明

プエラアルファ

塚田9段:かつて非常に強かった。この時は最高に強いというわけではなかった(笑)
持将棋:必敗の形から

三浦 vs GPS

7五歩 同歩 8四銀
珍しい形、プロでもさされるようになる

第三回

今回は事前にプロ側に貸出
今度は勝つだろうと思われていたが、1勝4敗

コンピュータ将棋の歴史

コンピュータの歴史とコンピュータチェスの歴史はほぼ同じ

  • 1997年 実力:アマ二段
    カスパロフに6局戦って勝ち越した
    今では普通のPCでもプロは勝てない

  • 2005年 アマ竜王戦ベスト16 実力:アマ五段
    TACOSが橋本7段に勝ちそうになった

コンピュータ将棋の基本技術

mini-max原理30ノード(評価:18ノード)

α-β法 22ノード(評価::12ノード)
「カットされる」先を読まなくていい

効率良い場合 16ノード(評価:8ノード)
より短く、時には深く読める
並び方が勝負(今のコンピュータ将棋の関心事)

その他の技術

  • 反復進化
  • トランスポジションテーブル
  • Futility枝刈り、null-move枝刈り
  • singular拡張
  • 静止探索(捕獲探索)
  • 証明数探索(詰将棋の研究で得られた)

他分野への応用が期待されるアルゴリズム

  • 実現確率探索(激指)
  • 評価関数のパラメータの自動調整(Bonanza)
    偏微分方程式を解く
  • 並列探索(大規模クラスタ)(GPS)
  • 合議(もんじゅ、あから2010)
    ※人間(棋士)だとうまくいかないが、コンピュータだと何故かうまくいく

質疑応答

合議が人間(棋士)だとうまくいかないが、コンピュータだと何故かうまくいくのはなぜか?

統一性がない。コンピュータは何故かうまくいく

何年ぐらい先に人間のトップに勝てるか?

  • 今はトップ(森内さん、羽生さん)のレベルにはまだ到達していない
  • 3年くらい経ったら同じくらいになっている。さらに3年たったら人間は勝てなくなるかも

棋風はどこから出てくるのか

元となる棋譜のどこを重点的に取るかで変わる

「Bonanza のヒューリスティック探索法:前向き枝かりと勝利の三角形」 ー 保木 邦仁(Bonanza開発者)

思考アルゴリズム概要

  • ゲーム木探索
  • 最善応手系列を計算すると次の一手が出る
  • 将棋は平均して80手(枝が80本伸びる)
  • どうすれば効率よく探索できるか?

mini-max探索の効率化

上記と同様

前向き枝刈り

part1(Extended Futility 枝刈り)

なんで上手くいくのかわからないが、経験的になぜか上手くいく
1. コマをとる手
2. 1.をもう少し探索(浅い探索)
3. 他は枝刈り

part2(Late Move Reduction法)

  1. コマを取る手
  2. 1.の深い探索
  3. 他の手も一応浅い探索
  4. いい手が見つかる
  5. 4.をもう少し探索
  6. 他は枝刈り

part3 (null move 枝刈り)

  1. コマを取る手
  2. 1.の深い探索
  3. 他の手
  4. パス(実際は将棋にパスはないが)
  5. 浅い探索
  6. 枝刈り

数値分析

アルファベータ、3種の前向き枝刈り、有効分岐因子は3程度
普通のノートパソコンで1秒程度の時間で、深さ8の全幅探索

評価関数の自動学習法

  1. ルート局面
  2. 子局面
  3. プロ棋士の選択、コンピュータの選択に点数の偏りがあればプロ棋士の選択に近付けるように調整
  4. 目的関数を設計して最適化していく

目的関数の特徴

  • 複数の極小点を持つ
  • 大局的極小点の方が合理的なコマ価値を持つ
  • 偏導関数は連続でない
  • 目的関数は連続

大規模な機械学習の成功

  • 目的関数に含まれる階段型関数をなめらかな関数で近似
  • 束縛条件付加による無限遠点の局所最適解除法
  • 正則化による過学習の回避

王を含む3駒全通りに対する値付け

※図で説明してました

評価関数自動学習の問題点

  • 局面評価の精度で人間を超えることが出来ない
  • 探索の深さで改善(10ミリ秒程度の時間で人間の1分程度の思考に到達)

まとめ

コンピュータチェスでは1997年力ずく探索の改良で人間に勝った

将棋でもデータ処理の量が多ければ多いほど強くなるようになって来た

質疑応答

他のソフトとの類似はあるのか

他のソフトが公開してくれていないから分からない

何故Bonanzaは公開したか

お金持ちになれるのであれば、公開しなかった(笑)
あとは他のソフトも公開していた

勝利の三角形を評価する方法について

Bonanzaは3駒全通り力ずく
他のソフトは力ずくでないアルゴリズムを採用しているものもある

勝利の三角形はどこから着想を得られたのか

そんなに突拍子もないことではない
二つの組み合わせはすでに他のソフトやチェスでもあった
それを単純に三つにした
因みに四つはメモリに乗り切らない(笑)

「SIMDと将棋プログラム / Magic Bitboard」 ー 山本 一成(Ponanza開発者)

将棋プログラムにとって大事なこと

  • 正確な評価関数?
  • 精密な探索技術?
  • そもそもコンピュータ将棋の強さの秘訣は上記二つをただただ速く読むこと
  • 人間でもたかだか1秒で1局面

2倍速くなるとどれくらい強くなる?

Pona(2倍速) vs Pona
⇒勝率7割(楽観的に8割という人も)

羽生四冠の生涯勝率はおよそ7割
⇒Ponaを2倍速くできえれば羽生四冠に勝てる?(笑)

Bitboardとはなにか?

1マスを1ビットとして表現
81マスの将棋では81ビットで表現
unsigned long longが使えるので効率がよい

例)6六金の動きを算出

駒を取る手をいかに速く作るか
銀の動きのBB & 敵のBB = 取る動きのBB

それで何が嬉しいの?

  • 条件分岐がなくなる
  • ビットパラレル(平行して演算)

BB(Bitboard)

コンピュータ将棋にとって厄介な駒

香角飛馬竜
※盤面の形によって、どこまでいけるか決まるため

どうすればよいか?

単純な解決策、マスずつ数える->遅い
forループは遅い
「因みにプログラマーの方挙手」

ノノノノノノノノ

「ほとんどプログラマーじゃないですかw」

どうやって高速化するか

まずは香車で考える
BBのレイアウト(配置)を変えておく
関係するビット列に注目
右シフト10&ビットマスクで取れそう

事前に計算して持っておけば一発で取れる
香の効きtbl[][

覚えてほしいこと

必要なBitの配置をハッシュキーにできればOK

チェス界のMagicBitboard(2006)とは?

掲示板で話が盛り上がって生まれた手法

将棋でもできたらいいな

チェスの駒位置
↓低コストな操作
文字列

そう言えば掛け算ってどんな演算だっけ?

64ビット整数 * MagicNum = garbage
掛け算でBitを上位に移動

なんとか将棋でもMBBを使えないか

チェスは64bit変数だから掛け算ができるが、
将棋は64bit変数を二つ並べて擬似的に81bit変数に

MagicNumberをどう探すか?

乱数を使って取り敢えず試す(笑)
条件を満たせば採用

MagicNumberを探すのにどれくらい掛かるか?

1万回位乱数を使って見れば見つかる(笑)

角のMBBはすぐ見つかるが、飛車のMBBはなかなか見つからない

仕様メモリを増やせば解決

実用性など

PonanzaやAperyなど新しい将棋プログラムで普通に使われる

歩の移動の算出

1bitシフトで算出可能

SSE

128bitの変数みたいなもの
Shogi SIMD Extensions
ありがとうIntelの人
でも本当は81bit変数が良かったな。。。

質疑応答

Ponanzaの場合一手何分でさせば強いか?

検証が大変で、現状分からない

テーブルはCPUのキャッシュに乗るか?メモリに乗るか?

定かではないが、キャッシュには結構乗っているのではないかと期待

今回のBB以外に新しいアルゴリズムはあるか?

ソースコードとしての関係はない
が、影響は受けている

「コンピュータ囲碁の仕組み、将棋との比較」 ー 山下 宏(YSS開発者)

私について

「囲碁もつくっています。なので今日は囲碁です」

囲碁の局面評価

将棋と同じく直接変換

2006年を堺に急激に棋力が伸びた

なにがあったか?

モンテカルロ法を用いたアルゴリズムを導入

モンテカルロ法を使った囲碁の仕組み

  1. 乱数で交互に置く
  2. 打てなくなるまで繰り返す
  3. 評価する(1000回中何回勝ったか)
  4. どちらに良い局面だったかが分かる

シュミレーションの制度を上げる

囲碁知識を利用

  • 辺りを逃げる、石を取る

プロの棋譜から着手確率を求める

単純乱数と囲碁っぽい乱数

シミュレーションが強さを決める

1手に10000回のシミュレーション
純粋乱数 15級
囲碁知識を利用 2段

囲碁の木探索

手を選択 -> シュミレーション -> 勝ち負け -> 勝った手の下に降りていく
開始曲面から終了局面を何度も繰り返す
250手中30手くらいしかよまない(読み抜けの危険)

現在の囲碁棋力

アマチュアの県代表レベル
将棋に比べて10年遅れている

「習甦における非線形評価関数と確率モデル」 ー 竹内 章(習甦開発者)

局面の評価における非線形性

非線形な評価が必要と思われるケース

確率的な局面評価

習甦の評価関数群

  • 入力:効き数
  • 機器評価
  • 駒の価値
  • 評価値
  • 安定度

関数の推定手順

連立方程式を解くプログラム例

分散がどう役に立つのか

ProbCut by M. Buro
オセロで使われていた枝刈りをする手法

まとめ

線形和による評価関数群
* 玉安全度
* 駒の現在価値
* 駒の潜在価値

シグモイド関数
->玉面評価の期待値
多項式の近似
->局面評価の分散


1 Star2 Stars3 Stars4 Stars5 Stars (まだ評価されていません)
Loading...
      この投稿は審査処理中  | 元のサイトへ