Using Restart Heuristics to Improve Agent Performance in Angry Birds

Tommy Liu, Jochen Renz, Peng Zhang, Matthew Stephenson

Abstract

In autonomous game-playing, agents often struggle with the "sunk cost" fallacy, continuing to play levels that are no longer winnable or optimal. This paper explores a multi-tiered heuristic framework for Angry Birds AI that allows agents to strategically restart levels. By utilizing Qualitative Spatial Reasoning (QSR) and post-shot performance analysis, agents can mimic human-like decision-making to save time and achieve higher scores in competitive environments.

Introduction

In the annual AIBIRDS competition, AI agents are tasked with playing Angry Birds autonomously under strict time constraints. While current agents have achieved high proficiency in aiming and trajectory planning, they typically lack the strategic foresight to abandon a failing attempt. Human players, conversely, frequently restart a level the moment they recognize a poor shot or realize the remaining resources are insufficient to clear the level.

A typical complex level in Angry Birds where strategic restarts can save time.

This "sunk cost" behavior in AI limits efficiency. If an agent spends two minutes finishing a level it cannot win, it loses time that could have been spent on a fresh, successful attempt. The authors address this by introducing a "restart heuristic" that triggers a level reset when a "lost cause" is detected.

Methodology

The proposed framework relies on four primary heuristic layers to determine when an agent should quit:

1. Qualitative Spatial Reasoning (QSR)

Rather than using computationally expensive physics engines like Box2D, the system employs QSR to model force propagation through game objects. This allows the agent to predict the outcome of impacts using "common sense" physics rules. The model defines four types of propagation: Direct, Falling, Structure Falling, and Thrown Blocks.

Diagrams illustrating the qualitative modeling of structure falling and thrown block propagation.

2. Solvability Heuristic

Evaluated prior to a shot, this heuristic checks if the remaining pigs are physically reachable and if the qualitative force available from the remaining birds is sufficient to eliminate them.

3. Post-Shot Heuristics

After a shot is fired, the agent evaluates its effectiveness using two metrics:

  • Score Heuristic: Did the shot result in a score increase above a predefined threshold?
  • Good Use Heuristic: Did the bird type interact with a material it is specialized for (e.g., Blue birds hitting ice)?

4. Combined Restart Signal

A weighted sum of these heuristics triggers a restart signal if a specific threshold is exceeded, signaling that the current run is unlikely to yield a competitive score.

Experimental Results

The heuristics were tested against standard benchmarks, including the "Poached Eggs" levels and historical AIBIRDS competition levels from 2014, 2015, and 2017.

Key findings include:

  • Efficiency Gains: A "Naive" agent showed a Time Ratio (TR) of 1.18, solved levels 18% faster when allowed to restart strategically.
  • Score Improvements: The "Datalab" agent, a former competition winner, achieved higher total scores on the 2015 Grand Final levels when the restart logic was enabled.
  • Predictive Accuracy: The QSR module proved highly effective at identifying "True Negatives"—correctly predicting when a level became impossible to solve after a specific bird was used.

Discussion and Conclusion

The research demonstrates that strategic quitting is a powerful optimization tool in time-limited AI competitions. By prioritizing qualitative "common sense" reasoning over exact physics simulations, agents can make rapid decisions about the viability of a level.

However, challenges remain. The current system acts as an external wrapper; because agents are not inherently aware of the restart, they may repeat the same unsuccessful shot. Future work will focus on integrating these heuristics directly into the agents' learning models and expanding the QSR logic to handle complex elements like TNT and specialized bird powers.

Summary updated

BibTeX
@inproceedings{liu2019using,
  author = {Tommy Liu and Jochen Renz and Peng Zhang and Matthew Stephenson},
  title = {{Using Restart Heuristics to Improve Agent Performance in Angry Birds}},
  booktitle = {CoG},
  year = {2019},
  url = {https://openreview.net/forum?id=IWJuEEmoVbF},
}
Figure