Deep Select

After reading about recursion and stack frames, I decided that I'd re-implement a computer strategy game. This fun game has various implementations and various names, including Chain Reaction and Atom Smasher. However, few, if any, have implemented a network version with the game logic written in MySQL stored procedures.

This strategy game is addictive, hard to describe and simple to play. The board consists of a number of territories. The objective is to win all of the territory. Players gain territory by placing counters in territories, one per turn. Once a territory is claimed by a player, a competing player cannot claim the territory directly. Instead, when a player's turn causes counters to exceed the number of adjacent territories then counters are redistributed among adjacent territories and the adjacent territory is gained by the player. (In some implementations, this threshold condition occurs when counters equal rather than exceed.) During a game, the overspill situation often occurs recursively. Indeed, this is the crux of the game and it causes the state of play to swing rapidly. In this regard, the game is comparable to Orthello, also known as Reversi. However, the complexity of Chain Reaction is such that a player can win with the most unlikely move.

Before you begin, you need to add the following to /etc/my.cnf and re-start MySQL Server 5.0 to enable recursive stored procedures:

[mysqld]
max_sp_recursion_depth=256

Next we consider the board and the game engine. In trivial implementations, the board is a square grid. In more advanced versions, the grid may have holes. Furthermore, the board can be *huge*. I've played on boards which were 20×20 cells. It would be typical to implement these boards as a two dimensional array in a desktop application. The MySQL implementation will be a directed graph of arbitrary cells. That means we can form 2D grids and other more exotic arrangements by numbering the cells and describing their relationships. At present, the schema doesn't represent the cells graphically:

DELIMITER //

CREATE SCHEMA chain //
USE chain //

CREATE TABLE cell (
id INT PRIMARY KEY,
user INT NOT NULL DEFAULT 0,
count INT NOT NULL DEFAULT 0,
max INT NOT NULL DEFAULT 2
) //

CREATE TABLE adj (
`from` INT NOT NULL,
`to` INT NOT NULL
) //

CREATE PROCEDURE inc (IN user0 INT, IN node INT, IN depth INT, IN total INT)
BEGIN
DECLARE sum INT;
DECLARE count0 INT;
DECLARE max0 INT;
DECLARE done INT DEFAULT 0;
DECLARE buddy INT;
DECLARE cur1 CURSOR FOR SELECT `to` FROM adj WHERE `from`=node;
DECLARE CONTINUE HANDLER FOR SQLSTATE '02000' SET done=1;
#SELECT "1",user,node,depth,total;
IF depth<64 THEN
#SELECT "2";
 SELECT COUNT(*) INTO sum FROM cell;
 IF sum<total THEN
   SELECT count, max INTO count0, max0 FROM cell WHERE id=node LIMIT 1;
#SELECT "3",count0,max0;
   IF count0<max0 THEN
#SELECT "4";
     UPDATE cell SET user=user0, count=count0+1 WHERE id=node;
   ELSE
     UPDATE cell SET user=user0, count=1 WHERE id=node;
     OPEN cur1;
     REPEAT
       FETCH cur1 INTO buddy;
       IF NOT done THEN
         CALL inc (user0,buddy,depth+1,total);
       END IF;
     UNTIL done END REPEAT;
     CLOSE cur1;
   END IF;
 END IF;
END IF;
END //

Writing the stored procedure wasn't easy but you can see my debug technique from the commented statements. Anyhow, to test this recursion, we'll create a trivial board with two cells:

INSERT INTO cell (id,user,count,max) VALUES (0,0,0,4) //
INSERT INTO cell (id,user,count,max) VALUES (1,0,0,4) //

INSERT INTO adj (`from`,`to`) VALUES (0,1) //

If you make repeated calls to the stored procedure and select results then you'll confirm that counters spill from cell 0 to cell 1:

CALL inc (1,0,0,256) //
SELECT * FROM cell //

However, the total number of counters in the system doesn't always increase. We'll fix that in a future article.

# posted by Dean Swift @ 10:50 am