Monte Carlo Solution to Webbels

Webbels is a toy game that was originally presented to me in one of my computing science classes towards the end of my degree. Essentially, the goal of the game is to match groups of colored balls that are larger than size 2, and get the highest score possible. As the balls are matched, they are deleted from the board, and new boards come in from the left side.

A version of the game can be found here: Skatgame Webbels

My version is shown below, playing a game with a set number of balls, and an 8x8 board.

The code consists of two seperate classes. The first is webbels, which represents the state of the board, and handles actually operating the game itself. I chose to represent the blocks simply as just a list of lists of whatever size the board is. The game itself also has a move counter, score counter, and a few variables to control how the game is played. The Webbels class also contains a few utility functions. One to fill the board, one to find all available moves, another to slide blocks in, another to slide blocks down, and another to slide blocks to the right.

The Monte Carlo class represents the search state for the tree. In this class is where the “Heart” of the AI is. Essentially what a Monte Carlo tree represents is a graph of connected states of the game. Imagine a snapshot of the board taken before and after every move, and then connected together. The Monte Carlo tree should represent every possible state that is reachable from a given position of the game.

So what is a Monte Carlo search? Essentially, what is done is this: using the above tree of game states reachable from the initial state, we look at each state individually. We clone the game state, then apply that move. Then what we do is play the game randomly either until the game ends, or until we have passed our search depth. Then what we do is return the final score after this. Once we’ve done that for every possible move, we chose the one with the highest score and repeat.

What this means is that essentially the game is looking ahead at each move that it could be making, and chosing the one that will give the highest score in the future.

By @Charles in
Tags : #Webbels, #CMPUT396, #Monte Carlo,