Tamed ZoG (Part 2: BAM!)

but...

...the sound of the heavy bludgeon came into contact with someone's head. The body jerked and fell back. The deed was done, nobody heard, not yet seen: a perfect end, the perfect solution, a perfect story.

But as they say dwarves, for any trouble is a Troll.

sir Terry Pratchett

Thud! of Course, I could not pass this game. Not only because I love the works of Terry Pratchett, but mainly for the reason that this game is like no other. Let's start with the fact that it is played on an octagonal Board. The dwarves are fighting the trolls (and the last considerably less). How trolls can win, staying in the minority? Very simple — in one move, the Troll may remove from the Board a few dwarves. But the dwarfs, even acting together, to remove from the Board one Troll you have to work hard.

Board game, based on the work by Pratchett, was developed in 2002 by Trevor Turana and released for sale. From the moment I found out about this game, I really wanted to play it. I long and unsuccessfully searched for her computer implementation, but all I can find is discussion about the fact that this game is too complex for a computer to play it. Now, I have the opportunity to check this statement.

To begin to understand the rules of the game.

As I said earlier, the game is played on an octagonal Board, in the center of which is located "the Rock", occupies one cell. The game involves 8 trolls, on the one hand and 32 dwarf (Dwarfs) on the other. The task of each side is to minimize the number of the enemy.

The game is played in two stages (this rule substantially is used in the story of the eponymous books). Each of the players must play as gnomes and trolls. As a rule, to remove from the Board all opponent's pieces is not possible. The game ends by agreement of the players, after which points are considered. Each remaining on the Board dwarf is estimated at 1 point, the Troll — 4 points. The results of the two games played added. Who scored the most points is the winner.

Dwarves move any number of free squares in a vertical, horizontal or diagonals (as a Queen in Chess), but, in order to remove from the Board Troll, gnome needs it "jump". Several of the dwarves forming a line (vertically, horizontally, or diagonally), allow for extreme gnome jump (in the opposite direction from the line direction) by the number of cells less than or equal to the number of gnomes in a line (provided that at the end point of the jump is a Troll). Single standing gnome also forms a line and, thus, can leap 1 square in any direction, removing the Troll (if he of course managed to get close to him).

Trolls can move one square in any direction (like a king in Chess). All the dwarves trapped on the distance of one cell from the point of end of a course, removed from the Board. Thus, in one move, the Troll may withdraw from the Board until the 7 dwarfs (if very lucky). In order to remove the gnome from the Board, the Troll needs to go (even if close to him is already a dwarf). Trolls also can line up in a line (although they need to a much lesser extent than the dwarves). Line of the N trolls (vertically, horizontally, or diagonally) may push an extreme Troll on the N (or less) cells, provided that, in the result of this move, from the Board will be cleared at least one dwarf.

The pieces cannot jump over each other or through "the Rock" in the center of the Board.

You can see that we need to count the number of figures in the "line". As with the calculation of what is in the ZoG it's very easy (most likely, I will repeatedly speak about it), the implementation of these rules will be, for us, kind of test, and at the same time, will more fully illustrate the language features of descriptions of the ZRF. Let's start, however, with a simple:

Board

(define board-defs
(image "images\gluk\Thud.bmp")
(grid
(start-rectangle 45 35 60 58)
(dimensions
("a/b/c/d/e/f/g/h/i/j/k/l/m/n/o" (0 35)) ; files
("15/14/13/12/11/10/9/8/7/6/5/4/3/2/1" (0 35)) ; ranks
)
(directions (n 0 -1) (e 1 0) (s 0 1) (w -1 0)
(nw -1 -1) (ne 1 -1) (se 1 1) (sw -1 1))
)
(kill-positions a15 b15 c15 d15 e15 k15 l15 m15 n15 o15
a14 b14 c14 d14 l14 m14 n14 o14
a13 b13 c13 m13 n13 o13 
a12 b12 o12 n12
a11 o11
h8
a5 o5
a4 b4 n4 o4
a3 b3 c3 m3 n3 o3
a2 b2 c2 d2 l2 m2 n2 o2
a1 b1 c1 d1 e1 k1 l1 m1 n1 o1 )
(symmetry Black (n s)(s n) (ne sw) (sw ne) (nw se) (se nw))
)

