Inspiration
We were inspired by the challenge of building a competitive AI agent that could not only play well but also learn and adapt its strategy over time. Game-based AI has seen incredible success, with agents mastering Chess, Go, and even StarCraft. We aimed to apply similar methods to Push Battle, a unique board game that combines elements of positioning, spatial reasoning, and strategy.
What it does
This project taught us a lot about blending different algorithms to create a more robust AI. Q-learning allowed our agent to learn from its past games, Minimax helped with strategic depth by planning moves ahead, and Monte Carlo Tree Search provided an exploratory advantage, allowing the agent to simulate various move sequences and outcomes. We also gained insights into effective memory and computation usage, as the agent operates under strict resource constraints.
How we built it
We built our agent by combining three main algorithms:
Q-learning: This reinforcement learning method helps our agent to develop a long-term strategy by rewarding it for moves that lead to winning positions. The model trained by self-play to recognize patterns that increase its chances of winning. Minimax with Alpha-Beta Pruning: Minimax allowed us to anticipate the opponent's moves and determine the best possible outcome from each decision. Alpha-Beta Pruning was essential to manage the depth of this search tree, enabling our agent to look ahead efficiently without exhaustively evaluating every option. Monte Carlo Tree Search (MCTS): To account for variability and randomness, we used MCTS to simulate multiple move sequences and determine which paths were most promising. This allowed our agent to explore potential outcomes and adapt to new board states effectively.
Challenges we ran into
One of the primary challenges was balancing the different strategies. Q-learning requires a lot of training data, while Minimax is computationally intensive, especially on an 8x8 grid. Additionally, MCTS can be resource-heavy if not tuned correctly. Working within the provided hardware constraints was tricky, as we had to optimize our code and tune hyperparameters to make sure our agent performed well without timing out. The complexity of Push Battle's mechanics also made it challenging to design rules for pushing and moving pieces effectively, especially with the “wrap-around” rule on the board edges.
Accomplishments that we're proud of
Successfully integrated Q-learning, Minimax, and Monte Carlo Tree Search to create a versatile and adaptive agent. Optimized performance within strict resource limits, ensuring timely and efficient gameplay. Developed a winning strategy that learns, adapts, and improves with each game.
What we learned
The strength of hybrid algorithms in complex games, with each method enhancing the agent's adaptability and strategic depth. Practical skills in balancing AI performance with efficiency under resource constraints.
What's next for The Push Battle!
We plan to further refine the agent’s learning and adaptability, explore additional strategies to improve decision-making speed, and experiment with new AI techniques for even greater competitiveness.
Log in or sign up for Devpost to join the conversation.