Adding AI to the Checkers Game
Well this task turned out to be a lot more effort than I expected. I don't know if any of you have worked with the DWS2 component, but it was a first for me. I can really see the power of the component set but it certainly takes a bit of effort to get implemented.
I’d really like to know how to declare classes properly. My class declarations seemed to work except for classes as properties of the class. (e.g. the PossibleMoves TstringList in the Tcheckers class) Whenever these properties were accessed I got a Delphi Error. If anyone could help me with this I’d greatly appreciate it.
Architecture
Firstly lets take a look at the Architecture used by the DWS2 component set, I'm not going to go into the design architecture but rather the implementation Architecture within our program.
The DWS component set consists of a core component (TDelphiWebScriptII) and then a number of peripheral components that deliver various interfaces with additional functionality (such as the GUI, File System etc). One of these components (dws2Unit) is designed to allow the user of the component set to extend the functionality based on their own requirements. In our case we need to extend the functionality to allow the scripts to interact with our game board and make decisions on what it wants to do, this extended functionality becomes the interface between the scripting language and the application.
The DWS system basically allows the creation of tight bonding between the script functionality and the functions within the Delphi program that carry out the work. For example you could create a function within the scripting environment called MyFunction that calls DoSomething within the Delphi Application. Obviously this function would then carry out some action that is relevant in the application.
To Create an interface function between the Scripting environment and the Application follow the following steps.
1. Goto the object inspector of the dws2Unit component
2. Goto the Propert Editor for (dws2Functions)
3. Add a new funtion, allocating a name, and a ResultType if creating a function.
4. Open the (dws2Parameters) property editor and create whatever parameters are required.
5. Go back to the Function declaration and create an event handler for the OnEval event.
6. To allocate a result value use
7. To access the paremeters that were created useCode:Info['Result'] := <Value>;
For more information I suggest looking at the DwsDemo example in the DWS demos\basic directory.Code:I := Info['InputParm1'];
[b]Linking to the Checkers Application[/I]
Within the Checkers program a number of functions are required to interact with the Checkers class. Each of these functions will either interact with the main board or with a TestBoard created internally.
Internally to the Checkers Application I created a TList to store the various TestBoards that the AI has available for planning with BoardID = 0 for the actual board being used. These test boards are created as required (through use of the NewBoard function). Test boards are temporary views of the board that can be updated by the script and the resulting board can be checked for game status etc.
For our purposes I defined the following interfaces into the Checkers Application.
[pascal]
// Informational
Procedure Author(Name : String);
Procedure AIName(Name : String);
// AI Related
Function NewBoard(CopyBoardID : Integer) : Integer; // Create a new TestBoard copying from CopyBoardID
Procedure CopyBoard(SourceBoard, DestinationBoard : Integer);
Function GameState(BoardID : Integer) : Integer;
Procedure DefineMoves(BoardID : Integer);
Function MoveCount(BoardID : Integer) : Integer;
Function Move(BoardID, MoveID : Integer) : String;
Procedure DoMove(BoardID : Integer ; MoveStr : String);
Function Board(BoardID, X,Y : Integer) : String;
[/pascal]
Each of these functions either informs the Delphi Application of something - such as the Authors Name and AI Name, that are then displayed by the Delphi Application; or they interact with a board.
These functions can be called by the script as follows:
[pascal]
Author('William Cairns');
AIName('Simple - First Move');
[/pascal]
Linking to the Script
While the script needs to communicate with the Application the Application also needs to communicate with the script. There needs to be a way for the Application to ask the script for information. To accomplish this I defined a number of procedures that must be defined in every Checkers AI script.
[pascal]
// Procedure AIInfo defines default info about AI Script
Procedure AIInfo;
//Procedure AIMove defines logic to calculate moves. Not that the script is NOT persistent
// and needs to recalculate each time it is called.
Procedure AIDoMove;
[/pascal]
The Delphi Application will call the AIInfo procedure whenever the script is loaded. This process cannot be used to do global initialisations as the script is not persistent and is rerun every time a move is needed. To those who have done web programming the similarity with scripting languages is clear. It would also be possible to implement Session logic but I didn’t go into it.
Writing our First CAI Script
For our first script I’ll just force it to use the first move available to it. I need to implement both the AIInfo and AIDoMove procedures to correctly link to the Application.
[pascal]
Procedure AIInfo;
Begin
Author('William Cairns');
AIName('Simple - First Move');
End;
Procedure AIDoMove;
Begin
DoMove(0,Move(0,0));
End;
[/pascal]
Nothing could be simpler. Notice that even though no other boards exist it is still necessary for the DoMove and Move methods to identify that they are referring to BoardId=0.
Adding some real AI
For the second script I am going to implement a two-move look forward logic. The value of a board position is going to be based on the pieces on the board. Each normal piece will be worth 1 point and each king 5 points. This is a very simplified AI that doesn’t take much to beat and sometimes gets into a loop where the same moves are continually carried out.
For simlification I have stripped out all comments in the code:
[pascal]
Procedure AIInfo;
Begin
Author('William Cairns');
AIName('Cost based Checkers AI');
End;
Var
MyColor : Integer;
Function GetMyValue(X,O : Integer) : Integer;
Begin
If MyColor = 1 then
Result := X
Else
Result := O;
End;
Procedure ValueBoard(BoardID : Integer; var XVal, OVal : Integer);
Var
I,J : Integer;
XValue, OValue : Integer;
Begin
XValue := 0;
OValue := 0;
For I := 0 to 7 do
For J := 0 to 7 do
Begin
Case Board(BoardID, I, J) of
'o' : OValue := OValue + 1;
'O' : OValue := OValue + 5;
'x' : XValue := XValue + 1;
'X' : XValue := XValue + 5;
End;
End;
XVal := XValue;
OVal := OValue;
End;
Function TestMoves(BoardID : Integer) : Integer;
Var
TstBoard : Integer;
MvCnt : Integer;
X,O, Value : Integer;
V,I : Integer;
Begin
TstBoard := NewBoard(BoardID);
PrintLn('Secondary Test Board: '+IntToStr(TstBoard));
PrintLn(' Copied from: '+IntToStr(BoardID));
V := 99;
DefineMoves(TstBoard);
MvCnt := MoveCount(TstBoard);
For I := 0 to MvCnt-1 do
Begin
CopyBoard(BoardID,TstBoard);
DefineMoves(TstBoard);
DoMove(TstBoard,Move(TstBoard,I));
ValueBoard(TstBoard,X,O);
Value := GetMyValue(X,O);
If Value < V then
Begin
V := Value;
End;
End;
Result := V;
End;
Procedure AIDoMove;
Var
TestBoard : Integer;
MoveCnt : Integer;
X,O : Integer;
M,V,I : Integer;
Begin
MyColor := GameState(0);
TestBoard := NewBoard(0);
PrintLn('Main Test Board: '+IntToStr(TestBoard));
M := 0;
V := 0;
DefineMoves(TestBoard);
MoveCnt := MoveCount(TestBoard);
For I := 0 to MoveCnt-1 do
Begin
CopyBoard(0,TestBoard);
DefineMoves(TestBoard);
DoMove(TestBoard,Move(TestBoard,I));
X := TestMoves(TestBoard);
If X > V then
Begin
M := I;
V := X;
End;
End;
DoMove(0,Move(0,M));
ValueBoard(0,X,O);
PrintLn('X='+IntToStr(X));
PrintLn('O='+IntToStr(O));
End;
[/pascal]
The important things to notice are the additional procedures and functions are created as well. These methods are internal to the program and the Application never knows that they exist.
This script iterates through all the possible moves and all possible moves thereafter. It chooses the result with the lowest impact to itself. (i.e. the option that allows it the most benefit over two moves). This script could be vastly improved by a few simple other checks such as can a moved piece be taken Y/N; are other pieces also safe Y/N; is the move into the side of the board making it more secure Y/N; does the move form a wedge of pieces Y/N etc. Read up on some Checkers strategies if you want to.
Where to from here?
My purpose if looking into the use of a scripting tool for AI is to be able to make use of scripts within my games. My Fairy Fantasy game is going to require a lot of AI for the various creatures in the game as well as any opposition I want to add. By implementing this AI in a scripting language I make it possible to create new AI characters very quickly. When my game is ready for distribution it is easy enough to store the AI scripts in a resource file so that they cant be modified.
I'll get a copy of the Checkers game including the AI scripting on my web site. It is unpolished and there are many unfinished aspects to the game but it does what I wanted it to do - give me AI scripting capabilities.
Reply With Quote
Bookmarks