← UIAPduino WebHID Lab対戦を開く →
SnakeVS.ino / VISUAL GUIDE

2匹ぶんの「記憶」と
1手の決め方を見てみよう

対戦版は、1枚の cell[16][16] に自分・相手・岩をまとめます。Webから届く両者の頭を記録しながら、次の方向だけを返します。

RESET→ROCK × n→START→DIR⇄同時移動・TICK
01
MEMORY MODEL

1マスを1バイトで表す

cell[y][x] には、次の4状態のどれか1つが入ります。複数の bool 配列を重ねず、盤面1枚だけで判定できます。

EMPTY = 0進入できる空き
MINE = 1自分の軌跡
OPP = 2相手の軌跡
ROCK = 3岩
3枚の bool[16][16] を持つ場合より512バイト節約し、RAM 2KBのCH32V003に探索用の余裕を残します。
00
COORDINATES

Xは右へ、Yは下へ

左上が (0,0)。添字はX・Yの順ではなく cell[Y][X] です。

X →　／　Y ↓

進入できる条件

盤外でなく、そのマスが EMPTY なら進めます。岩も両者の体も同じ判定で除外できます。

bool passable(int16_t x, int16_t y) {
  if (x < 0 || x >= 16 ||
      y < 0 || y >= 16) return false;
  return cell[y][x] == EMPTY;
}
01
CMD_RESET → CMD_ROCK × n

空にしてから、岩を1個ずつ記録

CMD_RESET で全マスを EMPTY にし、続く岩座標を ROCK に変えます。岩はWeb側で180°回転対称に配置されます。

例: 4組・8個の対称な岩

受信のたびに1マス更新

RESET [0x05] → すべて EMPTY
ROCK [0x03, 2, 3] → cell[3][2] = ROCK
ROCK [0x03, 13, 12] → 回転対称のペア
case CMD_ROCK:
  cell[buf[2]][buf[1]] = ROCK;
02
CMD_START / 0x01

自分と相手、2つの頭を置く

Webは「自分の頭」「相手の頭」「自分の初期方向」を送ります。2台対戦では、各デバイスへ自分視点に並べ替えて渡します。

自分 (3,8) ／ 相手 (12,7)

initRound()

myX=3;  myY=8;
oppX=12; oppY=7;
cell[8][3]  = MINE;
cell[7][12] = OPP;
curDx=1; curDy=0;
START [0x01, 3,8, 12,7, 2,1]
方向は +1 して送る: (2,1) → (+1,0)
03
passable() + contested

進めるマスと「取り合いになるマス」を分ける

壁・岩・両者の体を除いた候補を作ります。さらに、相手の頭から1マスの場所は、相手も次に入れるため正面衝突の危険があります。

水色=候補　黄色!=相手も選べる危険マス

相手の「現在地」だけでは足りない

両者が同時に同じ空きマスへ入ると引き分けです。候補と相手の頭のマンハッタン距離が1なら、評価を40点下げます。

dxo = abs(nx - oppX);
dyo = abs(ny - oppY);
if (dxo + dyo == 1)
  score -= 40;
鏡像対策: 候補の評価順も毎回シャッフルします。180°対称盤面で同じスケッチ同士が鏡のように動き続けるのを防ぎます。
04
countReachable()

BFSで、自分が生き残れる広さを数える

各候補から到達できる EMPTY の数をBFSで数え、取り合いペナルティを引いた点が最大の方向を選びます。

緑と赤の軌跡、岩をすべて壁として探索

評価例

↑ 上
204
→ 右
161
↓ 下
116
score = countReachable(nx, ny);
if (相手も入れる) score -= 40;

// 最大スコアの dx,dy を採用

配布スケッチは「自分の空間」だけを評価するため、CPU Lv3と互角ですがLv4のボロノイで壁に当たります。

05
CMD_DIR / 0x10

決めた「方向」だけをWebへ返す

座標は自分で確定しません。vs.sendDir(dx,dy) で次の向きを送り、Web側の同時移動を待ちます。

白い×は予定地。cellはまだ書き換えない

solveTick()

int8_t dx=curDx, dy=curDy;
computeNextDir(dx, dy);
curDx=dx; curDy=dy;
vs.sendDir(dx, dy);
ロックステップ: Webは CMD_DIR を待ってから次のティックへ進むため、USB応答速度で勝敗が決まりません。
06
Web: stepBoth()

