自作PCBオートルータをトーナメントにしたら、最強が盤ごとに入れ替わった — Python で arena をつくる

まとめ（先に結論）

• 前回、KiCad を使わず Python だけで PCB を描いて、自作の素朴な配線プログラム（A* で経路を探す迷路法）で 22 本ぜんぶ通せた、という記事を書きました。次回予告は「賢いやり方を入れたらどう変わるか」「詰め込んだらどこで破綻するか」でした
• 今回はその続きで、5 つの戦略を同じ問題で勝敗を競わせる「router-arena」というベンチを作りました。配線率・DRC 違反・ビア・配線長・時間で順位がつくリーダーボード方式です（DRC＝Design Rule Check は、線幅やすき間など「製造可能か」の規約チェックのことです）
• 正直なところを先に書いておくと、今回の 5 戦略は実は「1 つのエンジンの 5 つのノブ違い」です（greedy / greedy_len / ripup / ripup_fanout / fine_grid）。「5 つの別アルゴリズムが競った」ではなく、「1 つの自動配線器を 5 通りにチューニングして、どこで勝つか負けるかを観察した」が正確な言い方です
• それでも面白い観察がいくつかありました。簡単な盤では時間対効果で greedy_len が本命 だったり、fine_grid（細グリッド）が盤によっては最下位 に落ちたり。最強の設定は盤ごとにひっくり返る ので、「万能の一手はない」というありふれた話を、自分の手元で観察した回でもあります
• これは仕事ではなく、個人的な興味でやっている趣味の実験です。完走させるのが意外と難しく、何度も書き直しました。コードは GitHub に置いてあって、git clone して WSL（WSLg 付き Windows）上でそのままライブ GUI も動きます

トーナメント形式で観戦するのは単純に楽しいんですが、書き終わって思うのは「自分の自動配線が、どの盤で強くてどの盤で弱いかを並べてみると、設計の暗黙の前提がはっきり見える」ということでした。これも、自分で並べないと気付けない種類の発見でした。

前回のおさらいと、今回の動機

前回は「自分で書いた素朴な A* + 2 層 + ビア」で、ゆったり置いた基板の 22 本がぜんぶ通った、というだけの小さな記事でした。実は「次は詰め込んで破綻させるぞ」と意気込んでみたものの、いざ書き始めると別の興味が出てきまして。

配線アルゴリズムを 1 つ書いて「動いた」「動かなかった」だけだと、強さ弱さが見えないんです。実装の良し悪しを語るには、横並びで比較できる土俵が要る。

そこで今回は、配線アルゴリズムだけを純粋に競わせる小さなベンチマーク基盤を作ってみました。製造（Gerber 出力）も回路図も GUI 編集機能も入れません。「まだ配線されていない基板を投げ込むと、配線済み盤と順位表が返ってくる」だけのアリーナです。

リポはこちら → logicia32/router-arena

仕事の片手間でちまちま書いていたので、書いては動かない、書き直しては別のところで詰まる、という繰り返しでした。完走させて表が出るまでが、思っていたよりだいぶ遠かった、というのが正直なところです。

何を競わせるか — 5 つの戦略（と、正直な開示）

走らせたのは以下の 5 つです。専門用語が並ぶので、その場で説明を入れます。

ここで出てきた用語を、その場で簡単に。

• rip-up（リップアップ）& retry：すでに引いた線を 一度はがして 別の経路で引き直すこと。「先に引いた線が後から来た線をブロックしている」状態を解くための、自動配線で一番ポピュラーな救済手段です
• pad pinch（パッド・ピンチ）：パッドの周りが他の配線・パッドで囲まれてしまって、そこから一歩も出られない状態。「裏（反対の銅箔層）に逃げるビアを近くに打って助ける」のが定石です
• fanout（ファンアウト）：その「裏に逃げるビア + 短い渡り線」のセット。SMD（基板の上に貼り付けるタイプの部品）のパッドからの脱出によく使います
• グリッド：自動配線は格子の上の「迷路解き」として実装するのが定番で、その格子の刻みの細かさのことです。細いほど詰まったところを縫って通せるかもしれませんが、計算コストはぐっと重くなります

