Coins Flipping AI Live Demo

Overview

This example demonstrates how the game AI implemented with A* search algorithm solves the coins flipping puzzle. The solution found by the algorithm is guaranteed in fewest steps. The puzzle is based on one of questions at Brilliant.org. Game AI is run on Azure Functions.

About The Puzzle
The puzzle consists of ten coins. Only a pair of adjacent coins is allowed to be flipped over at same time. All ten coins that are head is the goal. Try to solve the puzzle in fewest steps (if any).

To play the live demonstration, click the coins below to edit initial state and hit button to run the algorithm.

Heuristic Function Explanation

As described in Overview, the game AI is implemented in A* search algorithm which estimates each step with the function below:

$f(n) = {g(n) + h(n)}$

where $g(n)$ is the total number of steps needed to reach the current step, and $h(n)$ is the sum of two types of evaluation:

$h(n) = {c(n) + t(n)}$

Both evaluation functions are based on the number of heads. The $c(n)$ is the maximum number of continuity and $t(n)$ is total number of heads.

Examples of evaluation: (Ⓗ is head and Ⓣ is tail)

ⒽⓉⒽⒽⓉⒽⒽⒽⒽⒽ

$c(n) = 5$, $t(n) = 8$

 

ⒽⒽⓉⒽⒽⒽⒽⓉⓉⓉ

$c(n) = 4$, $t(n) = 6$

 

The step that has higher score will be prioritized in the open list, which leads the algorithm to find the solution in fewest steps.

About The Project

The live demonstration is created as an example of Heuristic Suite - an experimental implementation of a series of heuristic algorithms in generic programming. The implementation in console application is also available and can be viewed on GitHub.