Webが2匹を同時に1マス進める

両者の予定地を先に計算し、移動前の同じ盤面を使って死亡判定します。生存した場合だけ、両者を一緒に盤面へ書き込みます。

同じ中央マスへ進む例 → 両者死亡

対戦特有の衝突

通常衝突壁・岩・どちらかの体
同じ予定地同じ空きマスへ同時進入
頭の交換互いの現在地へ同時進入
if (n1.x == n2.x && n1.y == n2.y)
  dead1 = dead2 = true;

// 生存時だけ両者を記録
07
CMD_TICK / 0x02

移動後の両者の頭から、体を復元する

蛇は縮まないため、「体」は頭が通った全マスです。Webは毎回、両者の新しい頭だけを送れば十分です。

前の頭は体に残り、新しい2マスを追加

受け取って、記録して、次を考える

myX=buf[1];  myY=buf[2];
oppX=buf[3]; oppY=buf[4];
cell[myY][myX]   = MINE;
cell[oppY][oppX] = OPP;
solveTick();
DIR方向を送る
Web同時移動
TICK両頭が届く
cell更新軌跡を追加
BFS次を考える
08
NEXT CHALLENGE: VORONOI

「自分が広い」から「相手より広い」へ

CPU Lv4は、各空きマスへどちらが先に着けるかを2回のBFSで比べます。緑の陣地数−赤の陣地数を最大化すると、相手を狭い側へ追い込めます。

緑=自分が先　赤=相手が先　暗色=同距離

配布スケッチを超える考え方

myDist  = BFS(myX, myY);
oppDist = BFS(oppX, oppY);

if (myDist < oppDist) mine++;
if (oppDist < myDist) theirs++;
score = mine - theirs;

CPU Lv5はさらに「自分の手→相手の最善応手」まで仮に打つ、深さ2のミニマックスを使います。

★
HOW TO WIN

配布スケッチを超える、勝つためのヒント

最大空間優先は「自分がすぐ詰まない」ための守りです。勝つには、同じ1手で相手の未来がどう狭くなるかまで評価します。

1広い場所より、通路の入口を先に取る
白い×のマスを取ると、盤面を左右に分けやすい

BFSの到達可能数だけでは、両者が使える共通空間もすべて「自分の空間」として数えます。狭い通路や分岐点を先に取ると、自分の壁で相手の移動範囲を切り離せます。

見る場所: 候補手を打った後、相手側の到達可能数がどれだけ減るか。
2自分と相手、両方の距離を比べる

各候補を仮に打ち、自分の頭と相手の頭からBFS距離を作ります。自分が先に着くマスを増やし、相手が先に着くマスを減らす手を選びます。

自分が先138マス
−
相手が先91マス
評価値=138 − 91=+47
3相手が一番うまく返す前提で選ぶ

自分に都合のよい相手の手ではなく、相手が返せる手のうち、自分の評価を最も下げる手を採用して比較します。これが深さ2のミニマックスです。

自分の候補 3手
↓ 各手に対する「相手の最善応手」を調べる
A: 上へ応手後の最悪値−18
B: 右へ応手後の最悪値+7　← 選択
C: 下へ応手後の最悪値−4
各「自分の手」について {
  worst = 相手の全合法手の 最小評価値;
}
答え = worst が最大になる自分の手;
4強さを落とす事故を最後に潰す

高度な評価関数でも、正面衝突、同点時の固定方向、仮想手の戻し忘れがあると安定して勝てません。

取り合いを減点相手の頭から1マスを警戒
同点はランダム化180°の鏡像動作を崩す
仮想手を復元cellと頭を必ず元へ戻す
RAMを再利用距離配列を使い回す
2秒以内に応答3回連続タイムアウトを防ぐ
全6配置で確認絶対方向の癖を見つける
✓
SUMMARY

SnakeVS.ino 全体を一言ずつ

cell[16][16]EMPTY・MINE・OPP・ROCKを1枚で管理。
initRound()両者の頭と自分の向きを初期化。
passable()壁・岩・両者の体をまとめて除外。
countReachable()候補から生き残れる空間をBFSで数える。
computeNextDir()取り合いを減点し、最大空間の方向を選ぶ。
CMD_TICK両者の頭を軌跡として記録し、次の方向を返す。
Snake VS に戻る