Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
ビットボード解説
Search
antenna_three
November 20, 2020
Programming
1
2.7k
ビットボード解説
UTMC (
http://www.komaba.utmc.or.jp/
) の活動としてリモートで行ったプレゼンテーションです。ビットボードという技術について、オセロやチェスを例にとって解説しました。
antenna_three
November 20, 2020
Tweet
Share
More Decks by antenna_three
See All by antenna_three
GitHub Actionsで学ぶCI/CD
antenna_three
0
24
Djangoで動的サイトを作ろう
antenna_three
0
820
シェーダで学ぶ画像フィルタ
antenna_three
0
2k
レイマーチング入門
antenna_three
0
1.9k
PythonによるWebスクレイピング入門
antenna_three
0
1.8k
ゲーム制作概論
antenna_three
0
2k
Other Decks in Programming
See All in Programming
Better Code Design in PHP
afilina
PRO
0
130
Why Jakarta EE Matters to Spring - and Vice Versa
ivargrimstad
0
1.2k
リアーキテクチャxDDD 1年間の取り組みと進化
hsawaji
1
220
シェーダーで魅せるMapLibreの動的ラスタータイル
satoshi7190
1
480
Micro Frontends Unmasked Opportunities, Challenges, Alternatives
manfredsteyer
PRO
0
110
Compose 1.7のTextFieldはPOBox Plusで日本語変換できない
tomoya0x00
0
200
Click-free releases & the making of a CLI app
oheyadam
2
120
Jakarta EE meets AI
ivargrimstad
0
620
Outline View in SwiftUI
1024jp
1
330
2024/11/8 関西Kaggler会 2024 #3 / Kaggle Kernel で Gemma 2 × vLLM を動かす。
kohecchi
5
940
受け取る人から提供する人になるということ
little_rubyist
0
250
CSC509 Lecture 12
javiergs
PRO
0
160
Featured
See All Featured
Teambox: Starting and Learning
jrom
133
8.8k
The Invisible Side of Design
smashingmag
298
50k
Build your cross-platform service in a week with App Engine
jlugia
229
18k
Why You Should Never Use an ORM
jnunemaker
PRO
54
9.1k
Making Projects Easy
brettharned
115
5.9k
Designing on Purpose - Digital PM Summit 2013
jponch
115
7k
Product Roadmaps are Hard
iamctodd
PRO
49
11k
CoffeeScript is Beautiful & I Never Want to Write Plain JavaScript Again
sstephenson
159
15k
Fireside Chat
paigeccino
34
3k
The Straight Up "How To Draw Better" Workshop
denniskardys
232
140k
The Art of Programming - Codeland 2020
erikaheidi
52
13k
How GitHub (no longer) Works
holman
310
140k
Transcript
ビットボード uc
今日話すこと • 前置き • 高速化について • ビット演算基礎 • 基本セルオートマトン •
オセロビットボード • チェスビットボード
なぜビットボード? • ボードゲームなどのAIを作るには大量の手の探索が必要 • ゲームの手番処理を高速化できれば探索数を増やせる • 手番処理の高速化に使える手法がビットボード
扱う数について • 扱う数はすべて符号なし整数 (unsigned integer) • 基本的には64ビット整数を想定
n進数 • 2進数 • 基本的に断りのない数は2進数 • ほかの進数と区別するときは接頭辞 "0b" を付ける •
16進数 • 64ビット整数などの大きな数を書くときに使用 • 接頭辞 "0x" を付ける
コードについて • 提示するコードは簡略化のためPythonで示す • Pythonの整数型は符号ありで上限を持たないが、 ここでは符号なし64ビット整数であるとして扱う ( でマスクすればよい) • 引数チェックなどは省く
高速化 プログラムを高速化する手法
高速化 • 速いマシンを使う • 速い言語を使う • オーダーが小さいアルゴリズムにする • ルックアップテーブルを作る •
キャッシュ効率を上げる • 並列化する • 命令数を減らす
ルックアップテーブル • 三角関数などの引数と戻り値の対応表をあらかじめ作っておき、 プログラム実行時にはマクローリン展開などの計算をせずに テーブル参照で戻り値を求める • 計算過程で出てきた再利用できる値をテーブルに保存しておく (メモ化)
並列化 • マルチプロセッサ • GPGPU • マルチスレッド • SIMD •
ビット配列 ビットボードはビット配列を利用した高速化技術
ビット演算基礎
ビット演算 • 2進数の各ビットごとに論理演算を行う • 64ビット整数であれば64個の論理演算が同時に行われる
ビット演算 ※RustのビットNOTは 、GoのビットNOTは
シフト演算
演算子の優先順位 • • •
ビットマスク • 整数の特定のビットの情報だけを取り出したいときに、 特定のビットだけを1にした定数(マスク)と ビット演算することで情報を取り出す手法 • 例: IPv4アドレスのサブネットマスク
ビット配列 • 整数を各要素が1ビットの配列と見立てたもの • 64ビット整数なら長さ64のビット配列と見立てられる • ビットボードの基本となる概念 • ここから基本セルオートマトンを例にして解説していく
基本セルオートマトン ビット配列を用いた高速化の例 Copyright (c) 2005 Richard Ling
基本セルオートマトン • 横一列に無限にセルが並んでいる • それぞれのセルは各時刻において1か0かの状態をとる • 現在の自身と両隣のセルの状態をルールに照らし合わせて、 次の時刻のセルの状態が決められる … 0
1 0 0 1 1 0 1 1 1 … … 1 1 0 0 0 1 1 0 1 0 …
ウルフラムコード • 次のセルの状態を決めるのは3つの近傍セルの状態 • 3つの近傍セルの状態の組み合わせは23 = 8通り • 8通りの近傍セルの状態それぞれについて、次のセルの状態が 2通りあるので、ルールは28
= 256通り • 256通りのルールをナンバリングしたものがウルフラムコード • 例えば、下のルールのウルフラムコードは01011010 (2) = 90 現在の近傍 111 110 101 100 011 010 001 000 次の状態 0 1 0 1 1 0 1 0
ルール90 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 1 0 0 0 0 現在の近傍 111 110 101 100 011 010 001 000 次の状態 0 1 0 1 1 0 1 0
ルール90 0 0 0 0 1 0 1 0 0
0 0 0 0 0 1 0 0 0 1 0 0 0 現在の近傍 111 110 101 100 011 010 001 000 次の状態 0 1 0 1 1 0 1 0
ルール90 0 0 1 0 1 0 1 0 1
0 0 現在の近傍 111 110 101 100 011 010 001 000 次の状態 0 1 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 0 0
ルール90 0 1 0 0 0 0 0 0 0
1 0 現在の近傍 111 110 101 100 011 010 001 000 次の状態 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 0 1 0 0
ルール90 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
ルール90の意味 • 両隣が異なるなら1になり、同じなら0になる 現在の近傍 111 110 101 100 011 010
001 000 次の状態 0 1 0 1 1 0 1 0
ルール90を実装する|配列版
ルール90を実装する|ビット配列版
ビット配列の利点 • 整数のビット数の数だけまとめて計算することができる • まとめた分だけ計算量を減らせる • コードの記述量が少なくて済む
ビット配列の欠点 • コードの可読性が低い • 演算は基本的にビット演算 • 1つの要素には1変数あたり1ビットしか割り当てられない • 要素数がビット数を超える場合には分割が必要
ビットボードでオセロ 合法手の探索、石の数え上げ
ビットボード • オセロ、チェス、将棋などの盤面をビット配列で表す手法 • 64ビット整数の場合、オセロ・チェス(8x8)なら1個の変数、 将棋(9x9)なら2個の変数で盤面のフラグを管理できる
ビットボードでオセロ • マスの状態は「空」、「白石」、「黒石」の3通り • 「白石があるか」、「黒石があるか」の2つの64bit整数で盤面 を表せる • 「手番 (player)」と「相手 (opponent)」の方が実装上は便利
• 今回はblackとwhiteの2変数で説明
初期配置をビットボードで表す • • • •
初期配置をビットボードで表す • • • •
空白マスを求める • • • • • • • • •
• • • • • • •
黒石が置けるマス(合法マス)を求めたい • • • • • • • • •
• • • • • • • 合法マスの定義: 1. 周囲8方向のいずれかにおいて 1個以上の白石が続いたのちに 黒石があるような空のマス 2. 黒石の周囲8方向にあって 1個以上の白石が続いたのちに ある空のマス
黒石の左方向にある合法マスを求めたい a b c d e f g h 1
2 3 • • • • 4 • • • • • 5 • • • • • • • 6 7 8 • 左図におけるa5のマスが 求めたい合法マス • 少し複雑な手順になるので ステップごとに説明
黒石の左にあるマスを求める • • • • • • • • •
• • • • • • •
端を超えてしまった部分をマスクする • • • • • • • • •
• • • • • • •
黒石の左にある白石を求める • • • • • • • • •
• • • • • • •
さらに左にある白石を追加する • • • • • • • • •
• • • • • • •
合計6回繰り返す • • • • • • • • •
• • • • • • •
黒石の左方向にある合法マスを求める • • • • • • • • •
• • • • • • •
黒石の左方向にある合法マスを求める
他の方向についても同様に求める • 上下方向は8ビットシフトすればOK • 上下方向、斜め方向は対応する別のマスクを使う必要がある
石の数を数える • 最終局面での盤面評価は石の数による • 石の数のカウントもなるべく高速化したい
石の数を数える(素朴な計算)
石の数を数える(高速)
何をやっているのか • 基本的なアイデアは分割統治法 0 0 1 0 0 1 0
1 1 1 1 1 1 0 1 1 0 1 1 1 2 2 1 2 1 2 4 3 3 7 10
• • •
• •
• • •
• • • •
• 下7ビットだけをマスクで取り出して返す
popcnt • IntelのSIMD拡張命令セット "SSE4.2" でpopcnt命令が追加さ れた • 自分でpopcountを書くより2倍くらい速い
ビットボードでチェス 遠方駒の利き判定
ビットボードでチェス • 全ての駒の位置をまとめたビットボード (occupied bitboard)、 駒種別の位置・利き・チェック位置など大量のビットボードを 管理 • すべてをビットボードで処理するわけではなく、盤面処理に 応じて配列とビットボードを使い分ける
遠方駒のやっかいさ • ルーク♜、ビショップ♝、クイーン♛などの遠方駒の利きは 他の駒の位置に影響される • 計算が煩雑な上に盤面が変わるたびに更新する必要がある • 遠方駒の利きを効率的に計算するためにoccupied bitboardが 使われる
♜ ♛ ♝
ルーク♜の横利きを求める ♙ ♜ ♞ ♚ • 左図のルーク♜の横利きを求 めることを考える
ルーク♜の横利きを求める 1 1 0 0 1 1 • 利きに関係する部分の occupied
bitboardを ビットシフトとマスクで 取り出す
ルーク♜の横利きを求める ♙ ♜ ♞ ♚ • 取り出したOccupied Bitboardをキーとして、 ルークの横利きを格納した ルックアップテーブルを
参照して横利きを求める
ルーク♜の縦利き・ビショップ♝の利き • 横方向と異なり、縦方向や斜め方向の列はビットシフトと マスクだけで取り出すことはできない
Rotated bitboard • 縦方向や斜め方向の利きを算出するために、90度回転、±45度 回転させたoccupied bitboard (rotated bitboard) を管理する •
4つのoccupied bitboardを管理するので局面更新の処理が 増加する • 1つの変数に複数のrotated bitboardを詰め込めば 処理増加は抑えられる
Magic bitboard 6 5 4 3 2 1 g f
e d c b ♜ • ルーク♜が右下にあるときの 利きに関係するマスは左の ようになる • Occupied bitboardから、 利きに関係するマスを残して 関係ないマスは0にマスクす る
Magic bitboard 6 5 4 3 2 1 g f
e d c b ♜ • ここで、おもむろに を 左のマスクされたoccupied bitboardにかける
Magic bitboard g' f' e' d' c b 6 5
4 3 2 1 • すると、うまい具合に利きに 関係するマスが連続する • ただし、 • あとは横利きを求める場合と 同様に、利きに関係するマス の状態をキーとしたルック アップテーブルを参照すれば 縦横の利きが同時に求められ る g' f' e' d' = g f e d + 5 4 3 2
Magic bitboard • Occupied bitboardにかけるマジックナンバーは駒の種類と 位置に対応している • 利きに関係ないマスを0にマスクしておりボードは疎なので、 マジックナンバーの存在は十分に期待できる •
マジックナンバーを解析的に求めることはできない • 乱数を使って総当り的にマジックナンバーを求める
pext • x86拡張命令セット "Bit manipulation instructions sets (BMI sets)" にて
"pext (Parallel bits extract)" 命令が使えるように • 集めたいビットだけを立てたマスクを指定すれば、入力から指 定したビットを下位ビットに集めて出力してくれる • 入力がstuvwxyz、マスクが10101010なら出力は0000suwy、と いう具合
Rotated vs. Magic vs. pext • Rotated bitboardはテーブルが小さくて済む • Intel系ではpextが少し速い
• ZENアーキテクチャではpextはかなり遅い • 今はMagic bitboardが主流
ビットボードで将棋 • 9x9 = 81マスあるので64ビット整数1つでは管理できない • 分け方としては64マスと17マス、6段と3段、6段と6段(中3段 が重なる)などがある • Rotated
bitboardを使用しない場合は縦向きにした方が香車の 利きを求めやすくなる
まとめ • ボードゲームなどのAI開発には盤面処理の高速化が必要 • 高速化の手法の1つにビット配列がある • ビットボードは盤面をビット配列で管理することで高速に処理 する手法 • 魔法のアルゴリズムを使うと高速な計算ができる
• CPU命令に魂を売り渡すとさらに速くことがある(裏切られる こともある)
参考文献 • セル・オートマトン | Wikipedia https://ja.wikipedia.org/wiki/セル・オートマトン • オセロをビットボードで実装する | Qiita
https://qiita.com/sensuikan1973/items/459b3e11d91f3cb37e43 • ビットカウントする高速アルゴリズムをPythonで実装しながら 詳しく解説してみる | Qiita https://qiita.com/zawawahoge/items/8bbd4c2319e7f7746266 • やねうら王 http://yaneuraou.yaneu.com/