Notes on the Bastet algorithm

Version 0.37

The first version, 0.37, has no special algorithm: it just does a carefully hand-written analysis of the top of the well in order to determine which blocks do not fit well, and assigns a score.

Version 0.41

The second version, 0.41, has a score() function that assigns a score to a single position of the game (based on completed rows, average height, number of "holes"). It then tries to drop each possible block straight down in every possible orientation, and assigns a score() to every possible result. Finally, it chooses the block for which the best possible score obtained by dropping it is the lowest. 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. Three major changes:

Also, these results must be adjusted to limit the repetitiveness of the game (you do not want Bastet to give you an endless stream of S-shaped blocks). When there is a repetition, I choose randomly (with decreasing probabilities) the block to give among the worst, second-worst and third-worst block.

Anyway, all of this is pretty standard stuff — people who write chess-playing programs use far more advanced techniques.

Hope this was clear enough. I am writing this for people without a specific background, so I had to be a bit generic; please feel free to write for further explanations.

If you haven't already, check out version 0.43: it is not included in most Linux repositories yet.