Search This Blog

Explore Simple Game Algorithms with Color Walk: Part 5

We're continuing to look at different game algorithms using the simple game Color Walk as a sandbox for exploration and discovery. The last post covered our first foray into a non-trivial algorithm, namely the greedy algorithm. We found that using the strategy of grabbing the most blocks from the board on each move was a reasonable thing to try, and it outperformed all the previous trivial algorithms. Then we extended the greedy algorithm to look ahead one move and found that it performed even better. Now we're going to extend the greedy algorithm to look ahead arbitrarily far and see how far we can actually look before the run time of the algorithm becomes prohibitive. In this process we should be able to find a way to improve the current data structure of the board to make searching more efficient and allow the algorithm to search more moves ahead as a result.