ビット演算できる型を使って、○×ゲームで遊べるようにしてみた

こんにちは、エンジニアの籏野です。

先日、とある開発中の思い付きでTypeScriptの型でビット演算ができるようにしてみました。
残念ながらその型はアプリで採用されることはなかったのですが、何かしらに活かしてみたいなと思い、TypeScriptの型レベルプログラミングだけで○×ゲームを作ってみました。

今回の型を作ろうとしたきっかけは、ある選択肢の中からいくつか選び出す際に、選び取った組み合わせと選んだもの以外の組み合わせが同じ状態を示すというルールがあったためです。
例: 1~5の選択肢がある場合に、「1, 3」と「2, 4, 5」は同じ状態を示すことを型で表現する

ビット演算できる型を使えばこのルールを型安全に表現できるかもと考え試してみました。
実際にはここまで複雑な手法を取らずとも十分と判断したので採用は見送っています。

ビット演算と○×ゲーム

まずビット演算を使ってどのように○×ゲームを行うのかを説明します。
○×ゲームは3×3のマスに対して2人のプレイヤーが交互に○と×を置いていき、先に3つ並べた方が勝ちというゲームです。
3×3のマスに対して以下のように番号を振ってみると、○×が置かれたかどうかをそれぞれビット配列で表すことができます。

今回実装した型は「0 or 1の配列」で表現しています。
そのため、ビットの位置は0始まりで数えており、ビット表記も先頭から0ビット目、1ビット目...となっている点に注意してください。

例: 0b001 -> 100 と表記されます

例えば以下のような盤面の場合、○×それぞれの置き場所は以下のように表現されます。

• ○: 010010000
• ×: 100000000

ではビット演算を用いて、盤面の状態を取得したり次の状態に遷移させたりしていきましょう。

まず、盤面全体でマークが置かれた場所を取得するには、○×それぞれのビット配列の論理和を取ればよいです

• ○(010010000) OR ×(100000000) = 盤面全体(110010000)

次のターンのプレイヤーがマークを置ける場所は盤面全体のビット配列の否定を取ります。

• NOT 盤面全体(110010000) = マークを置ける場所(001101111)

次のターンに新たなマークを置いた場合は、現在の置き場所を表すビット配列に対して、置きたい場所にビットが立った配列の論理和を取ればよいです。

• ×(100000000) OR 7番に置く(000000010) = 次のターンの盤面(1000000010)

これで盤面は以下のようになりました。

これらの操作を繰り返すことで、ゲームが進行していきます。

TypeScriptの型でビット演算

1ビットに対するビット演算の実装

まずは1ビットに対するビット演算を実装していきます。

// ビット定義
type Bit = 0 | 1;

// ビット論理和
type Or<L extends Bit, R extends Bit> = `${L}${R}` extends `00` ? 0 : 1;

// ビット論理積
type And<L extends Bit, R extends Bit> = `${L}${R}` extends `11` ? 1 : 0;

// ビット否定
type Not<T extends Bit> = {
	0: 1;
	1: 0;
}[T];

シンプルですね。
ではこれを用いてビット配列に対する演算として実装します。

以下のような実装も考えられましたが、1 & 0のようなneverになる場合にもtrueと同じ分岐にはいってしまうため今回のような実装になっています。

type And<L extends Bit, R extends Bit> = L & R extends 1 ? 1 : 0

ビット配列に対する操作の実装

配列内の各要素に対するビット演算は再帰的に実装ができます。
例えばビット配列の論理和を取る型は以下のようになります。

// ビット配列の論理和を取得する
type BitTupleOr<
	L extends Bit[],
	R extends Bit[],
> = L["length"] extends R["length"]
	? ComputeBitOr<L["length"], L, R, []>
	: never;
type ComputeBitOr<
	Length extends number,
	L extends Bit[],
	R extends Bit[],
	Result extends Bit[],
> = Result["length"] extends Length
	? Result
	: ComputeBitOr<
			Length,
			L,
			R,
			[...Result, Or<L[Result["length"]], R[Result["length"]]>]
		>;

空の配列を用意し、先頭から順に渡されたビット配列の中身を参照して論理和を取っています。
ANDやNOTも同様に実装できるのでここでは省略します。

ゲームを進行させる型を実装

ゲームの状態を表すには以下の要素が必要です。

• ○の置き場所
• ×の置き場所
• 次のターンのプレイヤー

これを型で表現すると以下の通りです

type Playboard = {
	player1: Bit[];
	player2: Bit[];
	nextPlayer: Player;
};

上記の型を基本とし、次のターンのプレイヤーが置き場所を指定すると、対応するビット配列に対して論理和を取って盤面を進行させます。
その型は以下のように実装されます。

// ※BitTupleは任意のインデックスにビットを立てる型
type Play<CurrentPlayboard extends Playboard, Next extends number> = {
	player1: CurrentPlayboard["nextPlayer"] extends Player1
		? BitTupleOr<CurrentPlayboard["player1"], BitTuple<9, Next>>
		: CurrentPlayboard["player1"];
	player2: CurrentPlayboard["nextPlayer"] extends Player2
		? BitTupleOr<CurrentPlayboard["player2"], BitTuple<9, Next>>
		: CurrentPlayboard["player2"];
	nextPlayer: ChangePlayer<CurrentPlayboard["nextPlayer"]>;
};

