This page describes how the block choosing algorithm in Bastet works.
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.
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.
The third version, 0.43, is an evolution of the previous one. There are three major changes:
score().score() of the result” to “drop two blocks (the one in the next block preview, and then another one) 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 again a standard one from AI programming: we build a partial game tree of depth 2, check Wikipedia:Game tree. The version with block preview is called “normal version”, the one without it “harder version”.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.