In this description, compared to what I was saying in the previous article added a new keyword kill-positions. This section of the description allows you to restrict the number of positions a Board, turning it, therefore, from quadrangular to octagonal. In the center, as I promised, is "Rock". Figures pass through it, can't. In fact, it is not part of the playing field.

Go ahead

( define game-defs
( board
(board-defs)
)
( board-setup
(White (Dwarf f1 g1 e2 i1 j1 k2 l3 m4 d3 c4 b5 
n5 a6 a7 a9 o6 o7 o9 o10 a10 b11 n11
m12 l13 c12 d13 e14 f15 g15 k14 i15 j15) )
(Black (Troll g7 h7 i7 i8 g8 g9 h9 i9) )
)
(loss-condition (White Black) stalemated)
(draw-condition (White Black) repetition)
)

Nothing new here. We arrange the shapes, defined terms loss (for each side — the inability to make another move) and a draw (repetition). Now, the fun begins. We need to come up with a way to count the figures in the line.

leprechaun Hop

( define dwarf-3
( mark
(opposite $1) (verify friend?)
(opposite $1) (verify friend?) 
back 
$1 (verify empty?)
$1 (verify empty?)
$1 (verify enemy?) 
add
)
)

In order to jump a piece on 3 cells, I do the following:

the
1. Remember the current position command mark
the
2. Double-move in the direction opposite that shown by checking on the cell friendly pieces
the
3. Return to the source cell, the back command
the
4. Double-move in the direction of travel, checking that the cell is empty
the
5. Move again if the target cell contains an enemy figure
the
6. If all conditions are met, complete the course by the add command (an enemy figure is removed from the Board automatically)

Now the gnomes can jump into three cells (in the presence of suitable lines), bringing from the Board Troll. In addition to the three dwarves could jump on a different number of cells, you must redefine the macros in dwarf-1, dwarf-2, and so on, to dwarf-7 inclusive. Further, macros can not determine, because greater number of cells, on our Board, the jump will not work (even before we had the opportunity to jump on 7 cells, dwarves must be very lucky, so most likely this macro will never be used). This solution is somewhat verbose, but it works.

Besides taking, the dwarves should be able to do a normal move (any number of squares in a specified direction). It's simple:

gnome

( define shift 
( $1 
( while empty? 
add 
$1
)
)
)

We use a cycle. While the cells are empty, are moving in that direction, adding possible moves. This does not mean that we will walk to all these cells. We simply report the core of ZoG that these cells can to go, the rest is up to him.

Implementation progress of trolls is somewhat complicated by the fact that at the end of the turn they can remove from the Board the figures of the dwarves from neighbouring cells. Here is the implementation of the Troll two squares:

Troll

