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:

better block evaluation function
instead of only dropping each block straight down (which left room for an easy winning strategy: build a horizontal roof with space under it, and the program won't check what there is below!), it drops each block in every legal position available. This is done by building a tree of every position a block can be in while it is falling, and traversing it (this is standard computer science stuff, if you wish to look it up check Wikipedia:Tree and Wikipedia:Depth-first search).
a second algorithm which allows a "next block" preview like in the traditional Tetris: this is done by changing "drop a block in every possible position + evaluate the score() of the result" to "drop two consecutive blocks in every possible position + evaluate the score() of the result". This is computationally more expensive (more positions to evaluate!), but it is still an easy job for a modern processor. The idea is to build a partial game tree of depth 2, check Wikipedia:Game tree .

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.