Brainvita - New Artwork and Improved Brainvita Solver

Brainvita at parlor games has been updated with new artwork. The marbles now look like real marbles rather than just filled circles. You can switch the color of the marble by using the theme (☀) button below the brainvita board.

Brainvita Solver

The original brainvita solver uses a brute force algorithm that recursively tries each move at the current position, and find which tree leads to the least number of marbles left in the end. Because the recursion can be 31 deep, the number of possibilities was so great that it was not feasible to find the "best move". The algorithm uses a 1 second cut-off to stop the evaluation, and return the best move found so far. In practice, this meant that for most early board position, the "best" move will invariably the first move tried, as the subtrees containing the alternative moves were never evaluated.

The "new" solver makes the following improvements:

1. Memoization: when a particular board position is encountered during evaluation, we remember the best result that we obtained for it, and store it in an array. If the same position is encountered -later, we don't need to re-compute the answer, and simply look it up. As there are roughly 2^33 distinct positions, we have to limit how many positions we remember. After a bit of trial and error, remembering the "most recently used" 100,000 positions gave a good balance between storage needs and efficiency. With this combination, the hit rate of the result cache was nearly 75%!
2. Orphan Marbles: Even with the speedup obtained by Memoization, the number of possibilities is still too large. We now look at how many "orphan" (not adjacent to any other marbles) are there. Positions with too many (current cutoff is 6) orphan marbles are unlikely to yield a good result, so we skip evaluating the trees that begin with such unfavorable positions.

You can use the hint (💡) button to have the computer play a single move, or click the computer (💻) button to have the computer play till the end. When the there are no more moves left, the rematch (↺) button will appear, and you can use it to reset the board to the initial position.

Even after the two optimizations described above, we cannot completely be assured that the best solution is found from an arbitrary starting position, so there is still scope for improvements. If anyone has suggestions for improving the solver, please let me know in the comments.