Notes on the Bastet algorithm

This page describes how the block choosing algorithm in Bastet works.

Version 0.37

The algorithm in bastet’s first version, 0.37 does a hand-written analysis of the top border of the well in order to determine which blocks do not fit well; for instance, a square “O” block fits well only if there are two consecutive columns with the same height. Based on the results, it assigns a score to each block type.

Then, it selects the block with the worst score 82% of the time, and otherwise chooses at random among the next three (second, third, and quarter). This is done because choosing always the worst block would produce long streaks of the same 1-2 block types (for instance, long sequences of S and Z blocks); this would result in a harder game, but also a more boring one for the player; so we have to compromise between these two goals.

Version 0.41

The second version, 0.41, has a score() function that assigns a score to a single state of the well at a given moment, based on number of completed rows, average height, and number of “holes”. It then tries to drop each of the seven possible block types straight down in every possible orientation, and assigns a score() to every possible result. Then, it chooses the block for which the best possible score obtained by dropping it is the lowest. This is a standard idea in game AI programming: check Wikipedia:Minimax and Wikipedia:Evaluation function for some more detail.

Version 0.43

The third version, 0.43, is an evolution of the previous one. There are three major changes:

This is a rather simple game AI — people who write chess-playing programs use far more advanced techniques. Note that in principle one could extend the same idea and build larger game trees: drop three, four, five… blocks before evaluating the resulting position. In practice, this does not lead to a more challenging game, because most human players do not “plan ahead” long enough for it to make a difference. So we stop at 2.

The probability of dropping each block in 0.43 are as follows: 80% worst block; 12% second-worst; 6% third-worst; 2% fourth-worst. The best three block types are never given. Ties are broken at random.

I hope this description is sufficiently clear for you. Please feel free to inspect the code for more details, or ask me for further explanations.