いつかRustでテトリスAIを作る 第1話 ～必要そうなパーツの実験編～
はじめに
対戦テトリスの世界では、もはや人間のトッププレイヤーでも絶対に太刀打ちできない強さのテトリスAIがいくつも知られています。
実際に戦ってみると、一瞬でそのAIの強さを体感できます。ボッコボコにされました。
僕の心を埋め尽くすのは、ひとえに作った人何者だよ、という気持ちでした。
一方で、ひょっとしたら僕でもめっちゃ強いテトリスAIを作れちゃうかもしれないじゃない？ という可能性も否定できません。
もし作れてしまったら僕も彼らと名を連ねることができて嬉しい。
もし全然ダメだったら、作者さんたちの凄さを強く体感できる。
どう転んでも勝ちだと確信したので、出発してみました。
ここから先色々とコードが出てきますが、全部書いてると大変なことになるので、 この記事で取り上げるコードの元ネタは、以下です 。（執筆当時のタグです。）
方針
Rust でやる！
最も有名なテトリスAIである（要出典） ColdClear は Rust で作られているようです。
自作に挫折したあと、このコードを読むことへの心理的障壁が少しでも減ると嬉しいなと思い、使用言語は Rust で決めうちです。
本音としては、Rust おもしろそうだしやっておきたい。それだけです。
OpenCV を使う！
メモリから情報を抜き出して演算するようなことも、不可能ではないかもしれません。しかし、それではあらゆるタイトルで使えるテトリスAIにはならなそうです。
どんなテトリスのタイトルでも、必ず情報は画面に出ます。
であれば、画面をテトリスAIの情報源にすることは当然で、素直に考えれば OpenCV を使うことが自然です。（ほんと？）
本音としては、OpenCV は有名だから触ってみたい。それだけです。
車輪の再発明を楽しむ！
もしテトリスに関する何らかのライブラリがあったとしても、使いません。
どれだけ効率が悪くても、テトリスについて考える時間、テトリスAIについて考える時間を楽しみます。
開始前の知識・スキル
- Rust：皆無
- OpenCV（ひいては画像処理）：皆無
- テトリス：2年弱やってた
- テトリスAI：ネタバレ回避のため実装は見てない
第一関門：盤面認識
とりあえず、最初から対戦でどう勝つかを考えてもしょうがないのでまずは テトリスAIの目 を作ります。
以下のような画面から情報を抜き出します。
（なにかあると怖いので、一応モザイクかけました。）
抜き出す必要がある情報は、以下2つです。
- 盤面のどこにブロックが存在している状態か
- 特定の領域を指定したとき、そこにどのテトリミノが表示されているか
※テトリミノとは、7種のテトリスブロックの呼称です。L,J,I,O,T,S,Z があります。いわゆる棒が Iミノです。
事前準備
実験なので、ヒューリスティック上等です。
情報を抜き出すべき盤面（20x10のフィールドのこと）の四隅の座標と、ネクストが表示されている部分（このゲームでは5コ）の四隅の座標を、ディスプレイサイズから割り出す係数を自力で計算しました。使ったツールは、PrintScreenキーとmspaintと電卓です。
pub struct PositionRatio {
pub lower_x_ratio: f32,
pub upper_x_ratio: f32,
pub lower_y_ratio: f32,
pub upper_y_ratio: f32
};
// 画面サイズをこの数値で割るとテトリス盤面の矩形の端を示す比率
pub const FIELD_RATIO: PositionRatio = PositionRatio {
lower_x_ratio: 6.2,
upper_x_ratio: 2.87,
lower_y_ratio: 6.75,
upper_y_ratio: 1.22
};
// 画面サイズをこの数値で割るとネクスト1〜5の領域の端を示す比率
pub const NEXT1_POS_RATIO: PositionRatio = PositionRatio {
lower_x_ratio: 2.75,
upper_x_ratio: 2.34,
lower_y_ratio: 6.35,
upper_y_ratio: 4.4
};
pub const NEXT2_POS_RATIO: PositionRatio = PositionRatio {
...
テトリスプレイヤーなら「おや？」と思ったかもしれませんが、ホールドされているミノは対象にしていません。
というのも、ホールドは恣意的に行うものであり、予測可能なものであるため、画像認識で再確認する必要はないからです。
また、この実験ではスクリーンショット撮影＋OpenCVによる画像認識をリアルタイムで行うことを考えています。
その部分に関する内容は、以前書いた記事で紹介しています。
盤面情報を推定する
ひとまず、盤面に関しては別に「どのテトリミノであるか」は興味の対象ではないので、ブロックの有無のみを割り出せれば（今のところ）問題なさそうな気がします。
であれば、割と HSV の V（明度）だけ見ればいけそうです。
// CELL_WIDTH, CELL_HEIGHT: マス数のこと。(10, 20)。
pub type FieldMatrix = [[CellState; CELL_HEIGHT]; CELL_WIDTH];
// original: 何のブロックも置かれてない状態のスクショの盤面部分を切り出した画像（事前に用意してある）
// image: 撮影したスクショから盤面部分を切り出した画像
// cell_size: 20x10 の盤面において、1マスの縦横それぞれのピクセル数
fn get_field_state(original: &Mat, image: &Mat, cell_size: &(usize, usize)) -> FieldMatrix {
let mut field: FieldMatrix = [[CellState::UNKNOWN; CELL_HEIGHT]; CELL_WIDTH];
// 背景差分を計算する。これによって可能な限りノイズを減らす。
let mut diff_rgb = Mat::default();
absdiff(original, image, &mut diff_rgb);
// 差分をHSVに変換する
let mut diff_hsv = Mat::default();
cvt_color(&diff_rgb, &mut diff_hsv,COLOR_BGR2HSV, diff_rgb.channels());
// 各マスごとに明度でブロックの有無を判定する
for y in 0..CELL_HEIGHT {
for x in 0..CELL_WIDTH {
let cell_hsv = Mat::roi(
&diff_hsv,
Rect_ { x: (x * cell_size.0) as i32, y: (y * cell_size.1) as i32, width: (cell_size.0) as i32, height: (cell_size.1) as i32 }
).unwrap();
// なんかこれをやるとデータが連続になってVectorに変換できるようになる
// TODO: 仕方ないことなのか、他のやり方があるのか調べる
let mut cell_c = Mat::default();
cell_hsv.convert_to(&mut cell_c, CV_8UC3, 1.0, 0.0);
// Vector に変換してHSVの平均値を計算する
let cell_data = cell_c.data_typed::<Vec3b>().unwrap();
let mean_hsv = mean_vec(cell_data);
// 明度が 100 以上であれば、そのマスにはブロックが存在している
if mean_hsv.2 >= 100 {
field[x][y] = CellState::EXIST;
} else {
field[x][y] = CellState::NONE;
};
}
}
return field;
}
fn mean_vec(vec: &[Vec3b]) -> (u8, u8, u8) {
let mut h: u32 = 0;
let mut s: u32 = 0;
let mut v: u32 = 0;
for elem in vec {
h = h + (elem[0] as u32);
s = s + (elem[1] as u32);
v = v + (elem[2] as u32);
}
h = h / (vec.len() as u32);
s = s / (vec.len() as u32);
v = v / (vec.len() as u32);
return (h as u8, s as u8, v as u8);
}
コードの内容にちょっとだけ触れてみます。
if mean_hsv.2 >= 100
ここが最大のヒューリスティック要素ですが、今のところこれでなんとかなりそうです。
なにげに、 ゴースト と呼ばれる、「今操作しているテトリミノを直落下させたとき、どこに落ちるかを示す半透明のやつ」の扱いが大変でしたが、半透明なだけにちょうどこのくらいの明度でスパッと切り捨てられそうな気配があります。
ちなみに、もちろん最初はRGB空間でなんとかしようと思いました。
が、各テトリミノについての閾値設定が必要になりかなり大変で精度も低いという問題があり、行き着いた先が明度での閾値処理でした。
少なくとも今のところ、テトリミノがある/ないを区別するための分散が最大になる軸は明度（であろう）、という予想がそこそこヒットしていそうです。
とりあえずは、「やり方がある」ことがわかれば十分で、あとからより良い方法に差し替えればいいので、第一関門の 盤面のどこにブロックが存在している状態か は突破したこととします。
特定領域に何のテトリミノがあるかを推定する
ネクスト1～5のテトリミノが何であるかは、戦術を立てるために厳密に推定する必要があります。
とすれば、上述したように明度でわかるのはブロックの有無のみなので、別なアプローチが必要になりそうです。
では、人間がテトリスをするときには、何を基準にテトリミノを判別しているんでしょうか？
…と考えてみると、「色」か「形」の二択になりそうです。
あくまで実験ですから、僕は色で判別してるので 色で判別するアプローチを実装してみます。
まずは、頑張ってそれぞれのテトリミノの代表値っぽいところを見つけた数値を用意します。
少なくとも、色を基準にする以上 色相が大事なはずで、Hの誤差はあまり許さず、SとVの誤差はある程度は許容するというポリシーで走り出しました。
// ミノの基準 HSV
pub struct MinoHSV {
pub kind: Mino,
pub h: u16,
pub s: u16,
pub v: u16
}
// 各ミノのHSVの代表値
pub const MINO_HSV_LIST: [MinoHSV; 7] = [
MinoHSV { kind: Mino::S, h: 100, s: 190, v: 180 },
MinoHSV { kind: Mino::Z, h: 0, s: 220, v: 130 },
MinoHSV { kind: Mino::L, h: 25, s: 250, v: 240 },
MinoHSV { kind: Mino::J, h: 210, s: 250, v: 170 },
MinoHSV { kind: Mino::I, h: 200, s: 240, v: 200 },
MinoHSV { kind: Mino::T, h: 290, s: 175, v: 150 },
MinoHSV { kind: Mino::O, h: 45, s: 215, v: 200 },
];
// 許容する HSV の誤差範囲
pub const ALLOW_H_GAP: u16 = 10;
pub const ALLOW_S_GAP: u16 = 50;
pub const ALLOW_V_GAP: u16 = 50;
推定のロジックは以下です。長くてすみません。
// ミノを判別する
// image は、ネクストであったりホールドであったり、何でもいいが、
// テトリミノだけが主に写り込んでいるような矩形を切り出した画像を想定している
fn estimate_block(image: &Mat) -> Mino {
// 大抵、黒・白・テトリミノの色 の 3クラスタに分かれそうという予想のもと
const CLUSTER_NUM: i32 = 3;
// HSVに変換する
let mut image_hsv = Mat::default();
cvt_color(image, &mut image_hsv, COLOR_BGR2HSV, image.channels());
let mut label = Mat::default();
let mut center = Mat::default();
let criteria = TermCriteria {
typ: 100,
max_count: 100,
epsilon: 0.5
};
let mut image_f = Mat::default();
image_hsv.convert_to(&mut image_f, CV_32F, 1.0, 0.0);
let image_reshaped = image_f.reshape(3, image_f.rows() * image_f.cols()).unwrap();
// kmeans クラスタリングが本当に正しい手法かというと疑問は残るが、
// やりたいことをの説明としては割と間違ってはいないのでこれを採用している
kmeans(
&image_reshaped,
CLUSTER_NUM,
&mut label,
criteria,
10,
KMEANS_RANDOM_CENTERS,
&mut center
);
// 0～360は少なくとも扱いたいので、16bitに変換
let mut center_u = Mat::default();
center.convert_to(&mut center_u, CV_16UC3, 1.0, 0.0);
// 候補値が3要素区切りで直列に並んだ配列 (h,s,v,h,s,v,h...)
let cands_serial = center_u.data_typed::<u16>().unwrap();
for i in 0..CLUSTER_NUM {
let first = (i * 3) as usize;
let candidate: MinoHSV = MinoHSV {
kind: Mino::UNKNOWN,
h: cands_serial[first]*2, // H値を0〜360にスケールする
s: cands_serial[first+1],
v: cands_serial[first+2]
};
// 盤面認識ロジックと逆で、明度が100未満であれば
// そもそもブロックがないはずなので無視する
if candidate.v <= 100 {
continue;
}
for mino in MINO_HSV_LIST{
// u16だと負の値になるかもしれないので対策しておく
let h_range = (std::cmp::max(ALLOW_H_GAP, mino.h) - ALLOW_H_GAP, mino.h + ALLOW_H_GAP);
let s_range = (std::cmp::max(ALLOW_S_GAP, mino.s) - ALLOW_S_GAP, mino.s + ALLOW_S_GAP);
let v_range = (std::cmp::max(ALLOW_V_GAP, mino.v) - ALLOW_V_GAP, mino.v + ALLOW_V_GAP);
if candidate.h >= h_range.0 && candidate.h <= h_range.1 {
if candidate.s >= s_range.0 && candidate.s <= s_range.1 {
if candidate.v >= v_range.0 && candidate.v <= v_range.1 {
return mino.kind
}
}
}
}
}
return Mino::UNKNOWN;
}
これについては、説明したいところも、ツッコミどころも多すぎるので、説明を割愛します。
ひとまず、割と信頼できる精度で推定ができていることは確認できました。
とりあえずは、「やり方がある」ことがわかれば十分で、あとからより良い方法に差し替えればいいので、 特定の領域を指定したとき、そこにどのテトリミノが表示されているか は突破したこととします。
第二関門：ゲームの操作
よく考えたら、テトリスAIを目指す以上、AIくんが操作を行えないと何の意味もないです。
つまり、 テトリスAIの手指 を作ります。
ひとまず、PCのゲームであることを前提とすれば、キーイベントさえ発行できればなんとかなるはずです。
ひとまず目についた enigo を使ってみることとしました。
こういった関数を用意しまして…
fn input_key(enigo: &mut Enigo, key: Key) {
enigo.key_down(key);
thread::sleep(Duration::from_millis(15));
enigo.key_up(key);
thread::sleep(Duration::from_millis(15));
}
pub fn move_right() {
let mut enigo = Enigo::new();
input_key(&mut enigo, Key::RightArrow);
input_key(&mut enigo, Key::RightArrow);
input_key(&mut enigo, Key::RightArrow);
input_key(&mut enigo, Key::RightArrow);
input_key(&mut enigo, Key::RightArrow);
input_key(&mut enigo, Key::Space);
}
pub fn move_left() {
let mut enigo = Enigo::new();
input_key(&mut enigo, Key::LeftArrow);
input_key(&mut enigo, Key::LeftArrow);
input_key(&mut enigo, Key::LeftArrow);
input_key(&mut enigo, Key::LeftArrow);
input_key(&mut enigo, Key::LeftArrow);
input_key(&mut enigo, Key::Space);
}
現在操作している（であろう）テトリミノの種類に応じて、とあるテトリミノであれば右端へ、とあるテトリミノであれば左端へ落とす…というような操作を適用してみます。
match current_mino {
Mino::I => {
move_right();
},
Mino::J => {
move_right();
},
Mino::L => {
move_left();
...
試してみた結果としては、ひとまず操作自体は狙った通りに行えました。
ですが、実は問題がありました。
今、 fn input_key() を見るとわかるように、キーを押下したとき～キーを離すまでと、キーを離してから次のキーを押下するまでの間 にそれぞれしばらくのスリープを入れています。
困ったことに、これをうまく調整しないとどうやらゲームがキー操作を検出できない速度でイベントが発行されてしまっていそうです。
そして、これのせいで 既存のテトリスAIとは比べ物にならないくらい遅いです 。
となると、これはアルゴリズム全体の見直しが必要そうです。
面白くなってきました。
付録: ゲーム中かどうかの判別をしないと大変だった話
今、作ってみているものを実行するときには毎回 cargo run --release をしています。
そうすると、テトリスがまだ画面に映ってもいないのに、 LeftArrow やらなにやらがこのプログラムから無限に高速で入力されて、僕のPC操作がままならなくなります。（実際、この間PCがフリーズしました。）
そのため、「今 テトリスのプレイ中である」 という判定がないといけないことに気が付きました。
これはのちのちしっかり考えないといけませんが、今は「ネクスト5コがすべて取得できていなければゲーム中ではない」（つまり、明らかに7種のテトリミノのうちいずれかに当てはまる色が画面の特定領域に表示されていなければ、それはテトリスのプレイ画面ではない）という判定をしています。
案外これでなんとかなってます。
第1話の振り返り
Rust, OpenCV のどちらも全く知見がなかったにしては、なんだかんだ遊べてるな。くらいが正直なところです。
少なくとも、目 と 手 が不可能ではないことを確かめられれば、一番おもしろい 脳 の部分にとりかかれるはずだ、という想定があり、今はそれが現実味を帯びてきました。
個人的に、「理論を最初に全部学んでから実践する」よりも、「実践したあとに理論を学んで修正していく」が好みなので、割と楽しめてます。
電車での移動中などに、"The Rust Programming Language 日本語版" を読んで、 「帰ったらあそこリファクタリングできるやんけ…！」 の昂りをしばしば楽しんでます。
次回予告
第2話を公開するときには、以下のものは達成しておきたいなと思っています。
- もうちょっとスマートな盤面認識/テトリミノ判別ロジック
- もうちょっと高速な操作
- 一人プレイで、テトリス（4列消し）を何回か打てるくらいの自動操作アルゴリズム
自分が「一段落したな」とおもったら、それも関係なく書こうと思いますが。
Discussion