
2026/03/25 9:27
**FETとクロス:2458個のディスクリート・トランジスタで作るティックタックトー**
RSS: https://news.ycombinator.com/rss
要約▶
Japanese Translation:
この記事は、離散トランジスタと論理ゲートのみを使用して完全に勝利できる手作りのTic‑Tac‑Toeエンジンを記録しています。設計は2458個のトランジスタと19個のフリップフロップから始まり、そのうち約1074個が、初期の18ビットROMルックアップテーブルを純粋に組み合わせ式NOR/NANDゲートで置き換えた後の意思決定論理に割り当てられています。CMOSで構築すると、総トランジスタ数は約2000個になります。
意思決定木は、勝利、ブロック、フォーク防止、中央、コーナー、サイドムーブ(9 + 9 + 6 + 9 + 9 + 6 + 3 + 1 + 4 + 4 + 4)をカバーする64個の「意思決定ゲート」から構成されています。各ゲートは入力反転を用いたNOR/NANDロジックを使用し、トランジスタ使用量を最小化します。
ワークフローは、KiCadで基本セルライブラリ(NOT、NAND)を作成し、次により複雑なゲートを構築してから完全な回路を組み立てることから始まりました。2枚の別々のPCBが製造されました:UI、電源規制、555タイマークロック、およびロジックを収容するメインボードと、トランジスタベースのコアを含むエンジンボードです。手作業で組み立てる際に、ワープ修正のために3回のリビジョンが必要となり、信頼性確保のために5枚の最終ボードが製造されました。
小型STM32テストベンチはPythonスクリプトを実行し、すべての可能なゲームをプレイしてエンジンが決して負けないことを確認しました。プロジェクトの目的はデモンストレーションであり、最適化ではありません;より効率的な設計も認められていますが追求されません。この作業は低レベルハードウェア設計の教育展示として機能し、基本ロジックだけで単純なゲームを解決できることを示し、ホビイストプロジェクトに刺激を与えます。
本文
概要と特徴
本プロジェクトは、2 458 個の個別トランジスタだけで構成されたクラシックな「井字ゲーム(Tic‑Tac‑Toe / Noughts and Crosses)」を実装したものです。
シミュレーション/設計
“デジタルデザイン”の講義中に、プレイヤー対プレイヤーとプレイヤー対コンピュータの両モードを備えた井字ゲームのグラフィカルロジックシミュレータモデルを作成しました。
エンジンはもともと並列入出力ROM(ルックアップテーブル)を用いており、18 ビットのボード状態をアドレスとして ROM にアクセスし、メモリから動きを読み取っていました。
機能的には問題ありませんでしたが、この手法は極めて非効率であり、すべての入力のうち 5 % 未満しか有効なゲーム状態に該当していませんでした。
そこで完全に組合せ論的ロジックゲートモジュールへ置き換え、さらに「完璧なプレイ」を保証するようにしました。
LOGISIM におけるシミュレーション
高レベルブロック図
ハードウェア実装
最終回路は、ボード状態を表す 18 個のフリップフロップと現在プレイ中のプレイヤーを追跡する 1 個のフリップフロップ、および数個の基本ゲートだけで構成されます。
CMOS 実装時のトランジスタ数は約 2 000 個と推定されています。
設計フロー
- 基本セル – KiCad で設計。各セルは独自の階層スキマティックシートに配置。
- 例:NOT ゲート(図示とシンボル)。
- 複合ゲート – 基本セルを組み合わせて構築(例:NAND + NOT で作る 2 入力 AND)。
- ロジック再描画 – 個々のコンポーネントではなく、階層シートを用いて全ロジックを KiCad 内に再現。
- レイアウト – 各基本セルは一度だけ配線し、その後「レイアウト複製」プラグイン(KiCad 2 通道以前)で全インスタンスに適用。
- 組み立て – 手作業で 2 層 PCB のマンハッタン配線を実施:
- メインボード:ユーザーインターフェース、電源制御、555 タイマークロック、およびエンジン以外の全ロジック。
- エンジンボード:トランジスタベースのエンジン(またはフラッシュメモリ代替版)。
組み立て
手作業で板を組み立てました。すべてが信頼性を持って動くようになるまでに 3 回のリビジョンが必要でした。
部品配置を高速化するため、リールから直接部品を移動させる真空ピックアンドプレースペンを作成しました。
1 分間のタイムラプス動画(映像は省略)も公開しています。
注意 – 手作業でのはんだ付けにより板が大きく歪みました。3 回のリビジョンと 5 台のプロフェッショナル組立後、板は張力下でも破損しなくなりました。
プレイデモ
短い動画でプレイヤー対プレイヤーとプレイヤー対コンピュータの両方を実演しています。
(映像省略)
エンジン
井字ゲームはシンプルであるため、完璧なプレイは一連の決定ゲートとして符号化できます。各ゲートは特定の勝利またはブロック条件をチェックし、トリガーされると以降のすべてのゲートを停止します。
決定ゲート例(上段の勝ち)
if (b[top][left] == "us" && b[top][middle] == "us" && b[top][right] == "empty") { play(top, right); }
ハードウェア等価は、入力条件が真となったときに活性化する単一の決定ゲートです。
CMOS では NOR/NAND を用いた論理反転がトランジスタ数を減らすため、ゲートへの入力は反転されます。
決定ゲートシーケンス
| 条件 | ゲート数 |
|---|---|
| 行を完成して勝つ | 9 |
| 列を完成して勝つ | 9 |
| 対角線を完成して勝つ | 6 |
| 相手の一歩先の勝ち(行)をブロック | 9 |
| 相手の一歩先の勝ち(列)をブロック | 9 |
| 相手の一歩先の勝ち(対角線)をブロック | 6 |
| フォークを防止 | 3 |
| 中央が空ならプレイ | 1 |
| 相手が隅にいて反対側の隅が空 | 4 |
| 空き隅 | 4 |
| 空き辺/上部/下部 | 4 |
合計 64 の決定ゲートと、状態反転・プレイ出力の OR 合成を行うサポートロジックで構成されます。
完全なエンジンは 1 074 トランジスタ を使用し、完全に組合せ論的な完璧プレイエンジンとなります。
エンジンのテスト
小型 STM32 テストベンチを用いてエンジンと PC を接続。Python スクリプトですべての可能な井字ゲームをエンジンに対してプレイし、決して負けないことを確認しました。
備考
効率化は優先事項ではありませんでした。フリップフロップ設計や複合ゲートの最適化によってトランジスタ数をさらに削減できる可能性がありますが、本プロジェクトは個別トランジスタのみで構成された完全機能の井字ゲーム完璧プレイエンジンを示すものです。
リンク
- 📁 リポジトリ
- 📝 LOGISIM ファイル
- 📃 メインボード BOM(対話型)
- 📃 エンジン BOM(対話型)
- 📃 エンジントスター・テスター BOM(対話型)
- 📦 製造ファイル(スキマティック、Gerbers)