Software writing software
My academic research relates to software automation – for me that means code writing code. Most code generators today are pretty stupid, though. My hypothesis is basically that software should be able to learn from experience so that it can not only generate tedious code, but also discover algorithms based on results of code execution. So, my goal isn’t just to develop software that generates mundane code components like simple data classes or default stored procedures, but build generators that learn from examining the environment along with trial and error in order to write intelligent systems.
To illustrate this point, I am using Towers of Hanoi as a proof-of-concept of a very simple example for how software can learn an algorithm and then write code that includes the algorithm for a problem domain. The recursive algorithm for solving towers of Hanoi is rather simple – see http://www.cs.cmu.edu/~cburch/survey/recurse/hanoiimpl.html. I found an example in C# for solving the puzzle using the recursive algorithm at http://azerdark.blogspot.com/2008/07/c-tower-of-hanoi.html
Here is a walk-through:
Let Hn = # moves for a stack of n disks.
Here is the optimal strategy:
Move top n−1 disks to spare peg. (Hn−1 moves)
Move bottom disk. (1 move)
Move top n−1 to bottom disk. (Hn−1 moves)
Note that: Hn = 2Hn−1 + 1
The # of moves is described by the below recurrence relation:
Solving Tower of Hanoi RR
Hn = 2 Hn−1 + 1
= 2 (2 Hn−2 + 1) + 1 = 22 Hn−2 + 2 + 1
= 22(2 Hn−3 + 1) + 2 + 1 = 23 Hn−3 + 22 + 2 + 1
…
= 2n−1 H1 + 2n−2 + … + 2 + 1
= 2n−1 + 2n−2 + … + 2 + 1 (since H1 = 1)
=
= 2n − 1
The code is fairly trivial:
procedure Hanoi(n: integer; source, dest, by: char);
Begin
if (n=1) then
writeln('Move the plate from ', source, ' to ', dest)
else begin
Hanoi(n-1, source, by, dest);
Hanoi(1, source, dest, by);
Hanoi(n-1, by, dest, source);
end;
End;
But, suppose I didn’t know the algorithm and I want to write code that can discover the algorithm for the game (or potentially any other game) by simply playing the game and looking for patterns. To do such a task requires a framework for capturing the moves and analyzing the states of all the pieces (variables) involved. The framework also needs to be able to know the rules are for performing the moves and how to determine if victory is achieved. In order to do this, I could have targeted the Hanoi puzzle specifically, but I want a framework that will work for potentially any game.
Enter the Gaming Automation Framework (GAF). To build this framework, I utilize SQL Server 2008 as my storage engine as well as leveraging functions and triggers in order to support a schema that not only supports playing the game, but also enforces rules on a game-by-game basis and supports functions for checking the status of a game as well as dictating the best moves.
Here is an overview of the GAF Components:
- Game Instantiation SQL Server Database
- Schema for game definitions and instantiation of games
- Database trigger framework for invoking functions enforcing rules that are specific to the game being played and for recording state of the game after each move.
- Stored procedures for creating games, game instances, performing moves, and undoing moves.
- Database function framework for defining what constitutes a valid move and what state arrangement defines success (i.e. winning the game).
- Game Player/Solver windows form
- Specification of the game to play along with the number of variable instantiations (i.e. for tower of Hanoi we might chose 3 disks, 4 disks, 5 disks, etc. For checkers we might chose 8 or 12 pieces, etc.)
- Function to play game using depth-first-search (DFS) to probe all moves in order to generate a solution.
- Function to analyze the game moves and determine a pattern and generate code to automatically solve the game (I’m still working on this part).
Let’s step through the major components:
Below are the schemas for game and game variable. Currently this only supports contiguous value check for the variables. I plan to improve this by allowing a discrete ranges to be associated with the variables.
CREATE TABLE [Games].[Game](
[GameId] [int] IDENTITY(1,1) NOT NULL,
[GameName] [varchar](50) NOT NULL,
[MoveRuleFunctionName] [varchar](256) NOT NULL,
–- function to get list of valid moves
[GameStatusFunctionName] [varchar](256) NOT NULL,
–- function to check if game over/won/lost
[BestMoveRuleFunctionName] [varchar](256) NULL,
CONSTRAINT [PK_Game_1] PRIMARY KEY CLUSTERED
(
[GameId] ASC
))
CREATE TABLE [Games].[GameVariable](
-- The “domain” of pieces”
[GameId] [int] NOT NULL,
[VariableId] [int] IDENTITY(1,1) NOT NULL,
[VariableName] [varchar](50) NOT NULL,
[MinInstances] [int] NOT NULL, -- Mininum number of “pieces”
[MaxInstances] [int] NOT NULL, – Max number of pieces.
[SimulationInstances] [int] NOT NULL,
-– This is the number of brute force simulations
-- to perform in order to find a solution, not currently using.
[MinValue] [int] NOT NULL,
–- min value or (range) (i.e. 1 for peg 1 for Hanoi
-- that the piece interacts with
[MaxValue] [int] NOT NULL,
–- max value (i.e. 3 for Hanoi for peg 3
[StartValue] [int] NOT NULL,
-- staring value of the piece – i.e. peg 1 for Hanoi
CONSTRAINT [PK_GameVariable] PRIMARY KEY CLUSTERED
(
[VariableId] ASC
)
So for the Tower of Hanoi, we define 3 variable rows to represent the disks and use the min and max value to control what peg the disks may be placed on.
Game Table Data:
The game table provides a level of abstraction from the specific game by storing metadata about how to play the game, check the status, and win the game in terms of the names of the functions. This allows multiple games to be setup with different rules. The simulation engine can then evaluate for a particular instance of a game which functions apply.
Games.GameVariable
The game variable relates to the game table and provides information on the variables to be used. I use the terms “variable”/“domain”/”game piece” and “domain”, ”value”, “location” interchangeably not just to confuse you, but because these are different ways to think of these entities depending on the type of scenario we are solving for. However, they are analogous and represent the mapping of a variable-value assignment. This could be a game piece/location, but could represent other types of domain/range pairs.
For our tower of Hanoi example, we only use a single variable to represent the disk and use the instance fields to control how many disks there are. In a a game where there are different types of pieces, separate variables would be created. To represent the valid states of the variable – we utilize start value to represent starting position, final value to represent winning position, and min and max to control the range of values. I plan to improve this so that not only can a range of values, but so that discrete sets of values can be used. For Tower of Hanoi, however this suffices.
Here are the tables used to support instances of the game. Note the use of the columns to store game-state for each move. This is the key component used for the automation aspect in order to discover patterns and translate into a solution algorithm.
CREATE TABLE [Games].[Instance](
[InstanceId] [int] IDENTITY(1,1) NOT NULL,
[GameId] [int] NOT NULL,
[GameDescription] [varchar](255) NULL,
[VariableInstanceCount] [int] NOT NULL,
[DomainStates] [varchar](max) NULL,
-– Each char represents a move and the value in the character
-- is the variable moved. (i.e. disk number)
[RangeStates] [varchar](max) NULL,
-– Each char represents a move and the value in the character
-- is the value mapped to the moved variable (i.e. peg)
[GameStatus] AS ([games].[fn_CheckHanoiGameStatus]([InstanceId],(1))),
CONSTRAINT [PK_GameInstance] PRIMARY KEY CLUSTERED
(
[InstanceId] ASC
))
CREATE TABLE [Games].[InstanceMove](
[InstanceMoveId] [int] IDENTITY(1,1) NOT NULL,
[MoveNumber] [int] NULL,
[InstanceId] [int] NOT NULL,
[InstanceVariableId] [int] NOT NULL,
-- The “piece” that was moved
[InstanceVariableValue] [int] NOT NULL,
-– The “location” that piece moved to
CONSTRAINT [PK_GameMove] PRIMARY KEY CLUSTERED
(
[InstanceMoveId] ASC
))
CREATE TABLE [Games].[InstanceVariable](
-- Current value for the piece (“domain" or variable)
-- and location (“range” or value)
[InstanceVariableId] [int] IDENTITY(1,1) NOT NULL,
[VariableId] [int] NOT NULL,
[InstanceId] [int] NOT NULL,
[VariableCurrentValue] [int] NOT NULL,
[InstanceVariableNumber] [int] NOT NULL,
CONSTRAINT [PK_MovePosition] PRIMARY KEY CLUSTERED
(
[InstanceVariableId] ASC
))
CREATE TABLE [Games].[InstanceVariableValueStates](
-- One per combination of domain and range (piece/location)
[InstanceId] [int] NOT NULL,
[InstanceVariableNumber] [int] NOT NULL,
[InstanceVariableValue] [int] NOT NULL,
[MoveStates] [varchar](max) NOT NULL,
–- Bit mask indicating if the variable
-- was moved on the bit corresponding to the move to the specified value.
CONSTRAINT [PK_InstanceVariableValueStates] PRIMARY KEY CLUSTERED
(
[InstanceId] ASC,
[InstanceVariableNumber] ASC,
[InstanceVariableValue] ASC
-- Please don’t get mad I’m using a compound primary key instead of generating
–- a surrogate, think of this as mainly a logical design at this point…
)
Here is the relationship diagram that shows how games and game instances inter-relate. The game instance is just that – an instance of a game, we could have multiple instances per games. Note that this isn’t a perfectly normalized design, some redundancy has been put in to avoid having to write complex queries to link game moves and their variables states back to the instance. We can clean that up later.
A trigger automatically sets the move number and sets the values in the Instance InstanceVariable after each move as well as performing some other tasks that we will get into later. Having the latest instance variable value is handy for processes that involve checking rules, etc, because they are interested in the latest state. They are usually interested in the prior state, also, so I’ll probably enhance this to store the prior value as well.
CREATE TRIGGER [Games].[InstanceMove_ITrig]
ON [Games].[InstanceMove]
AFTER INSERT
AS
BEGIN
DECLARE @InstanceId INT
DECLARE @InstanceVariableNumber INT
DECLARE @InstanceVariableValue INT
DECLARE @LastVariableNumber INT = –1
-- To force variable to be evaluated as null
DECLARE @OldVariableValue INT
DECLARE @InstanceMoveId INT
DECLARE @CustomErrorMessage varchar(255)=''
SET XACT_ABORT ON
BEGIN TRANSACTION
BEGIN TRY
-- Get variable information
SELECT
@InstanceId = INSERTED.InstanceId ,
@InstanceMoveId = INSERTED.InstanceMoveId,
@InstanceVariableValue= INSERTED.InstanceVariableValue,
@InstanceVariableNumber = iv.InstanceVariableNumber
FROM INSERTED
INNER JOIN Games.InstanceVariable iv
ON iv.InstanceVariableId = INSERTED.InstanceVariableId
IF (SELECT COUNT(*) FROM Games.InstanceMove
WHERE InstanceId = @InstanceID) > 1
BEGIN
SELECT TOP 1 @LastVariableNumber = InstanceVariableNumber
FROM Games.InstanceMove im
INNER JOIN Games.InstanceVariable iv
ON im.InstanceVariableId
= iv.InstanceVariableId
WHERE im.InstanceId = @InstanceId
AND im.InstanceMoveId <> @InstanceMoveId
ORDER BY MoveNumber DESC
END
-- Set move number
UPDATE [Games].[InstanceMove]
SET MoveNumber =
(SELECT COUNT(*) FROM [Games].[InstanceMove]
WHERE InstanceId = INSERTED.InstanceId)
FROM INSERTED
WHERE INSERTED.InstanceMoveId = InstanceMove.InstanceMoveID
-- TODO: This part of the code is currently specific to Tower of Hanoi,
need to use the MoveResultStatus in order
-- to check if this is a bad move and use the mappings to display
-- the error message. That will
-- allow this trigger to work for any game, not just Tower of Hanoi.
DECLARE @MoveResult INT -- 1 if valid, 0 if invalid, -1 if
-- no more moves left
SET @MoveResult = Games.fn_CheckHanoiMove
(@InstanceId, @InstanceVariableNumber,@InstanceVariableValue,
@LastVariableNumber,
@OldVariableValue, 1)
IF @MoveResult <= –2
-- Ignore -1 error, since that means we just now ran out of moves,
just need to error out if we have used up all moves
BEGIN
SET @CustomErrorMessage = 'Invalid Move: ' +
(CASE
WHEN @MoveResult = -6 THEN 'Out of Moves'
WHEN @MoveResult = -2 THEN 'Destination peg '
+ CONVERT(VARCHAR(2),@InstanceVariableValue)
+ ' has a smaller disk on it already than disk '
+ CONVERT(VARCHAR(2),@InstanceVariableNumber)
WHEN @MoveResult = -3 THEN 'Source peg '
+ CONVERT(VARCHAR(2),@OldVariableValue)
+ ' has a smaller disk on top than disk '
+ CONVERT(VARCHAR(2),@InstanceVariableNumber)
WHEN @MoveResult = -4 THEN 'Disk '
+ CONVERT(VARCHAR(2),@InstanceVariableNumber)
+ ' moved to same peg '
+ CONVERT(VARCHAR(2),@InstanceVariableValue) + ' as it is already on'
WHEN @MoveResult = -5 THEN 'Disk '
+ CONVERT(VARCHAR(2),@InstanceVariableNumber)
+ ' moved twice in a row'
WHEN @MoveResult = -7 THEN
'Biggest disk Must be moved to center peg at the game point in order to win '
END)
RAISERROR (@CustomErrorMessage,16,1)
END
-- Update Instance Variable
UPDATE Games.InstanceVariable
SET VariableCurrentValue = Inserted.InstanceVariableValue
FROM INSERTED
INNER JOIN Games.InstanceVariable IV
ON IV.InstanceVariableId = INSERTED.InstanceVariableId
-- Update bit masks for moves
UPDATE Games.InstanceVariableValueStates
SET MoveStates = COALESCE(MoveStates,'') + '1'
WHERE InstanceId = @InstanceId
AND InstanceVariableNumber = @InstanceVariableNumber
AND InstanceVariableValue= @InstanceVariableValue
UPDATE Games.InstanceVariableValueStates
SET MoveStates = COALESCE(MoveStates,'') + '0'
WHERE InstanceId = @InstanceId
AND NOT (InstanceVariableNumber = @InstanceVariableNumber
AND InstanceVariableValue= @InstanceVariableValue)
UPDATE Games.Instance
SET
DomainStates = COALESCE(DomainStates + ',','')
+ CONVERT(VARCHAR(2),@InstanceVariableNumber),
RangeStates = COALESCE(RangeStates + ',','')
+ CONVERT(VARCHAR(2),@InstanceVariableValue)
WHERE InstanceId = @InstanceId
COMMIT TRANSACTION
There are 4 stored procedures used to play the game
- InsertInstance – Creates a new game. Based on the passed-in number of instances which gets set on the Game, Instance variables are generated by the trigger.
- InsertMove – Inserts a new move which then results in the execution of the InstanceMove_ITrig trigger above. Returns back the status of the game.
- UndoMove – Rolls back a move. This is used when the simulator plays a “loosing” move and allows the simulator to try all different game combinations without having to start all over when hitting a dead-end.
- GetInstanceStates – Gets the state data from the Instance table for a particular game instance. The states can then be analyzed for patterns to automate solution discovery.
These are all simple stored procedures with the exception of the UndoMove:
CREATE PROCEDURE [Games].[UndoLastMove]
-- Add the parameters for the stored procedure here
@InstanceId INT
AS
BEGIN
SET NOCOUNT ON
SET XACT_ABORT ON
DECLARE @MoveNumber INT = 0
SELECT @MoveNumber = COUNT(*) FROM Games.InstanceMove
WHERE InstanceId= @InstanceId
IF @MoveNumber = 0
BEGIN
RETURN -- Nothing to do
END
BEGIN TRANSACTION
BEGIN TRY
-- Identify the variable and value affected by the last move
-- and the last move id
DECLARE @InstanceVariableId INT = 0
DECLARE @InstanceVariableValue INT = 0
DECLARE @InstanceMoveId INT = 0
DECLARE @PriorInstanceVariableValue INT = 0
-- Find the current variable and value affected
SELECT @InstanceVariableId = InstanceVariableId,
@InstanceVariableValue = InstanceVariableValue,
@InstanceMoveId = InstanceMoveId
FROM Games.InstanceMove
WHERE InstanceId = @InstanceId
AND MoveNumber = @MoveNumber
-- Delete the move
DELETE FROM Games.InstanceMove
WHERE InstanceId = @InstanceId
AND InstanceMoveId = @InstanceMoveId
-- Find the prior value for the variable, since the most current
-- is now deleted
SELECT TOP 1 @PriorInstanceVariableValue =
(CASE WHEN InstanceVariableValue IS NULL THEN gv.StartValue
ELSE InstanceVariableValue END)
FROM Games.GameVariable gv
INNER JOIN Games.InstanceVariable iv
ON iv.VariableId = gv.VariableId
LEFT JOIN Games.InstanceMove im
ON im.InstanceVariableId = iv.InstanceVariableId
WHERE iv.InstanceId = @InstanceId
AND iv.InstanceVariableId = @InstanceVariableId
ORDER BY MoveNumber DESC
-- Drop the last state from Games.Instance
UPDATE Games.Instance
SET DomainStates =
(CASE WHEN @MoveNumber > 1
THEN SUBSTRING(DomainStates,1,DATALENGTH(DomainStates) -
CHARINDEX(',',REVERSE(DomainStates)))
ELSE NULL END),
RangeStates =
(CASE WHEN @MoveNumber > 1
THEN SUBSTRING(RangeStates,1,DATALENGTH(RangeStates) -
CHARINDEX(',',REVERSE(RangeStates)))
ELSE NULL END)
WHERE InstanceId = @InstanceId
-- Drop the last bit all the Games.InstanceVariableValueStates
UPDATE Games.InstanceVariableValueStates
SET MoveStates =
(CASE WHEN @MoveNumber > 1 THEN SUBSTRING(MoveStates,1,
@MoveNumber -1) ELSE '' END)
WHERE InstanceId = @InstanceId
-- Correct the current value on InstanceVariable
UPDATE Games.InstanceVariable
SET VariableCurrentValue = @PriorInstanceVariableValue
WHERE InstanceVariableId = @InstanceVariableId
COMMIT TRANSACTION
END TRY
BEGIN CATCH
ROLLBACK TRANSACTION
EXECUTE usp_GetErrorInfo
END CATCH
END
CREATE FUNCTION [Games].[fn_CheckHanoiGameStatus]
(
-- Add the parameters for the function here
@InstanceId INT,
@PostMoveCheck bit = 0
)
RETURNS INT
AS
BEGIN
-- Declare the return variable here
-- -1 = Game lost, 0 = Undecided, 1 = Game won, -2 = Game not started
DECLARE @ResultVar INT = 0
DECLARE @NumberOfDisks INT = 0
DECLARE @NumberOfMoves INT = 0
DECLARE @NumberOfDisksOnLastPeg INT = 0
DECLARE @MaxMoves INT = 0;
DECLARE @LastMoveVariableId INT = 0;
DECLARE @TwoMovesBackVariableId INT = 0;
DECLARE @MinVariableId INT = 0
SELECT @NumberOfMoves = COUNT(*) FROM Games.InstanceMove
WHERE InstanceId = @InstanceId
-- SELECT @NumberOfDisks = COUNT(*) FROM Games.InstanceVariable
-- WHERE InstanceId = @InstanceId
SELECT @NumberOfDisks = VariableInstanceCount, @MaxMoves =
(POWER(2,@NumberOfDisks) - 1)
FROM Games.Instance
WHERE InstanceId = @InstanceId
SELECT @MinVariableId = MIN(InstanceVariableId)
FROM Games.InstanceVariable
WHERE InstanceId = @InstanceId
IF @PostMoveCheck = 1
BEGIN
SELECT @TwoMovesBackVariableId = InstanceVariableId
FROM Games.InstanceMove im
WHERE MoveNumber = (@NumberOfMoves - 2)
AND InstanceId = @InstanceId
SELECT @LastMoveVariableId = InstanceVariableId
FROM Games.InstanceMove
WHERE MoveNumber = @NumberOfMoves
AND InstanceId = @InstanceId
END
DECLARE @IsBigDiskOnLastPegYet BIT = 0
SELECT @IsBigDiskOnLastPegYet = COUNT(*)
FROM Games.InstanceVariable
WHERE InstanceVariableNumber = @NumberOfDisks
AND VariableCurrentValue = 3
AND InstanceId = @InstanceId
SELECT @NumberOfDisksOnLastPeg = COUNT(*) FROM Games.InstanceVariable
WHERE InstanceId = @InstanceId AND VariableCurrentValue = 3
-- Check for moves less than 2 raised to number of disks and for all disks
-- on the correct peg. The rules function keeps disks from being put on in
-- the wrong order.
DECLARE @NumberOfMovesLeft INT = @MaxMoves - @NumberOfMoves
IF @NumberOfMoves < POWER(2,@NumberOfDisks)
AND (@NumberOfDisksOnLastPeg = @NumberOfDisks)
BEGIN
SET @ResultVar = 1
END
ELSE BEGIN
DECLARE @MidPointMoves INT = ((@MaxMoves + 1) /2)
IF @NumberOfMoves > @MidPointMoves
BEGIN
IF NOT EXISTS
(SELECT 0 FROM Games.InstanceMove im
INNER JOIN Games.InstanceVariable iv
ON im.InstanceVariableId = iv.InstanceVariableId
AND iv.InstanceVariableNumber = @NumberOfDisks
AND im.InstanceVariableValue = 3
AND im.MoveNumber = @MidPointMoves)
BEGIN
RETURN -1
END
END
IF
(@NumberOfMoves + @NumberOfDisks - @NumberOfDisksOnLastPeg) > @MaxMoves
-- @NumberOfMoves > POWER(2,@NumberOfDisks - @NumberOfDisksOnLastPeg) - 1
-- Big diks must reach be on third peg by half of the remaining moves
OR (@IsBigDiskOnLastPegYet = 0 AND @NumberOfMoves >
(POWER(2,@NumberOfDisks)/2) -1)
-- OR (@NumberOfMovesLeft > (POWER(2,@NumberOfDisks - @NumberOfDisksOnLastPeg)
- POWER(2,@NumberOf))
-- Every other move must be the smallest peg
OR (@TwoMovesBackVariableId <> @LastMoveVariableId
AND @MinVariableId = @TwoMovesBackVariableId AND @PostMoveCheck =1)
-- The big disk must move to the center peg at the midpoint of the game.
BEGIN
SET @ResultVar = -1
END
END
RETURN @ResultVar
END
Ultimately, I’d like to eliminate the use of the functions altogether and “schematize” this. That is, the rules and game status should be represent-able within a generic schema. This would allow the user to be able to create any game through a generic interface rather than requiring the development of a function. Based on the fact that the rules and status are completely based on states of entities and their inter-relationships, it should be possible to create a schema to represent this.
Below are the functions used for the game move/game status. Although these functions are specific to the game, they are defined at the game level and the intent is to execute them dynamically in the game engine based on the game selected. Therefore, we are still able to have a generic framework for doing the game even though we have create domain-specific code.
The below code does cheat a little bit – it has a couple of “hints” to prevent non-productive moves and terminate the game early. For example, if the user doesn’t move (or can’t move) the bottom disk on the middle peg in the middle move, we know that the game is lost. (we define losing as not solving the puzzle in the minimum moves). We also don’t let the same move to be reversed, since again that means the optimal moves can’t be achieved. These hints can be picked up through examining the winning pattern, and my long-term goal is for these to be incorporated into the “hinting” aspect of the simulator rather than having to be defined ahead of time.
REATE FUNCTION [Games].[fn_CheckHanoiMove]
(
-- Add the parameters for the function here
@InstanceId int,
@VariableNumber int,
@VariableValue int,
@LastVariableNumber int = NULL,
@OldVariableValue int = NULL,
@PostCheck bit = 0
)
RETURNS INT
AS
BEGIN
-- Declare the return variable here
-- 0 = Move Invalid
-- -1 = Game over - out of moves
-- 1 = Move Valid
DECLARE @ResultVar INT = 1
DECLARE @NumberOfDisks INT = 0
IF @LastVariableNumber IS NULL
BEGIN
SELECT TOP 1 @LastVariableNumber = InstanceVariableNumber
FROM Games.InstanceMove im
INNER JOIN Games.InstanceVariable iv
ON im.InstanceVariableId
= iv.InstanceVariableId
WHERE im.InstanceId = @InstanceId
ORDER BY MoveNumber DESC
END
IF @OldVariableValue IS NULL
BEGIN
SELECT @OldVariableValue = VariableCurrentValue
FROM Games.InstanceVariable
WHERE InstanceVariableNumber = @VariableNumber
AND InstanceId = @InstanceId
END
-- Represents the peg that we were on before
SELECT @NumberOfDisks = VariableInstanceCount FROM Games.Instance
WHERE InstanceId = @InstanceId
-- Validate that there is not already a peg with the disk
-- which is a lower number disk
-- (Disks are numbered from 1 to N with 1 as the top disk)
IF (SELECT COUNT(*) FROM Games.InstanceMove
WHERE InstanceId = @InstanceId) = (POWER(2,@NumberOfDisks) - 1 )
BEGIN -- No more moves after this one
SET @ResultVar = -1
END
IF (SELECT COUNT(*) FROM Games.InstanceMove
WHERE InstanceId = @InstanceId) > (POWER(2,@NumberOfDisks) - 1 )
BEGIN -- No more moves
SET @ResultVar = -6
END
ELSE BEGIN
-- Check that destination peg does not already have a smaller peg on it
IF ((SELECT COUNT(*) FROM Games.InstanceVariable
WHERE VariableCurrentValue = @VariableValue
AND InstanceVariableNumber< @VariableNumber
AND InstanceId = @InstanceId) > 0)
BEGIN
SET @ResultVar = -2 -- Destination peg has a bigger disk on it
END
ELSE BEGIN
-- Check that this disk was the top disk on the move-from peg
IF ((SELECT COUNT(*) FROM Games.InstanceVariable
WHERE InstanceVariableNumber < @VariableNumber
AND VariableCurrentValue = @OldVariableValue
AND InstanceId = @InstanceId) > 0)
BEGIN
SET @ResultVar = -3
-- Source peg had a smaller disk on it.
END
ELSE BEGIN
IF (@VariableValue = @OldVariableValue)
-- Move must change the position
BEGIN
SET @ResultVar = -4 -- Disk moved to same peg
END
ELSE BEGIN
IF (@LastVariableNumber = @VariableNumber AND NOT
@LastVariableNumber IS NULL)
BEGIN
-- Don't allow nonsense move
-- Moved same piece twice in a row
SET @ResultVar = -5
END
ELSE BEGIN
DECLARE @NumberOfMoves INT = 0
SELECT @NumberOfMoves = COUNT(*)
FROM Games.InstanceMove WHERE InstanceId = @InstanceId
IF @PostCheck = 0 -- For pre-check,
-- increment by one so we are on the right move
BEGIN
SET @NumberOfMoves = @NumberOfMoves + 1
END
DECLARE @MidPointMoves INT =
POWER(2,@NumberOfDisks) / 2
IF @NumberOfMoves = @MidPointMoves
AND (@VariableNumber <> @NumberOfDisks
OR @VariableVAlue <> 3)
BEGIN
-- Only valid move here is the big disk to last peg
SET @ResultVar = -7
END
END
END
END
END
END
-- Return the result of the function
RETURN @ResultVar
END
Regarding these functions, with the exception of the Tower of Hanoi rule check, which we can easily convert to a generic fashion by storing the function name in the game row representing Hanoi and using dynamic SQL, all of the code is generic and not specific to any particular type of game. Let’s take a look at the Windows form used to play the game and play it for a simple 2 disk scenario using brute force. In this scenario, we only “lose” the game once before having to backup. You’ll see as we increase the number of disks on the below graphics, that the loss rate increases very rapidly for games with higher number of disks.
At this point, we now have an interface that allows us to play a game (although it is somewhat tailored to Hanoi and requires a little bit more work to make truly generic) and record the results in state data. Given the above input along with the trigger interaction, here is the data generated including the states of the disks and the pegs as well as overall game states using various variable configuration (2 disks, 3 disks, etc.). Note the patterns. The domain states refer to which variable was moved on a move and the range states indicate which peg was altered for a move. For example for the 2-disk scenario, on Move 1, we moved Disk 1 to Peg 3, On Move 2, we moved Disk 2 to Peg 3 and on Move 3, we moved Disk 1 to Peg 3.
Above are the results of 3 to 5 disk scenarios. Remember, the game is being solved through brute-force at this point. We are just trying to simulate different variations in order to find a pattern or general algorithm for solving the game. All the application understands is how to call a stored procedure to make a rule based on another stored procedure that provides a list of all the legal rules, another procedure to find out the status and determine if a game is still winnable or if it has been won, and finally a stored procedure that can be called to back out a move and try again without having to start all over. Somewhere in the list is the required rule, as there is only 1 “winning” solution to any Hanoi game that uses the fewest moves. Using this approach, along with adding a couple of hints to prevent obvious dead-ends game-plays or detect losses half-way through, we can practically simulate up to 6 disks before the time complexity involved with the recursive depth-searches becomes overwhelming.
Below is the main code in the c# program for playing the game. As you can see, there is nothing specific to Hanoi, this could be used to try to play any game and find the solution by brute force.
public MoveStatus(fn_GetValidHanoiMoves_View move, bool used)
{
Move = move;
Used = used;
}
private List<MoveStatus> getMoveStatuses(int instanceId)
{
List<MoveStatus> moveStatuses = new List<MoveStatus>();
{
var gameMoves = from p in _dc.fn_GetValidHanoiMoves(instanceId)
select p;
foreach (fn_GetValidHanoiMoves_View gameMove in gameMoves)
{
// Add them to the list
moveStatuses.Add(new MoveStatus(gameMove, false));
}
//_dc.SubmitChanges();
}
return moveStatuses;
}
private void move(List<MoveStatus> moveStatuses)
{
int? gameStatus = 0;
Stack<List<MoveStatus>> moveStack = new Stack<List<MoveStatus>>();
while (gameStatus != 1)
{
// Create a new list on the stack unless we are in undo mode
if (moveStack.Count() >= Math.Pow(2.00,
(float)this.numericUpDownObjects.Value))
{
// Went too far, roll back the stack
_dc.UndoLastMove(_InstanceId);
moveStatuses = moveStack.Pop();
}
bool madeMove = false;
// Try a move until one works
foreach (MoveStatus moveStatus in moveStatuses)
{
if (!moveStatus.Used)
{
int? lastMoveId = 0;
moveStatus.Used = true;
_attempts++;
_dc.InsertInstanceMove(ref lastMoveId, ref gameStatus,
_InstanceId,
moveStatus.Move.InstanceVariableId,
moveStatus.Move.InstanceVariableValue);
this.listBox1.Items.Add("Move " +
moveStatus.Move.InstanceVariableNumber.ToString() +
" to "
+ moveStatus.Move.InstanceVariableValue.ToString()
+ "; stack=" + moveStack.Count().ToString());
_dc.SubmitChanges();
// if move fails, undo it.
if (gameStatus == -1)
{
_losses++;
_dc.UndoLastMove(_InstanceId);
this.listBox1.Items.Add("Undo; stack="
+ moveStack.Count().ToString());
_dc.SubmitChanges();
}
// If move was ok or game-won then break out
else
{
madeMove = true;
break;
}
}
}
// If a move worked, we can move on, else we need to backtrack
if (gameStatus == 0 && madeMove)
{
moveStack.Push(moveStatuses);
moveStatuses = (getMoveStatuses(_InstanceId.Value));
}
if (gameStatus == -1 || !madeMove || moveStatuses.Count()== 0)
{
// If game status is loosing, or we weren't able to make
// a move
// or the move status count (generated in line just above)
// is 0, then we undo and pop the stack back.
_dc.UndoLastMove(_InstanceId);
this.listBox1.Items.Add("Undo; stack="
+ moveStack.Count().ToString());
_dc.SubmitChanges();
moveStatuses = (moveStack.Pop());
// Go back to the prior move statuses
}
}
}
Let’s take a closer look at domain states and range states to understand their significance:
|
Disks
|
DomainStates
|
RangeStates
|
|
2
|
1,2,1
|
2,3,3
|
|
3
|
1,2,1,3,1,2,1
|
3,2,2,3,1,3,3
|
|
4
|
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
|
2,3,3,2,1,2,2,3,3,1,1,3,2,3,3
|
|
5
|
1,2,1,3,1,2,1,4,1,2,1,3,1,2,1,5,1,2,1,3,1,2,1,4,1,2,1,3,1,2,1
|
3,2,2,3,1,3,3,2,2,1,1,2,3,2,2,3,1,3,3,1,2,1,1,3,3,2,2,3,1,3,3
|
Based on the patterns and their interrelationships, we can determine what a solution would be for N disks through some mathematical introspection. We should be able to do this generically in code. For example, note that where N is the number of disks, N is always moved on the T/2 moves where T is the total number of moves required for the optimal solution. Note also that there is symmetry in the domain states before and after the middle move – i.e. for disk-2 scenario, the same disk is moved on the first and final third move, for 3-disk scenario, we have 1,2,1, both before and after the middle-move and this pattern continues for the 4 and 5 disk scenarios. Thus we can generate a hint for an optimal solution to automatically replay the first half of the game when trying to solve for a greater number of disks. There are additional patterns in the range states and how they relate to the domains. By simply finding all of the patterns, one should be able to define the winning pattern for any number of disks without even knowing the recurrence relation.
Another way to look at this is from the point of view of the variable states, which my infrastructure provides through the code previously shown in the trigger. It just involves appending a 1 or 0 on to the bit mask based on whether or not the variable was affected.
UPDATE Games.InstanceVariableValueStates
SET MoveStates = COALESCE(MoveStates,'') + '1'
WHERE InstanceId = @InstanceId
AND InstanceVariableNumber = @InstanceVariableNumber
AND InstanceVariableValue= @InstanceVariableValue
UPDATE Games.InstanceVariableValueStates
SET MoveStates = COALESCE(MoveStates,'') + '0'
WHERE InstanceId = @InstanceId
AND NOT (InstanceVariableNumber = @InstanceVariableNumber
AND InstanceVariableValue= @InstanceVariableValue)
At the end of the game, we end up with the following. the bit mask just indicates what move the disk is moved to a particular peg. For example in instance 200, the 3 disk game, we find that disk 2 is moved onto disk 3 on the second move.
|
Instance
|
Variable
|
Value
|
Bit Mask (each bit is a move, and a 1 indicate a pairing of the variable (disk) and the value (peg).
|
|
199
|
1
|
1
|
000 - Disk 1 never moved to peg 1 (started there, but never moved there)
|
|
199
|
1
|
2
|
100 - Disk 1 moved to disk 2 on move 1
|
|
199
|
1
|
3
|
001 - Disk 1 moved to disk 3 on move 3 (last move)
|
|
199
|
2
|
1
|
000
|
|
199
|
2
|
2
|
000
|
|
199
|
2
|
3
|
010– Disk 2 moved onto peg 3 on move 2
|
|
200
|
1
|
1
|
0000100
|
|
200
|
1
|
2
|
0010000
|
|
200
|
1
|
3
|
1000001
|
|
200
|
2
|
1
|
0000000
|
|
200
|
2
|
2
|
0100000
|
|
200
|
2
|
3
|
0000010
|
|
200
|
3
|
1
|
0000000
|
|
200
|
3
|
2
|
0000000
|
|
200
|
3
|
3
|
0001000
|
|
201
|
1
|
1
|
000010000010000
|
|
201
|
1
|
2
|
100000100000100
|
|
201
|
1
|
3
|
001000001000001
|
|
201
|
2
|
1
|
000000000100000
|
|
201
|
2
|
2
|
000001000000000
|
|
201
|
2
|
3
|
010000000000010
|
|
201
|
3
|
1
|
000000000000000
|
|
201
|
3
|
2
|
000100000000000
|
|
201
|
3
|
3
|
000000000001000
|
|
201
|
4
|
1
|
000000000000000
|
|
201
|
4
|
2
|
000000000000000
|
|
201
|
4
|
3
|
000000010000000
|
|
202
|
1
|
1
|
0000100000100000100000100000100
|
|
202
|
1
|
2
|
0010000010000010000010000010000
|
|
202
|
1
|
3
|
1000001000001000001000001000001
|
|
202
|
2
|
1
|
0000000001000000000001000000000
|
|
202
|
2
|
2
|
0100000000000100000000000100000
|
|
202
|
2
|
3
|
0000010000000000010000000000010
|
|
202
|
3
|
1
|
0000000000000000000100000000000
|
|
202
|
3
|
2
|
0000000000010000000000000000000
|
|
202
|
3
|
3
|
0001000000000000000000000001000
|
|
202
|
4
|
1
|
0000000000000000000000000000000
|
|
202
|
4
|
2
|
0000000100000000000000000000000
|
|
202
|
4
|
3
|
0000000000000000000000010000000
|
|
202
|
5
|
1
|
0000000000000000000000000000000
|
|
202
|
5
|
2
|
0000000000000000000000000000000
|
|
202
|
5
|
3
|
0000000000000001000000000000000
|
|
203
|
1
|
1
|
000010000010000010000010000010000010000010000010000010000010000
|
|
203
|
1
|
2
|
100000100000100000100000100000100000100000100000100000100000100
|
|
203
|
1
|
3
|
001000001000001000001000001000001000001000001000001000001000001
|
|
203
|
2
|
1
|
000000000100000000000100000000000100000000000100000000000100000
|
|
203
|
2
|
2
|
000001000000000001000000000001000000000001000000000001000000000
|
|
203
|
2
|
3
|
010000000000010000000000010000000000010000000000010000000000010
|
|
203
|
3
|
1
|
000000000000000000010000000000000000000000010000000000000000000
|
|
203
|
3
|
2
|
000100000000000000000000000100000000000000000000000100000000000
|
|
203
|
3
|
3
|
000000000001000000000000000000000001000000000000000000000001000
|
|
203
|
4
|
1
|
000000000000000000000000000000000000000100000000000000000000000
|
|
203
|
4
|
2
|
000000000000000000000001000000000000000000000000000000000000000
|
|
203
|
4
|
3
|
000000010000000000000000000000000000000000000000000000010000000
|
|
203
|
5
|
1
|
000000000000000000000000000000000000000000000000000000000000000
|
|
203
|
5
|
2
|
000000000000000100000000000000000000000000000000000000000000000
|
|
203
|
5
|
3
|
000000000000000000000000000000000000000000000001000000000000000
|
|
203
|
6
|
1
|
000000000000000000000000000000000000000000000000000000000000000
|
|
203
|
6
|
2
|
000000000000000000000000000000000000000000000000000000000000000
|
|
203
|
6
|
3
|
000000000000000000000000000000010000000000000000000000000000000
|
Examining these patterns bit-by-bit for shift operations, power-functions, etc, may be a more practical way to decipher the winning patterns:
My goal is that the code should be able to find patterns, store the patterns in a dictionary and then consult a dictionary of patterns learned over time including patterns related to how to learn, match it up to the states based on how the variables change, and identify a recursive relation to solve for future games, not by using brute force, but by using the learned rules. As time goes on, we can add to the dictionary new algorithms and then use them to look for patterns. Therefore, this can be the basis for an extensible/self-learning framework.
Now, that we have captured the data states of the game, we can examine the game states as they relate to the number of variables. The engine for examining and learning the patterns can be the same engine that does the simulation, thus this can be a recursive self-learning organism feeding off of achieving goals within the constraints of rules. We should be able to apply this technique to any scenario, including complex ones by schematizing the scenario into a game-based schema. Since we can do that for Hanoi, although this is a very simple case, my thesis is that the same fundamental approach can be used for other scenarios, which may be much more complex.
I apologize that some of the code isn’t formatted nicely and wrapped strangely in some places. I used a handy add-in for inserting code (Insert Code from http://www.shahine.com/omar/InsertCodeForWindowsLiveWriter.aspx), but some of my code lines are too long and got truncated. Due to time constraints, I just went in and put hard returns where necessary in the blog post to make sure everything at least displays on the page.
If you feel like I left you hanging, it’s because I did. I will have more to post on this later after I figure out the recognition piece. Stay tuned…
