Axiom — increase the degree!

the Old grey donkey, Eeyore, stood alone in the overgrown with Thistle corner of the Forest, widely spread forelegs and dangling his head to one side, and thought about Serious Things.

A. Milne "Winnie-the-Pooh and all-all-all"

— You see a donkey? — I ask a policeman. There's a little grey donkey... article 2908. Price thirty-two cents. He has a great future.
— The donkey it is, agrees the policeman. They have sometimes a very big future.

Genrikh Altov "the donkey and the axiom"


What is the biggest challenge in designing Board games? Obviously no animation for moving the pieces on the Board. Difficult to come up with reasonable and interesting game rules. It is very difficult to provide game balance. If we are engaged in computer design are often very difficult to realize high-quality AI (for games like Go or Shogi, this problem is not solved until now). And even if we managed to implement a working AI, we have to do a very large amount of work to assess the quality of his work and choose from several options the best.

I want to tell you about the tool, can greatly simplify the solution to all these issues. Axiom Development Kit was conceived by developers as a way to improve Zillions of Games. In particular, it focused on the implementation of the game associated with capture site (such as Go), which AI ZoG doing very bad. In addition, the Axiom significantly extends the capabilities of the ZoG developers with many features not practically implemented in the framework of the traditional ZRF (markup rules). With all this, Axiom can operate completely independently, even if the ZoG on the computer has never been installed and purchased. But, everything in order...

image


I already wrote that ZoG has many drawbacks. Fortunately, developers have provided a mechanism to deal with some of them. Expansion module (engine) is a dynamically loadable library (DLL), taking under its control all aspects of the game, in addition to its visualization. Here here you can see an example of such an extension.

Independent development of own extensions can be very time consuming. Will have to develop AI (most likely in C++), since, when connecting the engine, the regular AI ZoG off. Axiom is a programmed engine that implements such a complicated developer stuff like AI algorithms and provides an opportunity to focus on the game logic.

We will try to implement the "Royal game of Ur". The required minimum ZRF-file:

engine Connection
(version "2.0")

(game
(title "Ur")

(engine, "../Axiom/Ur/axiom.dll")

(option "animate captures" false)
(option "animate drops" false)
(option "show moves list", false)
(option "pass turn" forced)
(option "highlight goals" is false)
(option "prevent flipping" true)
(option "recycle captures" true)

(drop-sound "Audio/Dice_cup.wav")
(move-sound "Audio/Clack.wav")
(capture-sound "")

(players White Black ?Dice)

(turn-order White ?Dice ?Dice ?Dice ?Black Dice ?Dice ?Dice ?Dice ?Dice)

(board 
(image "Images\Ur\board.bmp")
(grid
(start-rectangle -503 -13 -442 79)
(dimensions
("a/b/c/d/e/f/g/h/i/j/k/l/m/n/o/p/q" (67 0)) ; files
("5/4/3/2/1" (0 66)) ; ranks
) 
)
)

(board-setup
(?Dice (wdice q4) (bdice q3 q2) (q1 lock) )
(Black (init i5 j5 k5 l5 m5 n5 o5) )
(White (init i1 j1 k1 l1 m1 n1 o1) )
)

(piece
(name lock)
(image ?Dice "Images\Ur\invisible.bmp"
Black "Images\Ur\invisible.bmp"
White "Images\Ur\invisible.bmp")
)
(piece
(name init)
(image Black "Images\Ur\binit.bmp"
White "Images\Ur\winit.bmp")
)
(piece
(name prom)
(image Black "Images\Ur\bprom.bmp"
White "Images\Ur\wprom.bmp")
)
(piece
(name wdice)
(image ?Dice "Images\Ur\wdice.bmp")
)
(piece
(name bdice)
(image ?Dice "Images\Ur\bdice.bmp")
)

; The following dummy piece is required in order to placate the Zillions engine.

; in the zrf in order for it to be happy and thus allow "moves" to work correctly.
(piece (name Dummy) (dummy) (moves (from)))
)


Stayed here for a description of players, sequences of moves of the figures, but no explanation of the rules, which go figure. Also there is no definition of directions on the Board, playing zones, end-game and everything else associated with the game rules. All of this will be contained in the scripts Axioms. The sad point is that the interface of interaction with the ZoG engine does not provide for the transfer of information contained in the ZRF-file. This means that they will have to duplicate the scripts Axiom.

Fortunately, the composition Axiom Development Kit utility that allows you to automate this process. ZRF Converter rather capricious in operation. If something is not liked in the ZRF-file (for example a description of the Board rendered in the macro), the conversion process is interrupted with a mysterious diagnosis that cause break down. If everything went OK, the output we get the following description:

Ur.4th
{board
{position} a5
{position} b5
{position} c5
{position} d5
{position} e5
{position} f5
{position} g5
{position} h5
{position} i5
{position} j5
{position} k5
{position} l5
{position} m5
{position} n5
{position} o5
{position} p5
{position} q5
{position} a4
{position} b4
{position} c4
{position} d4
{position} e4
{position} f4
{position} g4
{position} h4
{position} i4
{position} j4
{position} k4
{position} l4
{position} m4
{position} n4
{position} o4
{position} p4
{position} q4
{position} a3
{position} b3
{position} c3
{position} d3
{position} e3
{position} f3
{position} g3
{position} h3
{position} i3
{position} j3
{position} k3
{position} l3
{position} m3
{position} n3
{position} o3
{position} p3
{position} q3
{position} a2
{position} b2
{position} c2
{position} d2
{position} e2
{position} f2
{position} g2
{position} h2
{position} i2
{position} j2
{position} k2
{position} l2
{position} m2
{position} n2
{position} o2
{position} p2
{position} q2
{position} a1
{position} b1
{position} c1
{position} d1
{position} e1
{position} f1
{position} g1
{position} h1
{position} i1
{position} j1
{position} k1
{position} l1
{position} m1
{position} n1
{position} o1
{position} p1
{position} q1
board}

{players
{player} Black
{player} White
{player} ?Dice {random}
players}

{pieces
{piece} lock
{piece} init
{piece} prom
{piece} wdice
{piece} bdice
{piece} Dummy
pieces}

{turn-order
{repeat}
{turn} White
{turn} ?Dice
{turn} ?Dice
{turn} ?Dice
{turn} ?Dice
{turn} Black
{turn} ?Dice
{turn} ?Dice
{turn} ?Dice
{turn} ?Dice
turn-order}

{board-setup
{setup} ?Dice wdice q4
{setup} ?Dice bdice q3
{setup} ?Dice bdice q2
{setup} ?Dice lock q1

{setup} Black init i5
{setup} Black init j5
{setup} Black init k5
{setup} Black init l5
{setup} Black init m5
{setup} Black init n5
{setup} Black init o5

{setup} White init, i1
{setup} White init j1
{setup} White init k1
{setup} White init l1
{setup} White init m1
{setup} White init n1
{setup} White init o1
board-setup}


Here we were waiting for the first surprise. Axiom allows to describe the Board more compact, but with serious limitations. grid can only describe a rectangular Board with a "standard" naming cells (in addition, in the description of the Board can contain only one grid). If necessary, the descriptions of boards to the more complex forms (e.g. three-dimensional) need to explicitly describe each position as it did ZRF Converter. Since, in our case, all constraints are respected (I had to rename columns and rows of the Board, compared with ZRF-implementation), use the more compact notation:

the
{board
5 17 {grid}
board}

Next, you need to determine the direction in which to move the shape. In games like Chess or Checkers, we could use a compact record specifying directions in terms of the coordinates:

the
{directions 
-1 0 {direction} North 
1 0 {direction} South 
0 1 {direction} East 
0 -1 {direction} West 
-1 1 {direction} Northeast 
1 1 {direction} Southeast 
-1 -1 {direction} Northwest 
1 -1 {direction} Southwest 
directions}

Alas, in our case, this method is not suitable. Since the trajectory of the chips on the Board in the game Ur pretty bizarre, have to explicitly define relationships between items:

Directions
{directions
( Anext )
{link} Anext l2 i1
{link} Anext j1 l2
{link} Anext k1 l2
{link} l1 Anext l2
{link} Anext l2 m1
{link} Anext n1 l2
{link} Anext o1 l2
{link} Anext l2 k2
{link} Anext k2 j2
{link} Anext j2 i2
{link} Anext i2 i3
{link} Anext i3 j3
{link} Anext j3 k3
{link} Anext k3 l3
{link} Anext l3 m3
{link} Anext m3 n3
{link} Anext n3 o3
{link} Anext o3 o2
{link} Anext o2 p2
{link} Anext p2 p3
{link} Anext p3 p4
{link} Anext p4 o4
{link} Anext o4 o3

( Bnext )
{link} Bnext i5 l4
{link} Bnext j5 l4
{link} Bnext k5 l4
{link} Bnext l5 l4
{link} Bnext m5 l4
{link} Bnext n5 l4

{link} Bnext l4 k4
{link} Bnext k4 j4
{link} Bnext j4 i4
{link} Bnext i4 i3
{link} Bnext i3 j3
{link} Bnext j3 k3
{link} Bnext k3 l3
{link} Bnext l3 m3
{link} Bnext m3 n3
{link} Bnext n3 o3
{link} Bnext o3 o4
{link} Bnext o4 p4
{link} Bnext p4 p3
{link} Bnext p3 p2
{link} Bnext p2 o2
{link} Bnext o2 o3

( Cnext )
{link} Cnext p3 p4
{link} Cnext p4 o4
{link} Cnext o4 o3
{link} Cnext o3 n3
{link} Cnext n3 m3
{link} Cnext m3 l3
{link} Cnext l3 k3
{link} Cnext k3 j3
{link} Cnext j3 i3
{link} Cnext i3 h3

( Dnext )
{link} Dnext p3 p2
{link} Dnext p2 o2
{link} Dnext o2 o3
{link} Dnext o3 n3
{link} Dnext n3 m3
{link} Dnext m3 l3
{link} Dnext l3 k3
{link} Dnext k3 j3
{link} Dnext j3 i3
{link} Dnext i3 h3
directions}