ここで正直なところをもう一度。この 5 つはすべて、内部では同じ 1 つの autoroute() 関数を呼んでいて、引数を変えているだけです。リポの arena/strategies/builtin.py を覗くとそのまんまです。

@router("greedy",    desc="composite順・rip-upなし")
def greedy(b, on_event=None):    autoroute(b, on_event=on_event)

@router("ripup",     desc="composite順 + rip-up&retry")
def ripup(b, on_event=None):     autoroute(b, ripup=True, ripup_rounds=6, on_event=on_event)

@router("fine_grid", desc="rip-up + 12.5mil 細グリッド")
def fine_grid(b, on_event=None): autoroute(b, ripup=True, ripup_rounds=6,
                                           grid=_ti(12.5,"mil"), on_event=on_event)

なので「5 つの autorouter が競い合った」ではなく、「1 つの autorouter を 5 通りに設定したときの挙動を比較した」が正確です。この区別は最後まで効いてくる ので、先に置いておきます（本当の意味で別エンジン同士の対決は、後述のとおり次回への宿題です）。

どんな問題を解かせるか — 公式コース

ベンチの対象は 手続き生成の合成基板 です。フットプリントライブラリは持ち込まず、DIP / SOIC / QFP / BGA（足の形と並びが違う 4 種類のパッケージのことです）のパッド列をプログラムで作って、ネットを乱数で割り当てています。

公式コースは 8 問。広いピッチで素朴に通る dip_easy から、0.8 mm ピッチの BGA-100 ボスステージ bga100_boss まで、詰まり具合を段階的に上げてあります。

$ arena list
== 戦略 ==
  greedy         composite順・rip-upなし（最速・基準）
  greedy_len     length順・rip-upなし
  ripup          composite順 + rip-up&retry 6round
  ripup_fanout   rip-up + pad_pinch自動 via fanout
  fine_grid      rip-up + 12.5mil 細グリッド

== 公式コース (suite) ==
  dip_easy     10xdip14 @100mm   random
  dip_dense    16xdip14 @90mm    random
  soic_mid     20xsoic8 @100mm   random
  soic_tight   20xsoic8 @90mm    random
  qfp_boss     8xqfp32 @110mm    random
  qfp48_mix    6xqfp48 @120mm    mixed
  bga40_mix    6xbga40 @100mm    mixed
  bga100_boss  4xbga100 @120mm   mixed

種（seed）を固定すれば誰でも同じ盤を再現できます。外部の EDA ツールは不要、Python 1 本で動きます。

採点ルール — DRC違反は最下位

「強さ」をぱっと「何本通ったか」で測りがちですが、実機で使うことを考えると DRC 違反（線幅・すき間・外形などの規約破り）を 1 件でも出した順位を上には置けない ので、採点はこうしました。

1. 例外で死んだ戦略 → 最下位
2. DRC 違反あり → 違反なしの下
3. 配線率（通った本数 / 全体）↑
4. DRC 件数 ↓
5. 時間 ↓
6. 総配線長 ↓

実装は arena/race.py の score_key() です。「製造できないルートに点を与えない」を最優先にエンコード したつもりです。

レース結果その1 — dip_easy（簡単な盤）

dip_easy は 10 個の DIP-14 を 100 mm 角に並べた、いちばん緩い盤です。ネット数は 38 本。

=== LEADERBOARD (dip_easy) ===
 # strategy            routed     %  DRC  via  trk  len(mm)     sec
-------------------------------------------------------------------
 1 ripup              35/38     92%    0   49  425   2404.2   15.00
 2 ripup_fanout       35/38     92%    0   49  425   2404.2   17.81
 3 greedy_len         33/38     87%    0   13  293   1873.6    3.85
 4 fine_grid          33/38     87%    0   81  565   2180.4  310.01
 5 greedy             21/38     55%    0   11  179   1310.5    2.96

目を引いたのは 3 行目と 4 行目です。greedy_len と fine_grid が同じ 33/38（87%）でタイ。でも時間は 3.85 秒 対 310 秒（およそ 80 倍差）。