( define troll-2 
( mark
(opposite $1) (verify friend?) 
back 
$1 (verify empty?)
$1 (verify empty?)
(verify (or (enemy? n) (enemy? nw) (enemy? s) (enemy? ne)

(if (enemy? n) (capture n)) (if (enemy? nw) (capture nw))
(if (enemy? s) (capture s)) (if (enemy? ne) (capture ne))
(if (enemy? w) (capture w)) (if (enemy? sw) (capture sw))
(if (enemy? e) (capture e)) (if (enemy? se) (capture se))
add
)
)

In addition to checking the availability of a proper line here is to verify that, as a result of stroke, will be taken at least one dwarf. Also, before completing the stroke, added taking neighbors on all eight directions (provided that it is the enemy of the shape). It should be noted that predicates such as enemy? or empty? allow call transfer parameter direction that allows you to check without moving to another cell. Often, it is very convenient. In the implementation of the stroke in the same cage, just remove unnecessary checks:

Troll one cell

( define troll-1 
( $1 
(verify empty?) 
(if (enemy? n) (capture n)) (if (enemy? nw) (capture nw))
(if (enemy? s) (capture s)) (if (enemy? ne) (capture ne))
(if (enemy? w) (capture w)) (if (enemy? sw) (capture sw))
(if (enemy? e) (capture e)) (if (enemy? se) (capture se))
add
)
)

Left to collect the game together and make sure everything works:

Thud!

(game
(title "Thud")
(description "...")
(history "...")
(strategy "...")

(players White Black)
(turn-order White Black)
(game-defs)
(piece
(Dwarf name)
(image White "images\gluk\d.bmp")
(description "d")
(moves
(dwarf-1 n) (dwarf-1 ne) (dwarf-2 n) (dwarf-2 ne)
(dwarf-1 e) (dwarf-1 nw) (dwarf-2 e) (dwarf-2 nw)
(dwarf-1 s) (dwarf-1 se) (dwarf-2 s) (dwarf-2 se)
(dwarf-1 w) (dwarf-1 sw) (dwarf-2 w) (dwarf-2 sw)

(dwarf-3 n) (dwarf-3 ne) (dwarf-4 n) (dwarf-4 ne)
(dwarf-3 e) (dwarf-3 nw) (dwarf-4 e) (dwarf-4 nw)
(dwarf-3 s) (dwarf-3 se) (dwarf-4 s) (dwarf-4 se)
(dwarf-3 w) (dwarf-3 sw) (dwarf-4 w) (dwarf-4 sw)

(dwarf-5 n) (dwarf-5 ne) (dwarf-6 n) (dwarf-ne 6)
(dwarf-5 e) (dwarf-5 nw) (dwarf-6 e) (dwarf-6 nw)
(dwarf-5 s) (dwarf-5 se) (dwarf-6 s) (dwarf-6 se)
(dwarf-5 w) (dwarf-5 sw) (dwarf-6 w) (dwarf-6 sw)

(dwarf-7 n) (dwarf-7 ne) (n shift) (shift ne)
(dwarf-7 e) (dwarf-7 nw) (e shift) (shift nw)
(dwarf-7 s) (dwarf-7 se) (shift s) (shift se)
(dwarf-7 w) (dwarf-7 sw) (shift w) (shift sw)
)
)
(piece
(name Troll)
(image Black "images\gluk\T. bmp")
(description "T")
(moves
(troll-1 n) (troll-1 ne) (troll-2 n) (troll-ne 2)
(troll-1 e) (troll-1 nw) (troll-2 e) (troll-2 nw)
(troll-1 s) (troll-1 se) (troll-2 s) (troll-2 se)
(troll-1 w) (troll-1 sw) (troll-2 w) (troll-2 sw)

(troll-3 n) (troll-3 ne) (troll-4 n) (troll-4 ne)
(troll-3 e) (troll-3 nw) (troll-4 e) (troll-4 nw)
(troll-3 s) (troll-3 se) (troll-4 s) (troll-4 se)
(troll-3 w) (troll-3 sw) (troll-4 w) (troll-4 sw)

(troll-5 n) (troll-5 ne) (troll-6 n) (troll-ne 6)
(troll-5 e) (troll-5 nw) (troll-6 e) (troll-6 nw)
(troll-5 s) (troll-5 se) (troll-6 s) (troll-6 se)
(troll-5 w) (troll-5 sw) (troll-6 w) (troll-6 sw)

(troll-7 n) (troll-7 ne)
(troll-7 e) (troll-7 nw)
(troll-7 s) (troll-7 se)
(troll-7 w) (troll-7 sw)
)
)
)

It should be noted that the trolls in this game, was very strong figures. Whether the Board more, the dwarves had to run away and gather in a compact unit, approach which would not be so easy. But, on our Board, with the ability to jump, trolls get to gnomes already 2-3 on the go. I was running this game mode computer control for both sides for a long time. In the end, both sides remained at 5 figures, then the trolls couldn't catch up with the dwarves, because of the mobility of the latter. Admit that a person could play for dwarf better. On the other hand, playing for the trolls, the computer with the task certainly cope.

Sources, as always, can be picked up at GitHub.

Just in case I remind that to run them on a Demo version of Zillions of Games will not work. You can not even try.

Article based on information from habrahabr.ru