Black and white pieces move in different ways, so I had to determine the direction of Anext for white and Bnext for black. In addition, for chips that have passed through the field of transformation, it is necessary to redefine the Cnext and Dnext. If this is not done, the field o3 creates a fork and all the chips will spin in a circle in a small unit, selecting a first of the available routes.

the
{symmetries 
Black {symmetry} Anext Bnext
Black {symmetry} Cnext Dnext
symmetries}

This construction allows to define "symmetry". A good illustration of the movement of pawns in Chess. Pawns always move forward, but the white is moving up the Board, and for black — in the opposite direction. There are more complex forms of symmetry. For example, in the quadripartite versions of Chess, the movement "forward", depending on color, may occur in the direction of any of the four "sides". Defining "symmetry", we will be able to always use the same direction (for example, Anext), not paying attention to the color of the shape. For black, it will be automatically converted into symmetric (Bnext).

Fortification


My acquaintance with Fortum it was early, but a very long time remained very superficial. The first time I saw the Fort in the days of the BK-shek and Micros. My friend was Vector 06C, to pull from which we managed to just behind the ears, joint efforts of all parents. To Vector periodically, re-buy, cassette tapes with games on them, from time to time, is found "neuchtenka". Among such neusance, we found the implementation of the Fort. Plenty played enough with the stack, my friend said, "yeah", and set the radix to zero (Forte so funny). The Fort of course was unable to move and we have about him, for some time, forgot.

Later, in College, the Fort was repeatedly bubbled to the surface of my attention, but do they seriously did not succeed. In fact, I never had a chance encounter nor programming microcontrollers nor any other useful application of the Fort. And now, thanks to the developers of Axiom, I have such an opportunity! The fact that the word appears in their Forth ForthScript not just. Actually, the Axiom itself is-a and part ForthScript and implemented in Forte, and axiom.dll includes an interpreter that can be used. If necessary, in the axiom.4th and CORE.4TH you can see the implementation details, and possibly to correct them.

So, to program the entire game logic will be in the Fort. But how do I start developing? For starters, it would be nice to achieve the simple movement of pieces on the Board. Each figure should have the opportunity to move 1, 2, 3 or 4 cells in its trajectory (while we will not be distracted by throwing random points on "bones"):