fine_grid は「グリッドを半分に細くしたぶん脱出余地が増えるはず」という戦略でした。実際、細かい盤面なら効きます。でも 太ピッチ THT（足の長いタイプの部品）が並んだこの盤では、細かさのアドバンテージはそもそも要りません。要らない場所で重い手を打つと、当たり前ですが時間だけ食って何も得しません。

逆に greedy_len（rip-up なし、ネット順を「短い順」に並べただけ）は、rip-up 付きの ripup に 2 本差まで詰め寄っています。「rip-up を入れると 35 本、入れないと 33 本」というのは、効きとしては小さくはないですが、時間で割ると greedy_len のほうがコストパフォーマンスは圧倒的に良い。「速い + 軽い + 8 割通る」が欲しい現場では、rip-up なしで十分、というのが正直な観察です。

greedy（複合スコア順）と greedy_len（短い順）の 21 → 33 本の差も大きい。ネット順を変えるだけで通る本数が 12 本増える。少なくとも自分のこの実装では、ネット順の影響がかなり大きい、という古典的な観察を追体験できた格好です。

下が、ripup で配線した最終状態の絵です（赤＝表の銅箔層、青＝裏の銅箔層、黒丸＝ビア、点線＝通らなかったネット）。GUI の表示と中身は同じです。

レース結果その2 — qfp_boss（中ボス）

次は qfp_boss。8 個の QFP-32（0.8 mm ピッチの SMD）を 110 mm 角に並べた中ボスです。ネット数は 69 本。

=== LEADERBOARD (qfp_boss) ===
 # strategy            routed     %  DRC  via  trk  len(mm)     sec
-------------------------------------------------------------------
 1 ripup_fanout       35/69     51%    0  111  492   2846.3  490.18
 2 ripup              29/69     42%    0   93  409   2122.6  273.64
 3 greedy_len         27/69     39%    0   30  177   1405.1   26.11
 4 greedy             20/69     29%    0   41  162   1280.6   13.50
 5 fine_grid          12/69     17%    0   10   80    666.4  155.07

注目は最下位の fine_grid。SMD 細ピッチの脱出が大事な盤こそ fine_grid の本懐 のはずなのに、ノーマル ripup の半分以下、「何もしない」素朴な greedy の 60% しか配線できていません。track 80 本・via 10 本と「ほぼ何も試せていない」状態です。

これ、最初は「細グリッド戦略のバグ」を疑いました。直す前に、まず autoroute の失敗理由の breakdown を取って、4 盤ぶん比べてみました。pp = pad_pinch、np = no_path（経路が見つからなかった）です。

fine_grid は L4 で +14 本、bga40_mix で +10 本、本来の細ピッチで実際にはちゃんと強い。ところが、qfp_boss だけで −17 本 と巨大に崩れます。盤次第で挙動が真逆になっている、という現象が起きていました。

細グリッドが盤によって真逆になる理由

最初の素朴な仮説は「細グリッドだと SMD パッドの隣セルが全部 halo（パッド禁止帯）で埋まって、Dijkstra が一歩も動けない」でした。事実そうなる組み合わせは存在するんですが、bga40_mix で逆に勝てている ことの説明がつかない。

差を生んでいたのは、戦略のコードではなく 盤側の設計ルールの厚み でした。

QFP-32 のピッチは「0.8 mm」と書きましたが、実装上の正確な値は 32 mil = 813 μm（中心間距離）です。隣接パッドの halo（パッドの中心からどこまで他の配線を寄せないか、の禁止距離）を実寸で計算すると、

• default rule：813 − (228 + 325) = 260 μm （＝12.5 mil ≒ 318 μm セルの内側！）
• fine rule：813 − (228 + 175) = 410 μm （＝12.5 mil セルの外側、ターゲットパッドの隣セルは生き残る）

