Battle Sheep

Battle Sheep is a board game about capturing as much area on the board as possible, but you can only move your sheep linearly by splitting up existing stacks of sheep. This project is about transfering the game onto the web, and implementing an AI adversary. This project was for a university algorithms course. If you want to try it out, I recommend playing on the 'open' level.

Main game screen with the game board and movement controls.The player selecting a new square onto which move their pieces.

The AI algorithm

I implemented the AI using a minimax algorithm with alpha-beta pruning, and optimization tricks such as 'move ordering'. The online version makes the AI traverse the game tree until a depth of 6, i.e. find the best move for the next 6 turns into the future. Here are some performance benchmarks for the AI.


I'm sure there is still plenty of room for optimization, but I didn't have time to explore further. One way to improve the performance of the AI is by using web workers to take advantage of parallel processing.