move
: common-move ( 'dir n -- )
SWAP
BEGIN
DUP EXECUTE verify SWAP
1 - DUP
0= IF
DROP
TRUE
ELSE
SWAP
FALSE
ENDIF
UNTIL
empty? IF
from
here
move
add-move
ENDIF
;

: i-move-1 ( -- ) ['] Anext 1 common-move ;
: i-move-2 ( -- ) ['] Anext 2 common-move ;
: i-move-3 ( -- ) ['] Anext 3 common-move ;
: i-move-4 ( -- ) ['] Anext 4 common-move ;
: p-move-1 ( -- ) ['] Cnext 1 common-move ;
: p-move-2 ( -- ) ['] Cnext 2 common-move ;
: p-move-3 ( -- ) ['] Cnext 3 common-move ;
: p-move-4 ( -- ) ['] Cnext 4 common-move ;

{i moves-moves
{move} i-move-1
{move} i-move-2
{move} i-move-3
{move} i-move-4
moves}

{moves p-moves
{move} p-move-1
{move} p-move-2
{move} p-move-3
{move} p-move-4


{pieces
{piece} init {moves} i-moves
{piece} prom {moves} p-moves
pieces}


Running ZRF-ku on the run, you can see that now the shapes can be moved. How does it work? Look at the implementation of common-move. Comment (in the style of the Fort), located immediately after the name shows that it takes on the stack of two parameters — compiled command transition in the direction and number of steps of movement. The implementation itself consists of two parts. First, in a loop, the specified number of times, the system goes in the direction, then, after verifying that the target field is empty, a sequence of commands Axiom that form the course (moving chips). Most importantly, during this whole balancing act is not to destroy the stack!

A description of each of executed commands can be viewed in the manuals ForthScript and Axiom supplied with Axiom Development Kit, and I want to draw your attention to a few important differences in this code from what you would write using ZRF:

the
    the
  • In Axiom, the command transition in the direction (in the script above, this is performed using EXECUTE) forms a Boolean code, using which you can verify the success of the transition (if the direction is in a given cell is not defined, the transition is not performed and the stack is placed FALSE)
  • the
  • Command completion of the progress add-move is separated from the move command figure move (I already wrote in one of his articles why it is so important)!

You can play around with this version for a while, you notice that the chips, when he reached the small block, you begin to walk in a circle. In order that the chip can break out of this "circle of samsara", it should be turned upside down (inverted chip set Cnext and Dnext, leading to the finish). Let me remind you that the flip chips in the game Ur sly. The chip is flipped standing on the square of arrival, and passing through it. In addition, since chips can go all the way to the end, do not forget about the removal from the Board of chips, come down to the finish:

Flip chip
VARIABLE isPromouted

: common-move ( 'dir n -- )
FALSE isPromouted !
SWAP
BEGIN
current-player White
= IF
here p2
ELSE
here p4
ENDIF
= IF TRUE isPromouted ! ENDIF
DUP EXECUTE verify SWAP
1 - DUP
0= IF
DROP
TRUE
ELSE
SWAP
FALSE
ENDIF
UNTIL
empty? IF
from
here
move
here h3 = IF
capture
ENDIF
isPromouted @ IF
current-piece-type 1+ change-type
ENDIF
add-move
ENDIF
;


It is worth to say a few words about variables in the Fort. We define the variable isPromouted using VARIABLE. After the variable is defined, any reference in the code puts it on the stack address of this variable. To retrieve the value located at the specified address, use the command @, ! overwrites the value of the variable.

Some complexity, Axiom, represent manipulations with types of shapes. The fact that the definitions of figures are located after code that controls their movements (because they use it). For this reason, we cannot use the names of types of shapes in code (as in this place they have not yet been determined). As a rule, from this unpleasant situation, you can get out. For example, in our code, to turn the chips, we just incrementorum type figure running the course.

An important part of the gameplay is the ability to skip the turn players. The player must perform a move, if there is such possibility to pass the course, otherwise. If you do not care about this specifically, the game will automatically end in a draw at the first the impossibility of progress in any of the players. Also, skip the enemy turn, it is logical to implement a second course of the player after the move to the "socket". Do this:

Pass
: is-rosette? ( -- ? )
here i2 =
here i4 = OR
here l3 = OR
here o2 = OR
here o4 = OR
;

: common-move ( 'dir n -- )
q5 enemy-at? NOT IF
FALSE isPromouted !
SWAP
BEGIN
current-player White
= IF
here p2
ELSE
here p4
ENDIF
= IF TRUE isPromouted ! ENDIF
DUP EXECUTE verify SWAP
1 - DUP

DROP
TRUE
ELSE
SWAP
FALSE
ENDIF
UNTIL
empty? IF
from
here
move
here h3 = IF
capture
ENDIF
isPromouted @ IF
current-piece-type 1+ change-type
ENDIF
is-rosette? IF
q1 piece-type-at q5 create-piece-type-at
ELSE 
q5 capture-at
ENDIF
add-move
ENDIF
ENDIF
;

: pass-move ( -- )
q5 capture-at
Pass
add-move
;

{i moves-moves
{move} i-move-1 {move-type} normal-type
{move} i-move-2 {move-type} normal-type
{move} i-move-3 {move-type} normal-type
{move} i-move-4 {move-type} normal-type
{move} pass-move {move-type} pass-type
moves}

{moves p-moves
{move} p-move-1 {move-type} normal-type
{move} p-move-2 {move-type} normal-type
{move} p-move-3 {move-type} normal-type
{move} p-move-4 {move-type} normal-type
{move} pass-move {move-type} pass-type
moves}

{move-priorities
{move-priority} normal-type
{move-priority} pass-type
move-priorities}


The first catches the eye catchy definition of is-rosette?. Unfortunately, the Axiom, in contrast to the ZRF, there is no way of determining the play areas. All fields have to be checked individually.

Implementation of the pass speed also differs from the approach used in the ZRF. The setting "pass turn" is ignored by Axiom. Instead, a pass must be formed explicitly by Pass. This is one example of a more complete use of possibilities of notation recording moves ZSG (used to transfer motion from engine to the ZoG). Another example is the ability to use the reset commands (drops) when performing partial moves (partial moves) are not implemented in the ZRF.

note
Understanding ZSG-notation is very important when designing your own expansion module (engines). The ability to perform in ZoG any progress is completely determined by whether we can write it in the ZSG-notation. ZoG does not document this format, but the documentation for Axiom a describing section (Appendix B). Familiarity with this section may relieve the developer from extensive experimentation to ascertain the characteristics ZSG notation.

In order to pass the course only worked when there is no possibility of any other stroke, you need to use priorities. The course having the lower priority can only be performed in the absence of the possibility of stroke with a higher priority. Unfortunately, a pass in the style of Axiom is not fully functionally equivalent to the behavior of ZoG, if you set "pass turn" force. In the ZRF implementation, the pass is automatically performed in the case of Axiom, you will have to click on the button:



I have to say, it's great confusing.

To implement skip turn after turn on the "socket" in the position of q5 is not used in the game, placed the invisible figure of the lock. At the beginning of the common-move checks for the presence in this field of enemy pieces. If the field is occupied by the enemy, the operation is performed.

Now, it's time to learn how to throw "dice":

roll dice
{players
{player} White
{player} Black
{player} ?Dice {random}
players}

{turn-order
{turn} White
{turn} ?Dice {of-type} clear-type
{turn} ?Dice
{turn} ?Dice
{turn} ?Dice
{turn} Black
{turn} ?Dice {of-type} clear-type
{turn} ?Dice
{turn} ?Dice
{turn} ?Dice
turn-order}

: drop-dices ( -- )
here q2 = q3 here = OR q4 here = OR empty? AND IF
drop
add-move
ENDIF
;

: count-dices ( -- n )
q2 piece-at piece-value
q3 piece-at piece-value +
q4 piece-at piece-value +
DUP 0= IF
DROP
4
ENDIF
;

: clear-dices ( -- )
here q1 = verify
q2 not-empty-at? q3 is not-empty-at? q4-not-empty-at?
AND AND IF
drop
q2 capture-at
q3 capture-at
q4 capture-at
add-move
ENDIF
;

: i-move ( -- ) ['] Anext count-dices common-move ;
: p-move ( -- ) ['] Cnext count-dices common-move ;

{moves p-moves
{move} p-move {move-type} normal-type
{move} pass-move {move-type} pass-type
moves}

{moves drops
{move} drop-dices {move-type} normal-type
{move} pass-move {move-type} pass-type
moves}

{moves clears
{move} clear-dices {move-type} clear-type
moves}

{pieces
{piece} lock {moves} clears
{piece} init {moves} i-moves
{piece} prom {moves} p-moves
{piece} wdice {drops} drops 1 {value}
{piece} bdice {drops} drops 0 {value}
pieces}


The cast of "bones" (drop-dices) is elementary. Just check that the target field is a roll of the dice, put a shape with drop and complete the course with add-move. The more complicated the cleanup (clear-dices). In ZoG lacks the ability to form the course, which consists only in removing the pieces from the Board. The course of treatment we associate with discharge invisible figures on unused in the game field q1. Removal from the Board of "bones" is a side effect of this move. It remains to count the dropped points (count-dices) and pass this value in common-move.
In order to determine the termination condition of the game, you need to count the chips, who retired from the Board. The checking itself is performed by the completion Axiom by calling the overridden OnIsGameOver. To perform the initial actions at the start of the game (for example the initialization of the pseudorandom number generator), you must override the OnNewGame:

subject to completion
{board
5 17 {grid}
{variable} WhitePieces
{variable} BlackPieces
board}

: WhitePieces++ WhitePieces ++ ;
: BlackPieces++ BlackPieces ++ ;

: common-move ( 'dir n -- )
q5 enemy-at? NOT IF
FALSE isPromouted !
SWAP
BEGIN
current-player White
= IF
here p2
ELSE
here p4
ENDIF
= IF TRUE isPromouted ! ENDIF
DUP EXECUTE verify SWAP
1 - DUP
0= IF
DROP
TRUE
ELSE
SWAP
FALSE
ENDIF
UNTIL
empty? IF
from
here
move
here h3 = IF
current-player White = IF
COMPILE WhitePieces++
ELSE
COMPILE BlackPieces++
ENDIF
capture
ENDIF
isPromouted @ IF
current-piece-type 1+ change-type
ENDIF
is-rosette? IF
q1 piece-type-at q5 create-piece-type-at
ELSE 
q5 capture-at
ENDIF
add-move
ENDIF
ENDIF
;

: OnNewGame ( -- )
RANDOMIZE
;

: OnIsGameOver ( -- gameResult )
repetition-reset
#UnknownScore
current-player White = IF
BlackPieces @
7 - 0= IF
DROP
#LossScore
ENDIF
ENDIF
current-player Black = IF
WhitePieces @
7 - 0= IF
DROP
#LossScore
ENDIF
ENDIF
;


note
the Use-defined variable "on the Board", is described in section 3.9.4 "Updating Board Variables" documentation of Axiom.

To fully realize the game remained a battle of figures and the processing of special fields. I'm not going to clutter the article with the details, because they do not carry anything new. Anyone can see a full implementation of "the Royal game of Ur" to your GitHub.

Basic instinct


The main highlight of ZoG is its versatility. ZRF allows you to create a new game (or described there), just declared its rules. Yes, she plays noticeably worse than the specialized programs, but such a possibility a quick prototype almost any game is worth it! Number developed for ZoG applications speaks for itself.

Axiom also universal. It removes many unpleasant restrictions That allows us to describe these Board games, which the ZoG can not cope. One possibility of using a full arithmetic is manipulation of Boolean flags, it displays this product to a qualitatively higher level, but it is not the main advantage of Axiom! ZoG plays well or bad, but for us, her AI is a black box. We have no influence on the quality of his game! Axiom provides us with the opportunity (but does not require it) to participate in the development of algorithms for the selection of the optimal speed.

The most obvious possibility of interference in the work of AI Axiom — the choice of weight function, which is evaluated each position. We need only to override OnEvaluate. Try to create a very simple evaluation function, based on the total advancement of chips from start to finish. The placement of the chips on the starting position we will estimate a weight of 0, and the chips that passed the full path, we evaluate how a large number like 100. Obviously, if a token is taken, the measurement value will fall sharply (the more, the farther the chip had to move). Of course, for the enemy will use the same rating, taken with the opposite sign. The better the position of the enemy — even worse than our

Simple evaluation function
VARIABLE whiteScored
VARIABLE blackScored

: Score ( value-piece-type -- pos player score )
DUP not-empty-at? IF
DUP player-at White = IF
whiteScored --
ELSE
blackScored --
ENDIF
DUP ROT SWAP player-at =
ROT ROT piece-type-at =
AND NOT IF
DROP 0
ENDIF
ELSE
DROP DROP DROP DROP 0
ENDIF
;

: OnEvaluate ( -- score )
7 whiteScored !
7 blackScored !

0 1 White i1 Score
0 1 White j1 Score +
0 1 White k1 Score +
0 1 White l1 Score +
0 1 White m1 Score +
0 1 White n1 Score +
0 1 o1 White Score +

0 1 Black i5 Score +
0 1 Black j5 Score +
0 1 Black k5 Score +
0 1 Black l5 Score +
0 1 Black m5 Score +
0 1 Black n5 Score +
0 1 Black o5 Score +

1 1 White l2 Score +
-1 1 Black l4 Score +
2 1 White k2 Score +
-2 1 Black k4 Score +
3 1 White j2 Score +
Black j4 -3 1 Score +
4 1 White i2 Score +

5 1 White i3 Score +
-5 1 Black i3 Score +
6 1 White j3 Score +
-6 Black 1 j3 Score +
7 1 White k3 Score +
-7 1 Black k3 Score +
8 1 White l3 Score +
-8 1 Black l3 Score +
9 1 White m3 Score +
-9 1 Black m3 Score +
10 1 White n3 Score +
-10 Black Score 1 n3 +
11 1 White Score o3 +
-11 1 Black o3 Score +
12 1 White o2 Score +
-12 1 Black o4 Score +
13 1 White p2 Score +
-13 1 Black p4 Score +
14 2 White p3 Score +
-14 2 Black p3 Score +
15 2 White p4 Score +
-15 2 Black p2 Score +
16 2 White o4 Score +
-16 2 Black o2 Score +
17 White Score 2 o3 +
-17 Black Score 2 o3 +
18 2 White n3 Score +
-18 2 Black n3 Score +
19 2 White m3 Score +
-19 2 Black m3 Score +
20 2 White l3 Score +
-20 2 Black l3 Score +
21 White Score 2 k3 +
-21 2 Black k3 Score +
22 2 White j3 Score +
-22 2 Black j3 Score +
23 2 White i3 Score +
-23 2 Black i3 Score +

1 1 White c2 Score +
1 1 White c3 Score +
1 1 White c4 Score +
-1 Score 1 Black d2 +
-1 Black 1 d3 Score +
-1 Black 1 d4 Score +

3 1 White a2 Score +
3 1 White a3 Score +
3 1 White a4 Score +
-3 1 Black b2 Score +
-3 1 Black b3 Score +
-3 1 Black b4 Score +

7 1 White f2 Score +
7 1 White f3 Score +
7 1 White f4 Score +
-7 1 Black f2 Score +
-7 1 Black f3 Score +
-7 1 Black f4 Score +

10 1 White g2 Score +
10 1 White g3 Score +
10 1 White g4 Score +
-10 1 Black g2 Score +
-10 1 Black g3 Score +
-10 1 Black g4 Score +

11 1 White e2 Score +
11 1 White e3 Score +
11 1 White e4 Score +
-11 1 Black e2 Score +
-11 1 Black e3 Score +
-11 1 Black e4 Score +

17 White Score 2 e2 +
17 2 White e3 Score +
17 2 White e4 Score +
-17 2 Black e2 Score +
-17 2 Black e3 Score +
-17 2 Black e4 Score +

18 2 White g2 Score +
18 2 White g3 Score +
18 2 White g4 Score +
-18 2 Black g2 Score +
-18 2 Black g3 Score +
-18 2 Black g4 Score +

21 2 White f2 Score +
21 2 White f3 Score +
21 2 White Score f4 +
-21 2 Black f2 Score +
-21 2 Black f3 Score +
-21 2 Black f4 Score +

whiteScored @ 100 * +
blackScored @ 100 * -

current-player Black = IF NEGATE ENDIF
;


Of course, the Axiom does not leave us alone with the Fort in the development of the evaluation function. We are provided with convenient primitives for the estimation of both material and positional components. For example, the following evaluation function (up to factors), taken from the official guide, it's nice to work for most games, like Checkers and Chess

the
: Mobility ( -- mobilityScore ) 
move-count \ Number of moves available to us. 
current-player TRUE 0 $GenerateMoves \ Generate moves for opponent 
move-count \ Number of moves available to the opponent. 
- \ #friendlyMoves - #unfriendlyMoves 
$DeallocateMoves \ Deallocate the opponent's move list 
;

: OnEvaluate ( -- score ) 
Mobility 
current-player material-balance 3 * + 
;

Here, the call to move-count counts the number of possible moves from the current position and material balance computes the sum of the weights assigned to the shapes, using the attribute {value} (in our code, we use it to specify numeric values "bones").

All this is fine, but what about in cases when the use of the minimax algorithm is redundant? In the game we are trying to implement, looking more than one move ahead, most likely, will only lead to wasted computing resources. As I have already wrote, here we do not need "Artificial intelligence", but rather "Artificial instinct"! Axiom provides us with the opportunity to intervene in the selection algorithm moves to a deeper level:

a Random algorithm to choose the move
VARIABLE BestScore \ Keep track of the best score found so far by our search engine.
VARIABLE Nodes \ The number of possibilities explored by our search engine.
VARIABLE being eated
VARIABLE Rosettes

: enemy-value-at ( pos -- value )
DUP
empty-at?
IF
DROP 0
ELSE
0 SWAP
player-at current-player <>
IF DROP 1 ENDIF
ENDIF
;

: friend-value-at ( pos -- value )
DUP
empty-at?
IF
DROP 0
ELSE
1 SWAP
player-at current-player <>
IF DROP 0 ENDIF
ENDIF
;

: Make_enemy_p ( pos --) < BUILDS , DOES > @ enemy-value-at ;
: Make_friend_p ( pos --) < BUILDS , DOES > @ enemy-value-at ;

i1 e0 Make_enemy_p
j1 e1 Make_enemy_p
k1 e2 Make_enemy_p
l1 Make_enemy_p e3
m1 Make_enemy_p e4
Make_enemy_p n1 e5
o1 Make_enemy_p e6
i5 Make_enemy_p e7
j5 e8 Make_enemy_p
k5 Make_enemy_p e9
l5 Make_enemy_p e10
m5 Make_enemy_p e11
n5 Make_enemy_p e12
o5 e13 Make_enemy_p

i2 r0 Make_friend_p
i4 r1 Make_friend_p
l3 r2 Make_friend_p
o2 Make_friend_p r3
o4 Make_friend_p r4

: CountEated ( -- count )
e0 e1 + e2 + e3 + e4 + e5 + e6 + e7 + e8 + e9 + e10 + e11 + e12 + e13 +
;

: CountRosettes ( -- count )
r0 r1 + r2 + r3 + r4 +
;

: Score ( -- score )
Eated in @ CountEated < IF 10 ELSE 0 ENDIF
Rosettes @ CountRosettes < IF 5 ELSE 0 ENDIF +
;

: Custom-Engine ( -- )
-1000 BestScore ! \ Keep track of the best score.
0 Nodes ! \ Count the number of possibilities explored.
CountEated Being Eated !
CountRosettes Rosettes !
(
Notes:
1 - We do not need to invoke $GenerateMoves since they have already been generated for the
current player { since ZoG has DLL_GenerateMoves called prior to calling DLL_Search}.

2 - ZoG does not invoke the search engine if there are no moves, so we can safely assume.
that at least one move exists. Thus we can use a BEGIN..UNTIL loop instead of BEGIN WHILE...REPEAT..
for iterating moves.
)
$FirstMove \ Obtain the address of the first move.
BEGIN
$CloneBoard \ Create a temporary copy of the current board.

DUP .moveCFA EXECUTE \ Apply the move to the board by executing its code.
Score \ Calculate the score for the new board.
BestScore @ OVER < \ Have we found a better score?
IF
DUP BestScore ! \ Save the improved score.
Score! \ Inform the ZoG of the improved score.
DUP $MoveString BestMove!
ELSE
DROP \ We didn't find a better move, drop the score.
ENDIF
$DeallocateBoard \ Done with the revised board.
Nodes ++ \ Count one more node explored.
Nodes @ Nodes! \ Inform the ZoG of the node count.
$Yield \ Allow ZoG to dispatch Windows messages.
$NextMove \ Advance to the next move.
NOT DUP \ No more moves?
UNTIL
DROP
;

{players
{player} White {search-engine} Custom-Engine
{player} Black {search-engine} Custom-Engine
{player} ?Dice {random}
players}


Much of this code taken from the documentation. As is clear from the comments, we iterate through all possible moves, and used to built a temporary position evaluation function. As the evaluation function, we could take the same function that you have written for OnEvaluate, but it would not be interesting. I tried to formulate some kind of very aggressive strategy. If you have the opportunity to take an enemy piece or to embark on a "socket", this course was considered preferable, if this is not possible, selects the first available move.

By the way, the predefined primitive Axiom gambling strategies {first} and {random} implemented in the same way. That's how they are described in the axiom.4th:

basic strategy
: $RandomMoveEngine
$FirstMove
0
$movesList @ CELLSIZE + @ 1-
$RAND-WITHIN

BEGIN
DUP 0>
WHILE
SWAP @ SWAP
$Yield
1-
REPEAT
DROP

( move ) $MoveString DUP CurrentMove! BestMove!
1 Nodes! 0 Score! 0 Depth!
;

to : {random}
['] $RandomMoveEngine $CompileEngine
;

: $FirstMoveEngine
$FirstMove $MoveString DUP CurrentMove! BestMove!
$Yield
;

: {first}
['] $FirstMoveEngine $CompileEngine
;


As I said, the open (even partially) the source code is perfect!

Lies, damned lies, and statistics


Well, we have created a new game and can play it using ZoG. We have implemented several versions of the game with different algorithms of course, but how do we determine which one is better? Of course, you can get a dozen "experts" and ask each of them to play hundreds of times with each of the options. As one friend of mine, "it may take years". There is a better way!

The composition Axiom provides tools AutoPlay that allows you to automate the testing process. The first thing we must do, following the path of automation is the creation of variants games:

the
(variant (title "Ur [random]"))
(variant (title "Ur [simple evaluation]"))
(variant (title "Ur [aggressive]"))

Adding these lines to the end of the ZRF file, and then start ZRF Converter to get the billet 4th-files versions of the game. In these files you need to make changes that affect the strategy used by the program. So, for example, is one of the simplest options:

the
LOAD Ur.4th ( Load the base Ur game )

{players
{player} White {random}
{player} Black {random}
{player} ?Dice {random}
players}

It is easy to see that we can override individual sections of the description, in the entire shared code in a loadable script files.

Once the options created, we can run the game in game mode one option against the other. This is the main advantage of the AutoPlay! You do not want to create variants in which players play using different strategy. Enough to give the following command:

the
AutoPlay Ur-[random] Ur-[random] 100

Everything as simple as possible. Set the options for the first and second players (in the current implementation, the AutoPlay greater number of players is not supported) and the number of parties. Then the program runs itself. It makes it much faster than if these parties play with the use of ZoG! The output generated a large text file containing the description of all games played ZSG notation. In the end, it displays the final statistics that I can see that, provided that the moves are selected randomly, the player making the first move has a slight advantage (even given the fact that he always goes to "unity"):

the
Final results:
Player 1 "Ur-[random]", wins = 52.
Player 2 "Ur-[random]", wins = 48.
Draws = 0
100 game(s) played

The presence of a full ZSG-descriptions allows us, after a little processing, download any of the parties in ZoG and examine it step by step. By the way, have thus been detected and corrected these mistakes in the implementation (don't know what I was thinking when I decided to just dropnode the result of a transition instead to check it out).
Another advantage of having the complete ZSG-descriptions, is that we processed data can collect any necessary statistics, if we are not satisfied with a simple ratio of the number of winning/losing games. The following script displays the data on the duration of the parties, the final invoice at the end of the party, number of passes, speed and number of chips "felled" by each player:

the processing Script
#!/usr/bin/perl -w

my @S = (0, 0, 0, 0, 0, 0);
my $ix = 0;
my $T;

while (<>) {
if (/results/) {
my $d = $S[0] - $S[1];
print "$T, $d, $S[3], $S[2], $S[4], $S[5]\n";
@S = (0, 0, 0, 0, 0, 0);
$ix = 0;
} else {
if (/^(\d+)\.\s+[^?].*$/) {
$T = $1;
if (/x h3/) {
$S[$ix]++;
}
if (/Pass|^(\d+)\.\s+x\s+q5\s*$/) {
$S[$ix + 2]++;
}
if (/init Black [ijklmno]5/) {
$S[4]++;
}
if (/White init [ijklmno]1/) {
$S[5]++;
}
$ix++;
if ($ix > 1) {
$ix = 0;
}
}
}
}


Now we have everything we need to compare the quality of games we have developed variants. We will consider three options:

the
    the
  • With a random selection of stroke (random)
  • the
  • With a simple evaluation function (simple)
  • the
  • With "aggressive" algorithm for the choice of stroke (agressive)

random vs random
the duration of the party (if the opponents are not trying to delay the game, on average, a little more than 150 strokes):



The number of chips remaining on the Board (negative value of the loss of the first player):



The number of "srubami" players chips about the same:



We see that the player who starts first has a slight advantage:

the
Final results:
Player 1 "Ur-[random]", wins = 52.
Player 2 "Ur-[random]", wins = 48.
Draws = 0
100 game(s) played


random vs simple
Account:



Opponents are playing on is equal to:

the
Final results:
Player 1 "Ur-[random]", wins = 50.
Player 2 "Ur-[simple evaluation]", wins = 50.
Draws = 0
100 game(s) played


simple vs random
Party a bit late:



But more "intelligent" player surely lead to:



the
Final results:
Player 1 "Ur-[simple evaluation]", wins = 87.
Player 2 "Ur-[random]", wins = 13.
Draws = 0
100 game(s) played


random vs agressive
the Party is even more delayed:



But random begins to play (even when he goes first):



To understand why this is so, let's see how many pieces of "hits" each player:



Aggressive player "cuts down" a lot, but he substituted also!

the
Final results:
Player 1 "Ur-[random]", wins = 25.
Player 2 "Ur-[aggressive]", wins = 75.
Draws = 0
100 game(s) played


agressive vs random
Party again is faster:



But "aggressive" player smashing "random" is almost nil!



Now, he "cuts down" much more than the enemy:



the
Final results:
Player 1 "Ur-[aggressive]", wins = 90.
Player 2 "Ur-[random]", wins = 10.
Draws = 0
100 game(s) played


simple vs agressive
sorry, we were not able to find the ideal strategy. Starting the first simple again lead to:


Party is delayed even more!



the
Final results:
Player 1 "Ur-[simple evaluation]", wins = 73.
Player 2 "Ur-[aggressive]", wins = 27.
Draws = 0
100 game(s) played


agressive vs simple
Party not is delayed, if agressive starts first:



He copes with the common enemy, but not as easily as with "random":



the
Final results:
Player 1 "Ur-[aggressive]", wins = 64.
Player 2 "Ur-[simple evaluation]", wins = 36.
Draws = 0
100 game(s) played


By the way, pay attention to the following wonderful line:

the
Draws = 0

The fact Article based on information from habrahabr.ru

Комментарии

Популярные сообщения из этого блога

Looking for books as you want

Automatically create Liquibase migrations for PostgreSQL

Vkontakte sync with address book for iPhone. How it was done