🎮 Snake VS

Web ページが対戦を進行し、UIAPduino は 次の方向 を返すだけです。

ここで大事なのが相手の体をどうやって知るか。 蛇は毎ティック成長して縮まないので、 「相手の体」＝「相手の頭が通った全マス」です。 だから Web は相手の頭の座標だけ送れば足り、受け取った頭を記録していくだけで相手の体が完全に分かります:

uint8_t cell[16][16];  // EMPTY / MINE / OPP / ROCK

// CMD_TICK 受信時: 両者の頭を記録するだけ
myX  = buf[1]; myY  = buf[2];
oppX = buf[3]; oppY = buf[4];
cell[myY][myX]   = MINE;
cell[oppY][oppX] = OPP;

1 セルを 1 バイトにまとめているのは RAM 節約のためです（bool 配列 3 枚より 512 バイト少ない）。 CH32V003 の RAM は 2KB しかないので、キミのアルゴリズム用に余裕を残してあります。

vs.sendDir(dx, dy) で方向を送ります（必ず呼ぶこと）。

死亡条件は「壁の外」「岩」「どちらかの蛇の体」に進入すること。 cell[y][x] が 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;
}

画面の 「陣地 ON」で、どちらが先に到達できるかを色分け表示できます。 自分の陣地が緑、相手の陣地が赤。CPU Lv4 がこれを最大化してくることを目で確認できます。

もうひとつ、引き分けの最大の原因になる注意点があります。 避けるべきなのは「相手のいまの頭」ではなく、 「相手が次に入れるマス」です。 両者は同時に着手するので、相手の頭の隣のマスへ進むと、 相手も同じマスを選んでいた場合に正面衝突して両者死亡になります。

// そのマスは相手も次の 1 手で入れるか？
bool contested(int16_t nx, int16_t ny) {
    int16_t d = (nx > oppX ? nx - oppX : oppX - nx)
              + (ny > oppY ? ny - oppY : oppY - ny);
    return d == 1;   // 相手の頭から 1 マス = 取り合いになる
}

配布スケッチはこの判定を入れてあります。 入れないとどうなるか実測した結果がこちらです（配布スケッチ同士を 60 戦させたもの）:

相手の頭だけ避ける（絶対方向の固定順）  → 決着 10%・引き分け 54（全て正面衝突）
＋ 次に入れるマスも避ける              → 決着 83%（ただし片側に偏る）
＋ 手の評価順もシャッフル              → 決着 87%・偏りなし

2 台とも同じスケッチだと、180° 対称の盤面で完全な鏡像になり、 中央で必ず正面衝突します。手の評価順をシャッフルして鏡像を崩すのも セットで必要です。配布スケッチは PLAYER_NAME と開始座標から乱数の種を作っているので、 2 台が同じ動きになりません。

なお生き残るだけなら CPU Lv1 には勝てますが、すぐ自分の体で囲まれて詰みます。

4 方向それぞれについて、そこから BFS で到達できるマス数を数え、 最も広い空間につながる方向を選びます。行き止まりに入り込まなくなります:

uint16_t countReachable(uint8_t sx, uint8_t sy) {
    bool visited[16][16];
    // ... 初期化 ...
    uint16_t head = 0, tail = 0;
    bfsQ[tail++] = (sy << 4) | sx;   // 座標を 1 バイトに詰める
    visited[sy][sx] = true;
    while (head < tail) {
        uint8_t p = bfsQ[head++];
        uint8_t x = p & 15, y = p >> 4;
        for (uint8_t d = 0; d < 4; d++) {
            int16_t nx = x + DDX[d], ny = y + DDY[d];
            if (!passable(nx, ny) || visited[ny][nx]) continue;
            visited[ny][nx] = true;
            bfsQ[tail++] = (ny << 4) | nx;
        }
    }
    return tail;   // 到達できたマス数
}

これは Snake Solver のヒント 4 と同じ考え方で、配布スケッチがこの実装です。 CPU Lv3 と互角まで来ますが、自分が詰まないことしか見ていないので Lv4 で止まります。

対戦で勝つには「自分が広い」だけでなく「相手を狭くする」視点が必要です。 そこで盤面をどちらが先に到達できるかで分割します（ボロノイ図）。

