Team90: CS3600 Chicken Agent

• Final agent submission for the Fall 2025 ByteFight tournament.
• The game is a 1v1, turn-based match on an 8x8 board where each chicken tries to lay the most eggs.
• Movement is shaped by trapdoors, turds, parity rules, and strict time limits.
• Our agent uses A* pathing, alpha-beta pruning, trapdoor belief tracking, and regression-based scoring.
• Built by Evan and Kylie.

Game Snapshot & Stats

Final: Ranked 34 / 102 teams, ~top 1/3 of the ladder.

Contents

• agent.py – Core decision loop, alpha-beta pruning, A* pathing, feature scoring.
• trapdoor_belief.py – Trapdoor probability model and signal update rules.

Core Design

1. Board Evaluation + Weighted Feature Scoring

Every action is scored using a weighted sum of features.
Weights come from regression fits on CSV match logs run through the Georgia Tech PACE cluster.

Main features:

• Egg reachability on our parity squares.
• Distance and safety relative to trapdoor belief.
• Opponent pressure and lane control.
• Self-block risk.
• Turd strategic value.
• Expected future egg gain if the current step opens a lane.

This evaluator is used inside our alpha-beta and also for one-step fallback scoring.

2. Alpha-Beta Pruning (Depth-Limited Search)

The engine has tight time and branching limits.
Our alpha-beta search is small but effective:

• Depth 2 or 3 depending on remaining time.
• Early pruning of:
  • trapdoor-unsafe actions,
  • low-value turd steps,
  • moves that create dead-ends,
  • moves dominated by A* route checks.
• Terminal checks only score egg margin and position safety.

Alpha-beta gives the agent the ability to plan past immediate bait traps and avoid self-lockouts.

3. A* Pathfinding With Manhattan Heuristic

Many board states hinge on whether a chicken can reach a target column, dodge a trapdoor zone, or move past a cluster of enemy turds.

We use A* for fast reachability and lane analysis:

• Heuristic: Manhattan distance (abs(dx) + abs(dy)), since movement is limited to cardinal steps.
• Cost penalties:
  • squares near high trapdoor belief,
  • squares adjacent to enemy turds,
  • paths that reduce future egg-laying potential.
• Use cases:
  • Detect whether a lane is reachable before the opponent.
  • Confirm that a move does not place us on a path with no safe exit.
  • Estimate the “value” of choosing one direction over another.

A* runs outside alpha-beta and is used for pruning and for scoring.

4. Trapdoor Belief Model

Implemented in trapdoor_belief.py.

The engine provides noisy (heard, felt) signals for white-parity and black-parity trapdoors.

Our belief model:

• Maintains probability grids for each parity.
• Updates likelihoods using signal tables from the assignment.
• Suppresses inconsistent positions.
• Normalizes every turn.
• Exposes a probability penalty used by both A* and evaluation scoring.

This gives the agent stable behavior around trapdoor zones without freezing movement.

5. Regression-Based Weight Tuning (PACE)

To replace hand tuning, we collected many match logs, converted them to CSV, and ran a small regression job on PACE:

• Input features: lane length, trapdoor distance, opponent proximity, self-block risk, egg value.
• Target: per-turn scoring contribution or final egg margin.
• Output: numerical weights injected into the scoring functions.

This greatly improved stability across a wide range of opponents.

6. Turd Strategy

We drop turds only when they give real board advantage:

• Blocking a lane the opponent needs for egg access.
• Forcing a long detour around a trap-heavy region.
• Creating space to move safely when both players are close.

Turd steps are included in alpha-beta but heavily pruned to keep the tree small.

7. Time-Aware Search Modes

The agent switches modes depending on time:

• Normal Mode: full scoring, A*, trapdoor checks, depth-3 alpha-beta.
• Low-Time Mode: depth-2, fewer branches.
• Critical Mode: no search; only fast scoring of legal moves.

Code Snippets

Move Selection (agent.py)

legal_moves = self.get_legal_moves(board)
scored = []

for mv in legal_moves:
    val = self.search_with_pruning(board, mv, depth)
    scored.append((val, mv))

best = max(scored, key=lambda x: x[0])[1]
return best.direction, best.move_type

Alpha-Beta Core

def alphabeta(self, state, depth, alpha, beta, maxing):
    if depth == 0 or state.is_terminal():
        return self.evaluate(state)

    if maxing:
        for mv in state.legal_moves():
            val = self.alphabeta(state.apply(mv), depth - 1, alpha, beta, False)
            alpha = max(alpha, val)
            if beta <= alpha:
                break
        return alpha

    else:
        for mv in state.legal_moves_opponent():
            val = self.alphabeta(state.apply_opponent(mv), depth - 1, alpha, beta, True)
            beta = min(beta, val)
            if beta <= alpha:
                break
        return beta

A* With Manhattan Heuristic

def heuristic(a, b):
    return abs(a.x - b.x) + abs(a.y - b.y)

def astar(self, start, goal, trap_penalty):
    open_set = [(0, start)]
    g = {start: 0}

    while open_set:
        _, node = heapq.heappop(open_set)
        if node == goal:
            return g[node]

        for nxt in self.neighbors(node):
            cost = 1 + trap_penalty[nxt]
            new_g = g[node] + cost
            if nxt not in g or new_g < g[nxt]:
                g[nxt] = new_g
                f = new_g + heuristic(nxt, goal)
                heapq.heappush(open_set, (f, nxt))

    return None  # unreachable