毎回、Rustを使ってアルゴリズムを実装したり、ツールを作ったりしていますが、今回は、テーブルゲームのリバーシを作ってみましょう。negamax探索というアルゴリズムを実装することで、それなりに強いリバーシを実装してみましょう。
-
negamax探索を使ったリバーシを作ってみよう
Rustでリバーシを作るには？
Rustでリバーシを作る手順ですが、段階的に開発していくと完成まで到達しやすいです。ここでは、次の手順で作っていきたいと思います。
(1) ゲームデータの表現方法を考える
(2) 石の置ける位置を判定したり、石を反転する処理を作る
(3) 簡単なリバーシAIを作る - 局面の評価関数を作る
(4) negamax探索を使って、数手先まで先読みするAIに鍛える
この中で最も大切なのが、(1)でゲームデータをどのように表現するかを考えることです。ここでは、盤面を8×8の配列として表現しましょう。各マスは「空(0)」「黒(1)」「白(2)」の数値で管理します。
-
リバーシのデータをどのように表現するかが重要
ゲームデータが決まったら、次に、(2)で石の置ける場所を判定する処理を記述しましょう。各マスの周囲8方向を調べて、石を置ける場所（合法手）を判定します。それが「合法手生成」です。石を置いた時は、同じ方向に相手の石が続き、その先に自分の石がある場合だけ、間の石を反転するようにします。
そして、(3)リバーシのAIを作ります。最も簡単なAIでは、全ての合法手を試し、それぞれの局面を評価したり、ランダムに選択したりします。なお、局面の評価を行う評価関数では、石の数だけでなく、角の価値、角の隣の危険度、置ける手の多さを点数化すると、簡単なAIでもそれらしく戦えるようになります。
そして、(4)でもっとAIを強くするために、次の「negamax探索」を使って数手先まで読むようにします。
negamax探索とは？
negamax探索とは、単純に全ての手を探索するのではなく、相手の最善手を自分の最悪手とみなして、符号反転しながら最大値だけを選んでいくという探索方法です。次の図は、negamax関数を利用して、最善手を選択する方法を示したものです。
-
negamax探索のアルゴリズム
このアルゴリズムのポイントは、相手の手番のときに得られた評価値の符号を反転して利用する点にあります。そもそも、リバーシでは、自分に有利な局面は相手に不利な局面です。この性質を利用して、評価値を反転しながら探索するのです。たとえば、相手にとって良い局面（評価: 3）は、自分にとっては悪い局面（評価: -3）を意味するように計算します。この評価の反転を繰り返すことで、最終的な評価を調べます。
ニューラルネットワークは使わないの？
なお、過去の対戦データを用いて、ニューラルネットワークを訓練する方法でも、AIを作ることができますが、negamax探索だけでも、「十分強いリバーシAI」になります。しかも、ニューラルネットワークや深層学習を使う場合には、対戦データを集めたり、モデルを訓練したりと、とても多くの準備が必要になります。
今回は、negamax探索を実装するだけにしておいて、余力のある方は、negamax探索の部分を、置き換える形でニューラルネットワークのAIを実装すると良いでしょう。
「人間 vs 人間」 - ルールのみ実装したリバーシを作ろう
いきなり本格的なプログラムを作るよりも、まずは、人間同士で遊べる処理を作りましょう。その後AIを追加すると開発しやすくなります。ターミナルを起動して、以下のコマンドを実行しましょう。
cargo new human-vs-human
すると、以下のようなRustプロジェクトのひな形が作成されます。
human-vs-human/
├── Cargo.lock ... 依存ライブラリの記録などに使われる
├── Cargo.toml ... プロジェクト設定ファイル
└── src/ ... Rustのプログラムが配置されるフォルダ
└── main.rs ... Rustのメインプログラム
このsrc以下に必要なファイルを追加して、次のようなファイルを作成します。
├── src
├── board.rs ... 盤面を管理する関数を定義するモジュール
├── game.rs ... ゲームの進行や結果表示などを実装するモジュール
├── main.rs ... メイン処理
└── rules.rs ... ゲームのルールを定義するモジュール
実際の各ファイルは、こちらにアップロードしています。
以下は、ポイントとなる部分にフォーカスして紹介します。
最初に、リバーシの盤面を管理する「board.rs」というファイルを作成してみましょう。次のようなコードを記述します。
// file: board.rs --- 盤面の定義と関連関数をまとめたモジュール
pub const SIZE: usize = 8; // 盤面のサイズ (8x8)
// 石の状態を表す定数 --- (*1)
pub const EMPTY: u8 = 0;
pub const BLACK: u8 = 1;
pub const WHITE: u8 = 2;
// Boardは8x8の2次元配列とする --- (*2)
pub type Board = [[u8; SIZE]; SIZE];
pub fn new_board() -> Board {
// 8x8 を 0(空)で初期化し、中央4マスだけ配置する --- (*3)
let mut b = [[EMPTY; SIZE]; SIZE];
b[3][3] = WHITE;
b[3][4] = BLACK;
b[4][3] = BLACK;
b[4][4] = WHITE;
b
}
pub fn stone_name(player: u8) -> &'static str { // 石の名前を求める関数
if player == BLACK { "黒" } else { "白" }
}
pub fn count_stones(board: &Board, stone: u8) -> usize { // 石の数を数える関数
board.iter().flatten().filter(|&&v| v == stone).count()
}
pub fn print_board(board: &Board) { // 盤面を表示する関数 --- (*4)
// Excel風に列をA-H、行を1-8で表示する。
println!(" A B C D E F G H");
for (r, row) in board.iter().enumerate() {
print!("{:>2} ", r + 1);
for &cell in row {
let ch = match cell {
BLACK => 'B',
WHITE => 'W',
_ => '.',
};
print!("{} ", ch);
}
println!();
}
}
プログラムを確認しましょう。(＊1)では、石の状態を表す定数を定義します。石の状態は、EMPTY(空: 0番)、BLACK(黒: 1番)、WHITE(白: 2番)と数値で表します。(＊2)では、盤面を二次元配列変数で表すべくBoard型を定義します。そして、(＊3)では、盤面を初期化する関数を定義しました。(＊4)では、盤面をターミナルに出力する関数です。
次に、ゲームのルールを表現するモジュール「rules.rs」を作成しましょう。
// file: rules.rs --- リバーシのルールを実装するモジュール
use crate::board::{Board, EMPTY, SIZE};
use crate::game::opponent;
const DIRS: [(isize, isize); 8] = [ // 8方向を表す --- (*1)
(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1),
];
// 盤面の範囲内かどうかを判定する --- (*2)
fn in_range(r: isize, c: isize) -> bool {
(0..SIZE as isize).contains(&r) && (0..SIZE as isize).contains(&c)
}
// 1方向だけ調べて、反転できる相手石の座標を集める --- (*3)
fn flips_in_dir(board: &Board, row: usize, col: usize, dr: isize, dc: isize, p: u8) -> Vec<(usize, usize)> {
// 相手石をたどり、最後に自分の石で挟めたら反転対象として返す。
let mut r = row as isize + dr;
let mut c = col as isize + dc;
let mut tmp = Vec::new();
while in_range(r, c) {
let v = board[r as usize][c as usize];
if v == opponent(p) { tmp.push((r as usize, c as usize)); }
else if v == p { return if tmp.is_empty() { vec![] } else { tmp }; }
else { return vec![]; }
r += dr;
c += dc;
}
vec![]
}
// 8方向を調べて、着手時に反転される石をすべて返す --- (*4)
pub fn collect_flips(board: &Board, row: usize, col: usize, p: u8) -> Vec<(usize, usize)> {
if board[row][col] != EMPTY { return vec![]; }
let mut flips = Vec::new();
for (dr, dc) in DIRS {
flips.extend(flips_in_dir(board, row, col, dr, dc, p));
}
flips
}
// 現在のプレイヤーが置ける全座標を返す --- (*5)
pub fn valid_moves(board: &Board, p: u8) -> Vec<(usize, usize)> {
let mut moves = Vec::new();
for r in 0..SIZE {
for c in 0..SIZE {
if !collect_flips(board, r, c, p).is_empty() { moves.push((r, c)); }
}
}
moves
}
// 指定座標に着手し、反転を適用する。置けない場合はfalseを返す --- (*6)
pub fn apply_move(board: &mut Board, row: usize, col: usize, p: u8) -> bool {
let flips = collect_flips(board, row, col, p);
if flips.is_empty() { return false; }
board[row][col] = p;
for (r, c) in flips { board[r][c] = p; }
true
}
プログラムを確認しましょう。(＊1)の部分は、for文を使って八方向の座標を処理できるように、相対座標のタプル配列を用意します。これはゲームプログラミングでは、よく使われる手法で、(＊4)で実際に八方向を処理するようにしています。(＊2)の関数in_rangeでは、行rと列cを与えて、盤面の範囲内かどうかを調べます。
(＊3)の関数flip_in_dirは、引数dr, dcで指定する方向に対して、反転できる相手石の座標を集めます。(＊4)の関数collect_flipsが、八方向全部の座標を集めます。(＊5)はプレイヤーが置ける全座標を集める関数です。
ほかにも、「game.rs」「main.rs」ファイルを作成しますが、詳しくは、GitHubのリポジトリを確認してみてください。
リバーシを実行してみよう
プログラムをコンパイルして実行するには、ターミナルを起動して、以下のコマンドを実行します。
cd human-vs-human
cargo run
コマンドを実行すると、人間vs人間のリバーシが実行できます。Excelなどの表計算ソフトと同じように、列をアルファベット、行を数値、C2とかF4のように座標を表現します。それで、配置可能な座標が表示されますので、交互に石を置きたい座標を入力します。
-
人間vs人間のリバーシを実行したところ
AIとの対戦型シンプルなリバーシを作ろう
続いて、人間とAIが戦うシンプルなリバーシを作っていきましょう。
その仕組みですが、多くの方が知っているように、リバーシでは、四隅を取ることができれば勝ちやすく、四隅のすぐ隣にはなるだけ置かないようにするのも重要です。このように、配置場所によるポイント制を導入することで、AIがそれなりの実力を発揮できるようになります。
まずはプロジェクトを作成します。
cargo new human-vs-ai
そして、先ほど「human-vs-human」で作成したファイル一式をコピーします。
なお、プログラムは、こちらにアップロードしています。
ここでは、ポイントとなるAIの思考処理を行うファイル「ai.rs」を確認してみましょう。
// file: ai.rs --- 評価関数ベースのシンプルAIモジュール
use crate::board::{Board, BLACK, WHITE};
use crate::rules::{apply_move, valid_moves};
// 盤面の重みを定義、四隅を高得点に設定 --- (*1)
const W: [[i32; 8]; 8] = [
[30,-12, 0,-1,-1, 0,-12,30],
[-12,-15,-3,-3,-3,-3,-15,-12],
[0, -3, 0,-1,-1, 0, -3, 0],
[-1,-3, -1,-1,-1,-1, -3,-1],
[-1,-3, -1,-1,-1,-1, -3,-1],
[0, -3, 0,-1,-1, 0, -3, 0],
[-12,-15,-3,-3,-3,-3,-15,-12],
[30,-12, 0,-1,-1, 0,-12,30],
];
// 局面の重み付き合計を計算する --- (*2)
fn positional_score(board: &Board, me: u8) -> i32 {
let opp = if me == BLACK { WHITE } else { BLACK };
let mut s = 0;
for r in 0..8 {
for c in 0..8 {
if board[r][c] == me { s += W[r][c]; }
if board[r][c] == opp { s -= W[r][c]; }
}
}
s
}
// 重みと合法手数を使って局面を評価する --- (*3)
pub fn evaluate(board: &Board, me: u8) -> i32 {
let mobility = valid_moves(board, me).len() as i32;
let opp = if me == BLACK { WHITE } else { BLACK };
let opp_mobility = valid_moves(board, opp).len() as i32;
positional_score(board, me) + (mobility - opp_mobility) * 2
}
// 1手先を読んで最も評価値が高い手を返す --- (*4)
pub fn choose_move(board: &Board, ai: u8) -> Option<(usize, usize)> {
let moves = valid_moves(board, ai);
let mut best: Option<(usize, usize, i32)> = None;
for (r, c) in moves {
let mut b = *board;
apply_move(&mut b, r, c, ai);
let score = evaluate(&b, ai);
if best.is_none() || score > best.unwrap().2 { best = Some((r, c, score)); }
}
best.map(|(r, c, _)| (r, c))
}
プログラムを確認しましょう。(＊1)では、盤面の重みを定義します。ここでは、-15から30までの点数を定義します。(＊2)では盤面の重みの合計を評価する関数positional_scoreを定義します。(＊3)では重みと合法手数を使って局面を評価します。(＊4)では、1手先だけを読んで最も評価が高い手を返す関数choose_moveを定義します。
プログラムを実行するには、ターミナルで下記のコマンドを実行します。
cd human-vs-ai
cargo run
実行すると、下記のように対戦ができます。ここで作成したAIは、盤面評価を元にしており、1手先しか見ていないので弱いです。
-
AIとの対戦ができるゲーム
もしかすると、油断して適当に石を配置していると苦戦することがあるかもですが、少し本気を出して勝負したら、まず負けないことでしょう。
-
真剣に相手すると弱いことが分かる
negamax探索を使ったAIを実装しよう
それでは、negamax探索を使ったリバーシAIを作ってみましょう。ターミナルで下記のコマンドを実行してプロジェクトを作ってみましょう。
cargo new negamax-ai
そして、先ほど作ったプログラムをそのままコピーします。なお、完成したプログラム全体は、こちらにアップロードしています。
そして、ファイル「ai.rs」を次のように記述します。
// file: ai.rs --- negamax探索でAIの着手を選ぶモジュール
use crate::board::Board;
use crate::rules::{apply_move, valid_moves};
use crate::game::opponent;
// 探索深さ(大きいほど強いが遅くなる) --- (*1)
const DEPTH: usize = 4;
// 盤面の位置ごとの重みを指定 --- (*2)
const W: [[i32; 8]; 8] = [
[30, -12, 0, -1, -1, 0, -12, 30],
[-12, -15, -3, -3, -3, -3, -15, -12],
[0, -3, 0, -1, -1, 0, -3, 0],
[-1, -3, -1, -1, -1, -1, -3, -1],
[-1, -3, -1, -1, -1, -1, -3, -1],
[0, -3, 0, -1, -1, 0, -3, 0],
[-12, -15, -3, -3, -3, -3, -15, -12],
[30, -12, 0, -1, -1, 0, -12, 30],
];
// 静的評価値(位置 + 合法手数差)を返す --- (*3)
fn evaluate(board: &Board, me: u8) -> i32 {
let opp = opponent(me);
let mut s = 0;
for r in 0..8 {
for c in 0..8 {
if board[r][c] == me { s += W[r][c]; }
if board[r][c] == opp { s -= W[r][c]; }
}
}
let my_mob = valid_moves(board, me).len() as i32;
let op_mob = valid_moves(board, opp).len() as i32;
s + (my_mob - op_mob) * 2
}
// negamaxで現在手番の最善評価を返す --- (*4)
fn negamax(board: &Board, turn: u8, depth: usize, root: u8) -> i32 {
// 現手番と相手の合法手を先に作って、終端判定やパス判定に使う --- (*5)
let my_moves = valid_moves(board, turn); // 自分の合法手
let op = opponent(turn); //
let op_moves = valid_moves(board, op);
// これ以上読まない深さ、または両者とも打てない終局なら静的評価を返す --- (*6)
if depth == 0 || (my_moves.is_empty() && op_moves.is_empty()) {
return evaluate(board, root);
}
// 自分だけ打てないときはパスして、手番を交代して評価の符号を反転する --- (*7)
// negamaxでは「相手の最善 = 自分から見た最悪」なので -1 を掛ける
if my_moves.is_empty() { return -negamax(board, op, depth - 1, root); }
// 全合法手を試して、最も評価値が高いものを採用する --- (*8)
let mut best = i32::MIN / 2;
for (r, c) in my_moves {
// 盤面をコピーして再帰的に評価を得る(視点交代のため評価反転) --- (*9)
let mut b = *board; // 盤面をコピー
apply_move(&mut b, r, c, turn); // 1手先の局面を作る
let score = -negamax(&b, op, depth - 1, root);
// 現手番から見て最大の評価値を採用 --- (*10)
if score > best { best = score; }
}
best
}
// 全合法手を探索し、最も評価が高い手を返す --- (*11)
pub fn choose_move(board: &Board, ai: u8) -> Option<(usize, usize)> {
let mut best = None;
let mut best_score = i32::MIN / 2;
let op = opponent(ai);
for (r, c) in valid_moves(board, ai) {
let mut b = *board;
apply_move(&mut b, r, c, ai);
let score = -negamax(&b, op, DEPTH - 1, ai);
if score > best_score {
best_score = score;
best = Some((r, c));
}
}
best
}
プログラムを確認しましょう。
(＊1)では、探索の深さを定数として決めています。ここで深さ(定数: DEPTH)を4にしているのは、「何手先まで読むか」を表しています。数字を大きくすると、AIはより先の展開まで考えられるので強くなりやすいですが、そのぶん計算量が増えて遅くなります。逆に小さくすると応答は速くなりますが、浅い読みしかできないため、目先の有利さだけで判断しやすくなります。この値はAIの強さと速度のバランスを決める、とても大事な設定です。そして、(＊2)の定数Wは、盤面の各マスに対して重みを与えています。
(＊3)では、盤面を静的に評価する関数evaluateを定義します。「静的評価」というのは、これ以上先を読まないで、その局面そのものに点数をつける考え方です。ここではまず、自分の石がある場所の重みを足し、相手の石がある場所の重みを引くことで、位置の有利不利を点数にしています。さらに、自分が打てる合法手の数と相手が打てる合法手の数を比べ、その差にも点数をつけています。これは「動ける手が多いほうが有利」という考え方にもとづいています。リバーシでは、打てる場所が多いことは次の選択肢の広さにつながります。この関数は、探索の末端で「この盤面はどれくらい良いか」を判断する土台になっています。
(＊4)では、関数negamaxを定義します。次の図は、この関数をシンプルにした処理を表しています。これは、先ほど解説したように、「相手にとって最善の手は自分にとって最悪の手になる」という性質を利用したものです。本来は自分番と相手番で別々に考えたくなりますが、negamax では「評価値の符号を反転する」だけで同じ形の処理にまとめられます。再帰処理でコードを比較的すっきり書けるのが利点です。この関数は、この局面から見て現在の手番側がどれだけ良い状態に持ち込めるかを数値で返します。
-
関数negamaxの動作を図にしたもの
それでは、関数negamaxの詳しい処理を確認しましょう。(＊5)では、今の手番の合法手と、相手の合法手を先に調べます。これはこのあとで行う終局判定やパス判定のために必要です。(＊6)では、探索を止める条件を判定しています。再帰可能な深さを表す引数depthが0になったときは、これ以上先を読まず、その場で評価関数を使って点数を返します。また、自分も相手もどちらも合法手がない場合は終局なので、そのときも評価を返します。探索では、どこかで必ず打ち切って点数化しないと再帰が終わりません。その役目をここが担っています。つまりこの部分は、再帰探索の「出口」を作っている重要な箇所です。そして、(＊7)では、自分だけ合法手がないときのパス処理をしています。
(＊8)では、現在打てるすべての合法手を順番に試し、その中で最も評価の高いものを探しています。ゲームAIでは、「候補を全部試して一番良いものを選ぶ」というのが基本の形です。ここで best をかなり小さい値で初期化しているのは、どんな評価値が来ても最初の比較で更新できるようにするためです。この部分が、実際に「どの手が良いか」を比較する中心になっています。
(＊9)では、ある候補手を実際に盤面へ適用して1手進んだ局面を作っています。そのあと、相手番として再帰的に探索し、その結果にマイナスをつけて、評価値を計算します。ここで盤面をコピーしているのは、元の盤面を壊さずに各候補手を独立して試すためです。再帰の結果にマイナスをつけるのは、ここでも negamax の「視点の切り替え」を表しています。この一連の処理で、「この手を打った先に相手が最善を尽くしたらどうなるか」を調べています。
(＊10)では、試した候補手の中で最も高い評価値を採用しています。(＊11)では、AIが実際に着手を選ぶ公開関数になっています。この関数は、今打てるすべての合法手を試し、それぞれについて negamax で先読みして、その中で最も評価の高い手を返します。
作成したプログラムを実行するには、ターミナルで以下のコマンドを実行します。
cd negamax-ai
cargo run
すると、次のように、negamax探索を実装したAIと勝負できます。
-
negamax探索を実装したAIと勝負しているところ
Webアプリにしてみよう
とはいえ、やはりターミナル上でゲームを遊ぶのは、それほど快適とは言えません。そこで、ここまで作ったアルゴリズムを利用して、Webアプリにしてみましょう。Rustの良いところは、手軽にWebAssemblyにコンパイルできるところにあります。とは言え、既に長くなってしまったので、Webアプリ化の方法は、また別の機会に紹介します。
-
ブラウザに移植したもの
今回は、こちらにソースコードをアップロードしていますので、そちらを参考にしてください。
Windowsの場合
# ZIPファイルの取得と展開
Invoke-WebRequest `
-Uri "https://raw.githubusercontent.com/kujirahand/mynavi-samples/main/2026/rust-reversi/web-app.zip" `
-OutFile "web-app.zip"
Expand-Archive web-app.zip -DestinationPath . -Force
cd web-app
# wasm-packのインストールとコンパイル
cargo install wasm-pack
wasm-pack build --target web --out-dir pkg
mv pkg public/pkg
# サーバーを実行
cargo run
macOS/Linuxの場合
# ZIPアーカイブ取得して解凍
curl -L -o web-app.zip https://raw.githubusercontent.com/kujirahand/mynavi-samples/main/2026/rust-reversi/web-app.zip
unzip web-app.zip
cd web-app
# wasm-packのインストールとコンパイル
cargo install wasm-pack
wasm-pack build --target web --out-dir pkg
mv pkg public/pkg
# サーバーを実行
cargo run
こちらのリンクからリバーシが遊べるようにしてみました。
まとめ
今回は、Rustでnegamax探索を実装してリバーシを作ってみました。negamax探索は、相手の最善手を自分の最悪手とみなして、符号反転しながら最大値だけを選んでいくという探索方法です。これを実装することで、数手先まで読むことができる強いAIを作ることができます。
なお、negamax探索をさらに発展させて、より強いリバーシAIを作るには、探索を効率化する工夫や、盤面をより正確に評価する工夫が大切です。たとえば、枝刈りを取り入れると、勝敗に関係しない手順を途中で打ち切ることができるので、より深く先読みできるようになります。また、評価関数に石の位置だけでなく、合法手の多さや確定石の数、終盤での石数なども取り入れると、局面に応じてより賢く判断できるようになります。ぜひ、改良してみてください。
ちなみに、最後に概要だけ紹介した「web-app」プロジェクトでは、ファイル「src/ai.rs」の評価関数を少し修正し、枝刈りの処理を入れた上で再帰回数を増やして6手先まで読むようにしました。それだけで、AIがかなり強くなりました。参考にしてみてください。
自由型プログラマー。くじらはんどにて、プログラミングの楽しさを伝える活動をしている。代表作に、日本語プログラミング言語「なでしこ」 、テキスト音楽「サクラ」など。2001年オンラインソフト大賞入賞、2004年度未踏ユース スーパークリエータ認定、2010年 OSS貢献者章受賞。これまで50冊以上の技術書を執筆した。直近では、「大規模言語モデルを使いこなすためのプロンプトエンジニアリングの教科書(マイナビ出版)」「Pythonでつくるデスクトップアプリ(ソシム)」「実践力を身につける Pythonの教科書 第2版」「シゴトがはかどる Python自動処理の教科書(マイナビ出版)」など。
Windows PCの『セキュアブート』証明書が2026年6月に期限切れ、更新状況の確認を
