Keys:
← : move piece left
→ : move piece right
↓ : drop piece
Z : rotate piece counter-clockwise
↑ or X : rotate piece clockwise
⌘R : reset game
The KRIEG series of prototypes are probably the oldest of my projects which will run on machines not now found for sale only on eBay, being the first projects I developed when I was teaching myself SDL* back in 2003; the KRIEG series of prototypes are quick-and-dirty clones of Puyo Puyo with an AI bolted on top; whilst playable, the prototypes were developed not to be good games, but to be test-beds for several ideas for AIs I was entertaining at the time…
The difference between KRIEG3 {video|source code & compiled:Mac OS X} and the earlier prototypes in the series is that this prototype is capable of creating chains.
A chain is comprised of cells which must be filled by blocks of the correct colour; one of those cells must be filled last, the filling of that last cell resulting in the complete elimination of the chain, eg.
A cell in the chain cannot be adjacent to a similarly coloured block which is not part of the chain, as that could result in the chain being prematurely, and possibly incompletely, eliminated.
The differences between KRIEG3 and the later prototypes in the series are: that the chains in this prototype are predefined (refer to the file ai3_patterns.hll), not learnt; that the chains in this prototype use predefined colours (ibid), not colours determined through analysis of the playfield to not cause the chain to be prematurely, and possibly incompletely, eliminated by adjacent blocks which are not part of the chain; and that the chains in this prototype are created fresh, the playfield is not analysed to determine whether any existing blocks can be used in the chain.
If the AI is not trying to create a chain (such as if there is not enough free space in the playfield for any of the predefined chains to fit into), the prototype falls back to using an improved version of the AI from KRIEG; whether to use the KRIEG or the KRIEG3 AI is reevaluated every time a piece is spawned under the control of the AI player.
The chain that the AI is trying to create is rendered as a slightly transparent overlay to the AI player’s playfield.
With regards to the KRIEG3 AI…
- If the AI has not selected a chain to try to create, a list of the free space in the AI player’s playfield is created, eg. for the playfield below the list would contain the nodes (in the format
[leftmost X-coordinate, width:height]) [0, 1:6], [1, 2:4], [2, 1:4], [3, 1:5], and [5, 1:6];
- traversing that list, the AI creates a second list, of those chains which could fit in the free space without having any adjacent blocks of colours which could cause the premature, and possibly incomplete, elimination of the chain;
- if there are any chains in that second list, the AI selects at random from that list a chain to try to create; if there are not, the prototype reverts to using an improved version of the AI from KRIEG;
- a prediction is made in much the same manner as in the AI from KRIEG, where a duplicate of the AI player’s playfield is created, the piece under the AI player’s control is attached to that duplicate playfield at the correct X-coordinate and with the correct rotation for the prediction, and that duplicate playfield is updated as the original would be, with blocks being dropped and eliminated until no more changes will occur within the duplicate playfield without the attachment of another piece;
- several values are then passed back to the AI: whether the attachment of the piece under the AI player’s control to that duplicate playfield exceeded the height of that playfield, which would result in gameover for the AI player; whether the prediction was ‘illegal’, viz., whether the prediction resulted in a cell of the chain being filled by a block of an incorrect colour, or a block not part of the chain coming to rest adjacent to a similarly coloured cell of the chain; the ‘legality’ of the prediction (a prediction which has more of its cells filled by blocks of the correct colour has a higher ‘legality’); and whether the prediction resulted in the completion of the chain;
- a. if every cell in the chain has been filled by a block of the correct colour but the last, and if there is a prediction which results in that last cell being filled by a block of the correct colour, which is not ‘illegal’, and which does not result in gameover for the AI player, the AI takes the X-coordinate and rotation of that prediction as its targets, attempting to move/rotate the piece under the AI player’s control to that X-coordinate and that rotation.
b. if there are any predictions which have a non-zero ‘legality’, are not ‘illegal’, and do not result in gameover for the AI player, a list is created containing that prediction with, or those predictions which share, the highest ‘legality’; the AI then selects a random prediction from that list, and takes the X-coordinate and rotation of that prediction as its targets, attempting to move/rotate the piece under the AI player’s control to that X-coordinate and that rotation.
c. if the targets for the AI cannot be set in 6a. or 6b., the targets for the AI are set in much the same manner as using the AI from KRIEG: a list is created containing those predictions which have a ‘legality’ of zero (so as not to affect the chain the AI is trying to create), are not ‘illegal’, and do not result in gameover for the AI player; the AI then selects a random prediction from that list, and takes the X-coordinate and rotation of that prediction as its targets, attempting to move/rotate the piece under the AI player’s control to that X-coordinate and that rotation.
With regards to the modified KRIEG AI…
- For every possible combination of piece X-coordinate and rotation, a prediction is made, resulting in a score for attaching the piece under the AI player’s control to the playfield at that X-coordinate and with that rotation, and – in an improvement on the AI from KRIEG – a flag indicating whether the attached piece exceeded the height of the playfield, which would result in gameover for the AI player;
- when predictions for every possible combination of piece X-coordinate and rotation have been made, the AI creates a list containing that prediction with, or those predictions which share, the highest score and do not result in gameover for the AI player, and – in an improvement on the AI from KRIEG – selects a random prediction from that list; with a prediction selected, the AI takes the X-coordinate and rotation of that prediction as its targets, and attempts to move/rotate the piece under the AI player’s control to that X-coordinate and that rotation.
With regards to the predictions made by the modified KRIEG AI…
- A prediction is made by creating a duplicate of the AI player’s playfield, and attaching the piece under the AI player’s control to that duplicate playfield at the correct X-coordinate and with the correct rotation for the prediction;
- that duplicate playfield is then updated as the original would be, with blocks being dropped and eliminated until no more changes will occur within that duplicate playfield without the attachment of another piece;
- several values are then passed back to the AI: the height of the highest column in that duplicate playfield; the total number of blocks eliminated from that duplicate playfield; the number of blocks of the same colour in the groups formed by the attachment of the piece under the AI player’s control to that duplicate playfield; and – in an improvement on the AI from KRIEG – a flag indicating whether the attachment of the piece under the AI player’s control to that duplicate playfield exceeded the height of that duplicate playfield, which would result in gameover for the AI player;
- the score for the prediction is then determined by multiplying those first three values passed back to the AI by the importance of those values to the AI’s decision-making process, summing the latter two values, and subtracting the first value from that sum.
(I’ll note that there is at least one bad bug in KRIEG3, a potentially long-to-infinite loop in kriegPlayfield::Spawn(); that bug has never triggered on any of the occasions I’ve used KRIEG3, but it is there…)
KRIEG3 was developed on an Apple iMac DV (Summer 2000) in C++ using SDL*, OpenGL, and sealfin*, compiled with Apple Xcode 1.1.