この型のテストコードを書いてみると盤面が進行したことが分かるかと思います。

test("盤面を進める", () => {
	type InitialPlayboard = {
		player1: [0, 0, 0, 0, 0, 0, 0, 0, 0];
		player2: [0, 0, 0, 0, 0, 0, 0, 0, 0];
		nextPlayer: "P1";
	};
	expectTypeOf<Play<InitialPlayboard, 0>>().toEqualTypeOf<{
		player1: [1, 0, 0, 0, 0, 0, 0, 0, 0];
		player2: [0, 0, 0, 0, 0, 0, 0, 0, 0];
		nextPlayer: "P2";
	}>();
});

ゲームの勝敗を判定する型を実装

勝敗の判定方法はいくつか考えられますが、ビット演算にこだわって以下のようにします。

• 現在の盤面と勝利条件を満たすビット配列(8パターン)の論理積を取る
• その結果が勝利条件を満たすビット配列と一致するかどうかで勝利を判定する

実装は以下の通りです

// ※Mark0 ~ Mark8は番号の位置のみにビットが立った配列を表します。
type WinnerCondition = [
	// 横一列
	BitTupleOr<BitTupleOr<Mark0, Mark1>, Mark2>,
	BitTupleOr<BitTupleOr<Mark3, Mark4>, Mark5>,
	BitTupleOr<BitTupleOr<Mark6, Mark7>, Mark8>,
	// 縦一列
	BitTupleOr<BitTupleOr<Mark0, Mark3>, Mark6>,
	BitTupleOr<BitTupleOr<Mark1, Mark4>, Mark7>,
	BitTupleOr<BitTupleOr<Mark2, Mark5>, Mark8>,
	// 斜め一列
	BitTupleOr<BitTupleOr<Mark0, Mark4>, Mark8>,
	BitTupleOr<BitTupleOr<Mark2, Mark4>, Mark6>,
];

type IsWin<T extends Bit[]> = ComputeIsWin<T, []>;
type ComputeIsWin<
	T extends Bit[],
	Current extends number[],
> = Current["length"] extends WinnerCondition["length"]
	? false
	: BitTupleAnd<
				T,
				WinnerCondition[Current["length"]]
			> extends WinnerCondition[Current["length"]]
		? true
		: ComputeIsWin<T, [...Current, 0]>;

○×ゲーム本体を実装する

これまで作成した型を使って○×ゲームを行う型TicTacToeを実装しました。
勝利までの流れをテストしてみると以下のようになります。

test("○×ゲームで遊ぶ", () => {
	type P1 = TicTacToe<0>;
	expectTypeOf<FormatPlayboard<P1>>().toEqualTypeOf<"O-- / --- / ---">();
	type P2 = TicTacToe<1, P1>;
	expectTypeOf<FormatPlayboard<P2>>().toEqualTypeOf<"OX- / --- / ---">();
	type P3 = TicTacToe<3, P2>;
	expectTypeOf<FormatPlayboard<P3>>().toEqualTypeOf<"OX- / O-- / ---">();
	type P4 = TicTacToe<4, P3>;
	expectTypeOf<FormatPlayboard<P4>>().toEqualTypeOf<"OX- / OX- / ---">();
	type P5 = TicTacToe<6, P4>;
	expectTypeOf<P5>().toEqualTypeOf<"Winner is Player1!">();
});

現在の盤面を描画する型も作ってみましたが分かりづらいですね。。
最終的な盤面は以下のようになってます。

また、既に○×が置かれたマスに置こうとすると怒られます。

test("○×ゲームで遊ぶ - 既に埋まっているマスに置こうとした場合", () => {
	type P1 = TicTacToe<0>;
	expectTypeOf<FormatPlayboard<P1>>().toEqualTypeOf<"O-- / --- / ---">();
	type P2 = TicTacToe<0, P1>;
	expectTypeOf<P2>().toEqualTypeOf<"Hey! Player2!! Invalid Move!">();
});

まとめ

この記事で作成した○×ゲームは以下のリポジトリに置いていますので、詳細な実装が気になる方はご覧ください。

https://github.com/taku-hatano/tic-tac-toe-type

今回の実装を活かして以下のように実際の○×ゲームのように遊ぶこともできます。

test("TicTacToe - Visualize Mode", () => {
	expectTypeOf<
		TicTacToeView<[
			"X", "X", "-",
			"O", "O", "O",
			"-", "-", "-"
		]>
	>().toEqualTypeOf<"Winner is Player1!">();
});

TypeScriptの型は非常に強力な表現力を持っていることが今回改めて分かりました。
弊社の過去のブログでは「TypeScriptの型レベルプログラミングで数独を解く」という記事もありますので、興味がある方はぜひご覧ください。
https://zenn.dev/forcia_tech/articles/20211221_advent_calendar

TypeScriptの型レベルプログラミングは非常に面白いので、ぜひ皆さんも試してみてください。

この記事を書いた人

籏野 拓
2018年新卒入社。

最後に

フォルシアはTSKaigi 2025およびzenn記事投稿コンテスト「TypeScriptでやってみた挑戦・学び・工夫」のスポンサーを務めています。
今後もTypeScriptに関する記事を投稿していきますので、ぜひご覧ください！