つまり qfp_boss だけが「default rule（厚いクリアランス） + 0.8 mm ピッチ + 細グリッド」の三重奏 で詰む盤になっていた。デフォルト 25 mil のままなら隣セルは halo の外なので Dijkstra は一歩進めるけれど、グリッドを半分に細くした途端、ターゲットパッドの周囲 8 セルが隣接パッドの halo で全部塞がり、自身は via 禁止（パッド真上のドリル穴は実機不良の元なので）なので、一歩も動けないまま諦める、という挙動でした。

これは「fine_grid のバグ」ではなく、「fine_grid は fine rule_class（クリアランス 0.10 mm 想定）とセットで設計されていたのに、qfp_boss の盤定義に対しては整合が取れていなかった」という、ベンチを作った私の見落としです（直す前に、まずこの観察を記事の核にしようと思って、そのまま残してあります）。

「万能の一手はない」を盤上で

並べてみると、全コースで一位になる戦略は無かった、というのが今回の身も蓋もない結論でした。

並べて思ったのは、「常に勝つ唯一の自動配線」みたいなものを目指すのは、設計の方向が違うのかもしれない ということでした。EDA の世界で「設計ルール（clearance / width / via stack…）」と「ルータの探索パラメータ（grid / cost / fanout 方針）」を同じ目で見て調整する仕事があるのは、たぶんこういう実態だからなんだろうな、と。自動配線の本当の難しさは、ルータそのものよりも、ルータと盤側ルールの整合にあるのかもしれません。

自分で書いた小さな自動配線をベンチに乗せて並べてみないと、私には実感できなかった感覚でした。

ライブで観戦できる GUI（WSL でも動きます）

今回のアリーナには PySide6 のライブ観戦 GUI も付けてあります（必須ではない、任意の依存）。arena gui --problem qfp_boss で起動すると、配線が引かれていく様子・rip-up で引き剥がされる様子・via が打たれる瞬間 までリアルタイムに描画されます。

git clone https://github.com/logicia32/router-arena
cd router-arena
pip install -e ".[gui]"
arena gui --problem L3       # 1 戦略をライブ実行
# 上部の 🏁 Race all で全戦略を順に走らせる
# 🏆 Tournament で勝ち抜き戦

Windows 11 の WSL 2（WSLg 付き）でも、追加設定なしでそのまま窓が出ます。Linux / Mac でも標準の Qt が動けば OK です。アルゴリズムが基板を 諦めながら考えてる感じ が、なかなか味があります（rip-up の引き剥がしは特にエンタメ性が高いです）。

次回への宿題

正直、今回はまだ「同じエンジンの 5 通りの設定」を並べただけで、本当の意味での「別エンジン同士のトーナメント」にはなっていません。rip-up & retry とは独立の別系統、たとえば 混雑マップを反復で更新して経路コストに乗せる「PathFinder 系」の density router を arena に投げ込んで、初めて「ルータ族 vs ルータ族」の対決ができます。

リポの arena/strategies/experimental.py に tsp_order / ga_order / density / shove / ml_cost の 5 つの枠を空けてあって、現状は「未実装」とだけ並んでいます。次回は、その中で density（PathFinder 系の negotiated congestion） を実装して、ripup 系と本気で競わせてみる予定です。

正直なところ、まだまだ趣味のレベルを脱していません。自動配線は奥が深い世界で、今回ぶつかった「ルールと grid の整合」だけでも、その入口を一段降りた気分です。次回もまた、再チャレンジします!!

ここまで読んでくださってありがとうございました。間違いや、もっと良い計測軸の提案があれば、ぜひ教えてください。

おまけ：レースを再現する手順

git clone https://github.com/logicia32/router-arena
cd router-arena
pip install -e ".[render]"     # PNG 書き出しまで欲しければ render extra
arena race --problem dip_easy
arena race --problem qfp_boss
arena suite                    # 公式コース全 8 問の集計

# 自前の戦略を入れる:
cp arena/strategies/_template.py arena/strategies/myrouter.py
# 編集 →
arena race --strategies myrouter,ripup --problem L3

各戦略は fn(board, on_event=None) -> None の 1 つの関数（board をその場で配線するだけ）。リップアップでも GA でも何でも、別ファイルに置けば勝手にレースに参戦します。