やり方: 自分の頭から BFS した距離 myDist[y][x] と、 相手の頭から BFS した距離 oppDist[y][x] を作り、各マスを比べます。
・myDist < oppDist → 自分の陣地
・oppDist < myDist → 相手の陣地
・同じ → どちらでもない

評価値 = 自分の陣地の数 − 相手の陣地の数。 4 方向それぞれについて「そこへ動いた後」の評価値を計算し、最大の方向を選びます。

// 距離配列は uint8_t 16×16 = 256 バイト × 2 枚。
// 255 を「未到達」の印にすれば visited 配列は要らない。
uint8_t myDist[16][16], oppDist[16][16];

// (sx, sy) から各マスまでの最短距離を BFS で求める。
// 壁・岩・両者の体で到達できないマスは 255 のままになる。
void bfsFill(uint8_t dist[16][16], uint8_t sx, uint8_t sy) {
    for (uint8_t y = 0; y < 16; y++)
        for (uint8_t x = 0; x < 16; x++)
            dist[y][x] = 255;

    const int8_t dx[4] = { 1, 0, -1,  0 };
    const int8_t dy[4] = { 0, 1,  0, -1 };
    uint16_t head = 0, tail = 0;

    dist[sy][sx] = 0;
    bfsQ[tail++] = (uint8_t)((sy << 4) | sx);

    while (head < tail) {
        uint8_t p = bfsQ[head++];
        uint8_t x = p & 15;
        uint8_t y = p >> 4;

        for (uint8_t d = 0; d < 4; d++) {
            int16_t nx = (int16_t)x + dx[d];
            int16_t ny = (int16_t)y + dy[d];
            if (!passable(nx, ny)) continue;
            if (dist[ny][nx] != 255) continue;

            dist[ny][nx] = dist[y][x] + 1;
            bfsQ[tail++] = (uint8_t)((ny << 4) | nx);
        }
    }
}

int16_t voronoiScore() {
    bfsFill(myDist,  myX,  myY);
    bfsFill(oppDist, oppX, oppY);
    int16_t mineCount = 0, oppCount = 0;
    for (uint8_t y = 0; y < 16; y++)
        for (uint8_t x = 0; x < 16; x++) {
            if (myDist[y][x] == 255 && oppDist[y][x] == 255) continue;
            if (myDist[y][x] < oppDist[y][x])      mineCount++;
            else if (oppDist[y][x] < myDist[y][x]) oppCount++;
        }
    return mineCount - oppCount;
}

相手を壁際に追い込む動きが自然に出てきます。これで CPU Lv4 を狙えます。

注意: 絶対方向（「右優先」など）で優先順位を決めると盤面の左右で癖が出ます。 スタート配置は 6 種類あり左右が入れ替わるので、必ず盤面から計算した基準で選びましょう。

CPU Lv5 は相手の応手まで読んできます。勝つには同じことをする必要があります。

考え方（ミニマックス）: 自分の候補手それぞれについて、 「相手が自分にとって最悪の手を返してきたときの評価値」を計算し、 その中で最大のものを選びます。

// 深さ 2（自分の手 → 相手の手）
int16_t best = -32000; int8_t bestD = 0;
for (自分の手 m : 4方向) {
    if (!合法(m)) continue;
    仮に m を打つ;
    int16_t worst = 32000;
    for (相手の手 o : 4方向) {
        if (!合法(o)) continue;
        仮に o を打つ;
        int16_t v = voronoiScore();
        if (v < worst) worst = v;
        o を戻す;
    }
    m を戻す;
    if (worst > best) { best = worst; bestD = m; }
}

気をつけること:
・仮に打った手は必ず元に戻す（cell を書き換えたら復元）
・両者の頭が同じマスになる組み合わせは引き分け＝自分も死ぬので、評価に含める
・CH32V003 は RAM 2KB。深さを増やすときは visited をローカルに取らず、 距離配列を再利用してスタックを節約する
・ロックステップなので計算時間で負けることはないが、2 秒以内に返すこと

ここまで来れば全段クリアが見えます。健闘を祈る！