In this installment of exploring game algorithms using the simple game Color Walk, we're going to do something a little different. Last time we explored a number of variations and hybrids of Dijkstra's algorithm—the classic, efficient graph algorithm for finding shortest paths—and found that pairing it with a pre-run of Greedy Look-Ahead (GLA) performed better than any other algorithm we've seen so far. This time we're not going to explore any new algorithms. Instead, we're going to look into what makes Dijkstra's algorithm tick: the priority queue. Save for this variant of a standard queue, Dijkstra's algorithm is conceptually the same as Breadth-First Search (BFS), so we want to see what makes this priority queue so special and how we can implement one efficiently with a binary heap.

# Lucid Mesh

Musings on software development, technology, and their interconnections with a programmer's everyday life

### Explore Simple Game Algorithms with Color Walk: Part 10

We're back for another round of exploring game algorithms using the simple game Color Walk. We finally reached the point of evaluating Dijkstra's algorithm—the classic, efficient graph algorithm for finding shortest paths—in the last post. It performed pretty well against the top dogs: Greedy Look-Ahead (GLA) and the GLA-BFS hybrid, especially when it came to consistently finding the best moves. However, it failed to find the best moves when a board could be solved in under 29 moves, so we're going to see if we can squeeze out any more performance by modifying Dijkstra's algorithm further. To do that, we're going to try combining Dijkstra's algorithm with GLA, running Dijkstra's algorithm in more than one pass, and changing the heuristic we use to guide the search.

### Explore Simple Game Algorithms with Color Walk: Part 9

Welcome back for more exploration of game algorithms using the simple game Color Walk. In the last post we covered the other fundamental graph search algorithm, depth-first search (DFS), the counterpart to the previously discussed breadth-first search (BFS). These graph algorithms do a full search of the graph of a color walk game, the full set of board positions resulting from each move at each point in the game. We found that running either of these algorithms to completion is extremely prohibitive due to the graph size being exponential in the number of moves. In order to deal with that exponential growth, we need to look at other graph algorithms, and we have quite a few to choose from. We'll explore some categories of graph algorithms and look at one in more detail, Dijkstra's algorithm.

### Explore Simple Game Algorithms with Color Walk: Part 8

We're continuing this ongoing saga of different game algorithms using the simple game Color Walk. In the last post we started exploring the fundamental graph search algorithms with breadth-first search (BFS), because after all, the full set of move choices and resulting board positions of any game can be arranged as a graph. After looking at BFS and finding that we can nominally improve the search for shortest number of moves, on average, it's time we look at the close sibling of BFS: depth-first search (DFS). We'll quickly run into performance issues just like we did for BFS, but let's see if we can come up with a reasonable way to limit DFS so that it can be a useful algorithm.

### Explore Simple Game Algorithms with Color Walk: Part 7

We're continuing to explore different game algorithms using the simple game Color Walk. In the last post we took a deep dive into other heuristics that could be used instead of the obvious maximize-the-number-of-blocks-removed approach and found that the obvious choice is actually hard to beat. After looking at various heuristics, it's time we fill in some gaps in our exploration of algorithms by looking at a couple of fundamental graph algorithms: breadth-first search (BFS) and depth-first search (DFS). These algorithms are the two basic ways to search for something in a graph of nodes (or vertices) connected by edges, and a graph is exactly what we have when we draw out all possible move choices with each node representing a move and edges connecting sequential moves. We'll focus on BFS for this post.

### Explore Simple Game Algorithms with Color Walk: Part 6

What's next with exploring different game algorithms using the simple game Color Walk? We've come a long way so far with building out the game's interface to support looking at different algorithms, looking at trivial round-robin and random algorithms, and designing a greedy algorithm that picked each move based on the most blocks removed. The last post showed how far we could push the greedy algorithm to look ahead and try to pick a better move that would result in more blocks removed up to five moves ahead, but even after improving the data structure for the board, we hit diminishing returns in looking more moves ahead. It's time to expand our search for algorithms by looking at other heuristics we can use to pick the best move. The greedy algorithm used a heuristic of "the most blocks removed" for any given move, but there are others that we can use.

### 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.

Subscribe to:
Posts (Atom)