Obstacle Chase
What a slow country! - said the Queen. - Well, here
do you have to run as fast as you can
on the same spot! If you want to go to another place, then
need to run at least twice as fast!
Lewis Carroll " Alice Through the Looking Glass "
Today, I want to talk about an amazing and undervalued game that I met a little less than two years ago. In a sense, it was from this game, as well as from Ur , that my acquaintance with Dmitry Skiryuk began . In those days, I was just starting to get interested in board games. My knowledge was scarce and, in many ways, naive. Games like Chase have literally opened up a new immense world for me. Even now, the work on this game, to a large extent, resembles a detective story. In this regard, the game " Chase " fully justified both its name and similarity with the pseudonym of a famous American writer .
The game was developed by Tom Kruszewski and released for sale by TSR in 1986. In addition to the special board, each of the players has 10 six-sided dice, but despite this, the game is not hazardous. Cubes are thrown only once, to determine the order of the turn and are used only as figures in the future. The number of points on the upper face indicates the number of steps to which the die can be moved. So a cube with one point can be moved to a neighboring field, in any of the six directions, with two points - to two fields in a straight line, with three points - to three, etc. The cube must move exactly the specified number of steps, no more and no less. In the process of moving, the cube does not turn the other side (the number of points on the top face does not change). The initial placement is shown below:
')
More about the rules
For each player, the total number of points on the upper edges is 25. The player must maintain this amount until the end of the game. Players take turns and if one of them takes one (or two, this is also possible), his opponent must add the sum of points dropped from the game to his cube with the minimum number of points (at the beginning of the game, this is one of the numbers). If not all points are then distributed, the remainder is distributed further, always starting with the cube with the least points. A player who has less than 5 dice is losing because he cannot distribute the required number of points among the dice remaining on the board.
The boundaries of the board do not prevent the movement of figures. The left and right borders of the board are “glued together” among themselves, and the figures rebound from the upper and lower borders of the figure with a ricochet. Of course, this does not mean that the figures move freely. Figures can not "jump over" each other, as well as the central field " Chamber ". To capture an opponent's piece, the piece must “get up” on it (chess taking), completing the full number of steps in a straight line. The course can end on the shape of its color. In this case, " bumping " occurs - the figure that appears on the target field shifts by one step, continuing the direction of movement (taking into account the gluing of the board and the bounce). If the next field is also occupied by its own figure, the “ bumping ” extends further, to the first empty field or field occupied by the enemy figure (the enemy figure is taken). Only one obstacle can make such a move impossible - it is forbidden to “push” the figures into the central cell using bumping .
You can see that from the initial position, each of the players can cyclically move all of their pieces, by moving any one of them to the side of two. Such a move is allowed by the rules. It is also allowed to “exchange” points between figures of the same color that are in the adjacent fields. So a pair of 5 and 2 can turn into 4 and 3, or even into 1 and 6. Such an action is considered a move. Not considered there was only one type of move. None of the figures can pass through the central field of the board ( Chamber ), but it can finish its movement on this field. If this happens, the figure is “split” into two, with the total points remaining. The figure is always divided so that the points of one of the received figures exceed the other points by no more than 1. The total number of pieces for each of the players cannot exceed 10 (for this very case, at the beginning of the game, each of the players has 1 die in reserve).
The directions of the “expansion” of the fragments resemble the tip of an arrow. A cube with a large number of points (if there is one) always goes to the left side. In two special cases, "splitting" is impossible. First, as I said above, the number of cubes of the same color cannot exceed 10. In addition, it is absolutely clear that it will not be possible to split a cube with 1 point. In both these cases, the cube entered in the Chamber comes out unchanged in the left direction. Each of the figures who left the Chamber , can initiate a bumping , hitting his own figure or take the figure of the enemy (only in this way you can take two enemy figures at the same time).
The boundaries of the board do not prevent the movement of figures. The left and right borders of the board are “glued together” among themselves, and the figures rebound from the upper and lower borders of the figure with a ricochet. Of course, this does not mean that the figures move freely. Figures can not "jump over" each other, as well as the central field " Chamber ". To capture an opponent's piece, the piece must “get up” on it (chess taking), completing the full number of steps in a straight line. The course can end on the shape of its color. In this case, " bumping " occurs - the figure that appears on the target field shifts by one step, continuing the direction of movement (taking into account the gluing of the board and the bounce). If the next field is also occupied by its own figure, the “ bumping ” extends further, to the first empty field or field occupied by the enemy figure (the enemy figure is taken). Only one obstacle can make such a move impossible - it is forbidden to “push” the figures into the central cell using bumping .
You can see that from the initial position, each of the players can cyclically move all of their pieces, by moving any one of them to the side of two. Such a move is allowed by the rules. It is also allowed to “exchange” points between figures of the same color that are in the adjacent fields. So a pair of 5 and 2 can turn into 4 and 3, or even into 1 and 6. Such an action is considered a move. Not considered there was only one type of move. None of the figures can pass through the central field of the board ( Chamber ), but it can finish its movement on this field. If this happens, the figure is “split” into two, with the total points remaining. The figure is always divided so that the points of one of the received figures exceed the other points by no more than 1. The total number of pieces for each of the players cannot exceed 10 (for this very case, at the beginning of the game, each of the players has 1 die in reserve).
The directions of the “expansion” of the fragments resemble the tip of an arrow. A cube with a large number of points (if there is one) always goes to the left side. In two special cases, "splitting" is impossible. First, as I said above, the number of cubes of the same color cannot exceed 10. In addition, it is absolutely clear that it will not be possible to split a cube with 1 point. In both these cases, the cube entered in the Chamber comes out unchanged in the left direction. Each of the figures who left the Chamber , can initiate a bumping , hitting his own figure or take the figure of the enemy (only in this way you can take two enemy figures at the same time).
I must say that Tom Kruszewski and TSR strongly overestimated the capabilities of their potential audience. For the mass consumer, the game turned out to be too difficult (chess is no less complex, but everyone is used to it). The manufacturer has stopped production and, at present, Chase can only be purchased from the hands, at various fairs, auctions and sales. Nevertheless, this game is considered to be one of the best games of the 20th century.
Simple work
The game begins with a board, and the board at Chase ... is original. Previously, I have not had to do games on hexagonal boards and this was the first (very small) obstacle. This is an interesting point and I want to talk about it in more detail. The mechanism for describing game boards in ZRF is well thought out and allows you to implement almost any board, provided that they are displayed on the plane and do not change during the game.
Here's what it looks like.
I am not in favor of mixing model details with visualization issues, but until it is necessary to separate one from the other (for example, to display the board in “fair” 3D, and not isometry), this approach works well. Consider this description in more detail:
(board (image "../Images/Chase/board.bmp") (grid (start-rectangle 48 32 108 82) (dimensions ("a/b/c/d/e/f/g/h/i/j/k/l/m" (60 0)) ("1/2/3/4/5/6/7/8/9" (-30 52)) ) (directions (se 1 1) (w 1 0) (sw 0 1) (nw -1 -1) (e -1 0) (ne 0 -1)) ) (kill-positions j1 k1 l1 m1 j2 k2 l2 m2 a3 k3 l3 m3 a4 k4 l4 m4 a5 b5 l5 m5 a6 b6 l6 m6 a7 b7 c7 m7 a8 b8 c8 m8 a9 b9 c9 d9 ) ) I am not in favor of mixing model details with visualization issues, but until it is necessary to separate one from the other (for example, to display the board in “fair” 3D, and not isometry), this approach works well. Consider this description in more detail:
- An integral part of the description is the file containing the image of the board. All the geometric dimensions and positions of the figures are tied to it (for this reason, most of the distribution of my implementation of Sokoban is made up of black rectangles of various shapes and sizes). The file containing the image of the board in the BMP format ( ZoG understands only this format) is determined by the keyword image . Here you can define several files at once (to enable switching between skins), but only with identical geometric proportions.
- The grid keyword allows you to describe an n-dimensional array of positions. In most cases, this is a familiar two-dimensional board, but you can also define boards of a different dimension (up to five). The board can consist of several grids , provided that a unique naming of the individual positions is provided. With a great desire, you can even place one grid on top of another, much like the way it is done in " Quantum Noughts and Crosses ".
- The size of the “cell” and the location of the grid are determined by the start-rectangle keyword. Two pairs of integers define the screen coordinates (x, y) of the upper left and lower right corners of the very first (top left) cell.
- The following is a description of "measurements" ( dimensions ). Each description contains a string of names (of which the names of positions are combined by the Cartesian product), as well as two integers. In these numbers lies the "magic", which allows to describe hexagonal and isometric boards. This is nothing more than the shifts to which the next grid cells are shifted. Usually (for two-dimensional boards), in one dimension, the cells are shifted by the width of the cell by x , and in the other by the height of the cell by y , but by further shifting these cells by half the width by x , you can get an excellent basis for the hexagonal board.
- The second component of the grid's “magic” is directions ( directions ). The board is not only positions, but also communications (named and unidirectional) between them. Of course, no one bothers to define each link individually, by specifying a name and a pair of positions for each connection, but this process will not be fun when determining the boards of large sizes. The directions keyword allows you to manipulate not the names of positions, but the directions inside the grid.
- To get the board of the required shape, we take a “rectangular” board of a larger size, and then shift the rows by half of the cell relative to each other. As a result, there are "extra" positions that must be "cut off" from the board. The kill-positions keyword makes it possible to declare a previously defined position name invalid. Of course, along with the deleted positions, the corresponding compounds are also broken.
The use of the grid keyword can significantly reduce the amount of manual work in describing “typical” boards, but this approach is not without certain disadvantages. Firstly, if the board image was not drawn under the selected geometric dimensions specifically, using only integer coordinates and offsets, it can be difficult to align the position of all the board positions perfectly. The individual description of the positions is less concise, but allows you to adjust their location independently of each other. At the same time, it requires just a killer amount of manual work (taking into account the need to correct all admitted typos). In order to somehow facilitate this process, I use the grid for a “rough” description, after which I get an individual description of the positions using a small script :
Script
my @grid; my %kp; my $sx, $sy, $dx, $dy; my $dm = 0; while (<>) { if (/\(start-rectangle\s+(\d+)\s+(\d+)\s+(\d+)\s+(\d+)\)/) { $sx = $1; $sy = $2; $dx = $3 - $1; $dy = $4 - $2; } if (/\(\"([^\"]+)\"\s+\((-?\d+)\s+(-?\d+)\)\)/) { my @a = split(/\//, $1); $grid[$dm]->{ix} = \@a; $grid[$dm]->{x} = $2; $grid[$dm]->{y} = $3; $dm++; } if (/\(kill-positions/) { $fl = 1; } if ($fl) { if (/\s(([a-z0-9]{1,2}\s+)+)/i) { my @a = split(/\s+/, $1); foreach my $p (@a) { $kp{$p} = 1; } } if (/\)/) { $fl = 0; } } } sub try { my ($ix, $pos, $x, $y) = @_; if ($ix < $dm) { my $i = 0; foreach my $p (@{$grid[$ix]->{ix}}) { try($ix + 1, $pos . $p, $x + $i * $grid[$ix]->{x}, $y + $i * $grid[$ix]->{y}); $i++; } } else { if (!$kp{$pos}) { my $a = $sx + $x; my $b = $sy + $y; my $c = $a + $dx; my $d = $b + $dy; print " "; printf "($pos %3d %3d %3d %3d)\n", $a, $b, $c, $d; } } } try(0, '', 0, 0); Result
(positions (a1 48 32 108 82) (a2 18 84 78 134) (b1 108 32 168 82) (b2 78 84 138 134) (b3 48 136 108 186) (b4 18 188 78 238) (c1 168 32 228 82) (c2 138 84 198 134) (c3 108 136 168 186) (c4 78 188 138 238) (c5 48 240 108 290) (c6 18 292 78 342) (d1 228 32 288 82) (d2 198 84 258 134) (d3 168 136 228 186) (d4 138 188 198 238) (d5 108 240 168 290) (d6 78 292 138 342) (d7 48 344 108 394) (d8 18 396 78 446) (e1 288 32 348 82) (e2 258 84 318 134) (e3 228 136 288 186) (e4 198 188 258 238) (e5 168 240 228 290) (e6 138 292 198 342) (e7 108 344 168 394) (e8 78 396 138 446) (e9 48 448 108 498) (f1 348 32 408 82) (f2 318 84 378 134) (f3 288 136 348 186) (f4 258 188 318 238) (f5 228 240 288 290) (f6 198 292 258 342) (f7 168 344 228 394) (f8 138 396 198 446) (f9 108 448 168 498) (g1 408 32 468 82) (g2 378 84 438 134) (g3 348 136 408 186) (g4 318 188 378 238) (g5 288 240 348 290) (g6 258 292 318 342) (g7 228 344 288 394) (g8 198 396 258 446) (g9 168 448 228 498) (h1 468 32 528 82) (h2 438 84 498 134) (h3 408 136 468 186) (h4 378 188 438 238) (h5 348 240 408 290) (h6 318 292 378 342) (h7 288 344 348 394) (h8 258 396 318 446) (h9 228 448 288 498) (i1 528 32 588 82) (i2 498 84 558 134) (i3 468 136 528 186) (i4 438 188 498 238) (i5 408 240 468 290) (i6 378 292 438 342) (i7 348 344 408 394) (i8 318 396 378 446) (i9 288 448 348 498) (j3 528 136 588 186) (j4 498 188 558 238) (j5 468 240 528 290) (j6 438 292 498 342) (j7 408 344 468 394) (j8 378 396 438 446) (j9 348 448 408 498) (k5 528 240 588 290) (k6 498 292 558 342) (k7 468 344 528 394) (k8 438 396 498 446) (k9 408 448 468 498) (l7 528 344 588 394) (l8 498 396 558 446) (l9 468 448 528 498) (m9 528 448 588 498) ) This is only half the battle! The names of the positions of the board must be corrected to bring them in line with the generally accepted notation. In addition, it is required to link pairs of positions with directions, not forgetting to “loop” the board along the edges. Everything together resulted in a rather large amount of manual work , but I did not write a script for this case (although it was probably worth it).
Sleep of reason
Even though I met Chase for quite some time, until recently, I couldn’t play it. It is very fancy for this board is required. With some skill, you can play on the Shogi board (9x9), but I didn't have one either. An ordinary chess board (8x8) is completely unusable for this game. The board for Chase was acquired on the past by the Zilantkone , but the cubes were not included in the kit. I abandoned my purchase to the far regiment and there it would probably have failed, if the case had not intervened.
Accidents are not accidental
My daughter was invited to the birthday of the family, with whom we have long and close friends. As a gift, a board game was chosen, and since several adults had to spend about three hours in a children's cafe, they (and me) also needed to do something. As a possible alternative, another game was proposed, but since I prefer games that are more abstract, I decided to bring something with me too. Initially, I thought about Ur , but in my set, his D2 “bones”, made in the form of semicircular sticks (more characteristic of Seneta ), were rather inconvenient, making a lot of noise when throwing and could disturb others.
It was then that I remembered about Chase. It was necessary to replenish his kit with twenty dice, but since I was still going to the board games store (for a gift), this (as I then thought) was not a problem. On the site, I looked after myself wonderful translucent cubes (70 rubles each), but life made adjustments. In the store, it turned out that the cubes I watched were only in one copy. What can I say, Kazan is not Moscow, I had to be content with the budget option and recruit the desired cubes from the proposed i-do, dode-and other -ahedra offered by the seller. It was not possible to assemble a red or green set, but there were blue and white (okay, okay, one slightly yellowish) cubes.
It was then that I remembered about Chase. It was necessary to replenish his kit with twenty dice, but since I was still going to the board games store (for a gift), this (as I then thought) was not a problem. On the site, I looked after myself wonderful translucent cubes (70 rubles each), but life made adjustments. In the store, it turned out that the cubes I watched were only in one copy. What can I say, Kazan is not Moscow, I had to be content with the budget option and recruit the desired cubes from the proposed i-do, dode-and other -ahedra offered by the seller. It was not possible to assemble a red or green set, but there were blue and white (okay, okay, one slightly yellowish) cubes.
Of course, I turned the rules around (talking about memory). In my presentation, the paths of scattering of "fragments", at the exit of the "replicator", did not resemble the tip of an arrow, but rather the Latin letter ' Y '. Apparently, a certain role was played by its similarity with the decay schemes of elementary particles. "Shards" moved not one cell (as in the original version of the rules), but in accordance with their "face value". In addition, such a move was much easier to block. Any obstacles (be it a figure standing in the way of the “shards” spreading out or the presence of ten figures on the board) were interpreted as the impossibility of performing a turn. In the original version of the rules, you can block the " Chamber " only by setting the shape on the way to entering it.
Another link of the " spoiled phone " was Dmitry himself. In his description of “Chase”, he mentioned that the figure who performed the capture has the right to repeat the move (by analogy with Checkers ). In the original source there was not a word about this (which dear Gest did not fail to inform him about), but I, at that moment, did not pay attention to it. I must say, the idea to cross the “Chase” with the “Drafts” even then caused many questions. Should there be a rerun rule in case of bumping ? On the "fragments" obtained by dividing the figure? What should be done if the capture was performed by each of the fragments? And if the same with bumping th? But there are no such difficulties that we could not create for ourselves! I enthusiastically set to work ...
Manual sunset
Of course, first of all, I tried to use the partial move mechanism used in ZoG for games, like checkers . Most recently, he came in handy to me, in the process of creating a very difficult game . Until now, I have not had to use it in the Axiom, but everything happens once for the first time. The essence of a partial move is that a complex, composite move is broken into small steps. In checkers, the capture of the opponent's piece is realized in just such a partial move. At the same time, the so-called “modes” of the execution of a move are also used, allowing to indicate that the next partial move is also obliged to perform a take.
I am not happy with the implementation of composite moves in ZoG and here's why. First of all, in the understanding of ZoG, partial moves are just separate , independent actions. In fact, this is just a set of moves performed by the same player, one after the other. We cannot transfer any intermediate information between partial moves! Global and positional flags are automatically reset, at the beginning of each turn. This is devilishly uncomfortable, but this is only part of the trouble! ZoG cannot consider a composite move as a single entity (in particular, for this reason it was necessary to introduce the hardcode option " maximal captures " to implement the "rule of majority". Some other ideas that do not fit into this hardcode cannot be realized anymore!
This is a fragment of the game from the game " Mana ", invented by Claude LeRoy. The number of dashes, at each position, shows how many steps a piece can move. The exact number of steps must be completed and, at the same time, it is impossible to turn back during the movement. This is where an ambush awaits us! Very rarely, but it happens that the figure, after completing two steps, pushes itself “to a dead end”. She cannot continue the movement, because she is hampered by other figures and is obliged to take another step, since she must complete the turn! And ZoG, in turn, does not provide exactly any means to solve this problem!
Another limitation is that a composite move can be continued only by the same piece that was moved by the previous partial move. This is exactly what happens in drafts, but in Chase the situation is a bit more complicated. For example, a capture can be carried out with the help of a bumping-a , that is, not the figure who performed the move! With the Chamber, the entrance is still more difficult. Both fragments can take the opponent's pieces and, logically, have the right to make the next partial move. And both of them are not the figure who came to the Chamber (that figure, on the board, is no longer at all)!
Ultimately, it all comes down to adding a partial-move-type call when taking an enemy figure (before bumping-a ). The restrictions I mentioned above remain in force. We cannot perform a partial move if the capture was made not by the figure who started the move (as a result of bumping or splitting in the Chamber ), but even in this form, this code would be a good solution. If he earned:
I could not decipher this rebus and just sent the code to the developer Axiom. Greg has not yet answered, but he seems to be working on the release of a patch, which I hope will solve the problem. The strange thing here is that the partial moves in the Axiom really work! Moreover, they significantly extend the functionality of ZRF. All this is well described in the documentation and is used in several applications. Apparently, I just had no luck.
Since the partial moves did not work, I had to find another way to solve the problem. If you can not perform all the actions in one move, you can try to stretch them for several moves! I have already done so in other games, creating a special invisible position on the board in which the flag figure was placed. If the piece belonged to the opponent, the player knew that he had to miss his turn. This is a small change , but it pulled others along. I had to mark the pieces that continued the turn (now it could be not only the pieces that started the turn), but also complicate the order of passing the turn. In general, it was a rather cumbersome and very awkward decision.
I am not happy with the implementation of composite moves in ZoG and here's why. First of all, in the understanding of ZoG, partial moves are just separate , independent actions. In fact, this is just a set of moves performed by the same player, one after the other. We cannot transfer any intermediate information between partial moves! Global and positional flags are automatically reset, at the beginning of each turn. This is devilishly uncomfortable, but this is only part of the trouble! ZoG cannot consider a composite move as a single entity (in particular, for this reason it was necessary to introduce the hardcode option " maximal captures " to implement the "rule of majority". Some other ideas that do not fit into this hardcode cannot be realized anymore!
This is a fragment of the game from the game " Mana ", invented by Claude LeRoy. The number of dashes, at each position, shows how many steps a piece can move. The exact number of steps must be completed and, at the same time, it is impossible to turn back during the movement. This is where an ambush awaits us! Very rarely, but it happens that the figure, after completing two steps, pushes itself “to a dead end”. She cannot continue the movement, because she is hampered by other figures and is obliged to take another step, since she must complete the turn! And ZoG, in turn, does not provide exactly any means to solve this problem!
Another limitation is that a composite move can be continued only by the same piece that was moved by the previous partial move. This is exactly what happens in drafts, but in Chase the situation is a bit more complicated. For example, a capture can be carried out with the help of a bumping-a , that is, not the figure who performed the move! With the Chamber, the entrance is still more difficult. Both fragments can take the opponent's pieces and, logically, have the right to make the next partial move. And both of them are not the figure who came to the Chamber (that figure, on the board, is no longer at all)!
Less words - more code
: val ( -- n ) piece-type mark - ; : mirror ( 'dir -- 'dir ) DUP ['] nw = IF DROP ['] sw ELSE DUP ['] ne = IF DROP ['] se ELSE DUP ['] sw = IF DROP ['] nw ELSE ['] se = verify ['] ne ENDIF ENDIF ENDIF ; : step ( 'dir -- 'dir ) DUP EXECUTE NOT IF mirror DUP EXECUTE verify ENDIF ; : bump ( 'dir -- ) BEGIN here E5 <> verify friend? here from <> AND IF piece-type SWAP step SWAP create-piece-type FALSE ELSE TRUE ENDIF UNTIL DROP ; : slide ( 'dir n -- ) alloc-path ! val SWAP BEGIN step SWAP 1- DUP 0= IF TRUE ELSE my-empty? verify SWAP FALSE ENDIF UNTIL DROP from here move + enemy? IF + cont-type partial-move-type + ENDIF bump enemy? IF alloc-all ELSE alloc-path @ 0= verify ENDIF add-move ; Ultimately, it all comes down to adding a partial-move-type call when taking an enemy figure (before bumping-a ). The restrictions I mentioned above remain in force. We cannot perform a partial move if the capture was made not by the figure who started the move (as a result of bumping or splitting in the Chamber ), but even in this form, this code would be a good solution. If he earned:
I could not decipher this rebus and just sent the code to the developer Axiom. Greg has not yet answered, but he seems to be working on the release of a patch, which I hope will solve the problem. The strange thing here is that the partial moves in the Axiom really work! Moreover, they significantly extend the functionality of ZRF. All this is well described in the documentation and is used in several applications. Apparently, I just had no luck.
Since the partial moves did not work, I had to find another way to solve the problem. If you can not perform all the actions in one move, you can try to stretch them for several moves! I have already done so in other games, creating a special invisible position on the board in which the flag figure was placed. If the piece belonged to the opponent, the player knew that he had to miss his turn. This is a small change , but it pulled others along. I had to mark the pieces that continued the turn (now it could be not only the pieces that started the turn), but also complicate the order of passing the turn. In general, it was a rather cumbersome and very awkward decision.
The result of my efforts was a very original modification of the game, which unfortunately had too little to do with the original. In addition, the use of "complex" order of transfer of moves ( turn-order ) backhand beat on the "intelligence" AI. The minimax algorithm used by him reacts extremely negatively to such liberties, and in the search-engine (alternative to constructing the Axiom AI) “immune” to them, it is incredibly difficult to implement depth-first search.
For bread crumbs
Well, let's assume, on our own, we take one (or even two figures) of the enemy, after which we distribute the points obtained by his remaining figures, necessarily starting with the younger ones. But what if there are several junior figures? For example, at the very beginning of the game, each of the players has two "edinichki." Taking any figure in denominations of one to five points, we will get two options for the distribution of points and the course of the game can seriously change, depending on which of them we choose.
The same and combinatorics
Here, practically out of the blue, an interesting combinatorial problem arises. In order to understand in what ways (when taking a figure) points can be distributed, it is necessary to imagine all combinations of figures (on the side of one of the players) that can appear in the game. There are only three conditions:
I have no doubt that this task has a beautiful analytical solution (perhaps the readers will prompt it to me), but I did not search for it. I just wrote a script to generate all possible sets of shapes that meet the specified conditions. The figures in the sets are ordered by face value, since the points taken are distributed in this order.
Only 294 possible options. However, this is only half the battle. We are more interested not in the layouts themselves, but in the ways in which we can place the points of the taken figure in each of them. I will not bore the reader with detailed reasoning, I will show only the script and the final result of its work:
— , . , «20» , ( 0), , . , , «» , «3333445» (, «» «»). , , «» , 30% (2407/7954) , , 64%!
- Each piece can have a rating of 1 to 6 points.
- The number of figures can not exceed 10
- The total number of points is always 25
I have no doubt that this task has a beautiful analytical solution (perhaps the readers will prompt it to me), but I did not search for it. I just wrote a script to generate all possible sets of shapes that meet the specified conditions. The figures in the sets are ordered by face value, since the points taken are distributed in this order.
Script
my @d; my %s; sub out { my ($deep) = @_; for (my $i = 0; $i < $deep; $i++) { print "$d[$i]"; } print "\n"; } sub dice { my ($start, $deep, $sum) = @_; if ($sum == 25) { out($deep); } if ($deep < 10 && $sum < 25) { for (my $i = $start; $i <= 6; $i++) { $d[$deep] = $i; dice($i, $deep + 1, $sum + $i); } } } dice(1); Result
1111111666 1111112566 1111113466 1111113556 1111114456 1111114555 1111122466 1111122556 1111123366 1111123456 1111123555 1111124446 1111124455 111112666 1111133356 1111133446 1111133455 1111134445 111113566 1111144444 111114466 111114556 111115555 1111222366 1111222456 1111222555 1111223356 1111223446 1111223455 1111224445 111122566 1111233346 1111233355 1111233445 1111234444 111123466 111123556 111124456 111124555 1111333336 1111333345 1111333444 111133366 111133456 111133555 111134446 111134455 11113666 111144445 11114566 11115556 1112222266 1112222356 1112222446 1112222455 1112223346 1112223355 1112223445 1112224444 111222466 111222556 1112233336 1112233345 1112233444 111223366 111223456 111223555 111224446 111224455 11122666 1112333335 1112333344 111233356 111233446 111233455 111234445 11123566 111244444 11124466 11124556 11125555 1113333334 111333346 111333355 111333445 111334444 11133466 11133556 11134456 11134555 11144446 11144455 1114666 1115566 1122222256 1122222346 1122222355 1122222445 1122223336 1122223345 1122223444 112222366 112222456 112222555 1122233335 1122233344 112223356 112223446 112223455 112224445 11222566 1122333334 112233346 112233355 112233445 112234444 11223466 11223556 11224456 11224555 1123333333 112333336 112333345 112333444 11233366 11233456 11233555 11234446 11234455 1123666 11244445 1124566 1125556 113333335 113333344 11333356 11333446 11333455 11334445 1133566 11344444 1134466 1134556 1135555 1144456 1144555 115666 1222222246 1222222255 1222222336 1222222345 1222222444 122222266 1222223335 1222223344 122222356 122222446 122222455 1222233334 122223346 122223355 122223445 122224444 12222466 12222556 1222333333 122233336 122233345 122233444 12223366 12223456 12223555 12224446 12224455 1222666 122333335 122333344 12233356 12233446 12233455 12234445 1223566 12244444 1224466 1224556 1225555 123333334 12333346 12333355 12333445 12334444 1233466 1233556 1234456 1234555 1244446 1244455 124666 125566 133333333 13333336 13333345 13333444 1333366 1333456 1333555 1334446 1334455 133666 1344445 134566 135556 1444444 144466 144556 145555 16666 2222222236 2222222245 2222222335 2222222344 222222256 2222223334 222222346 222222355 222222445 2222233333 222223336 222223345 222223444 22222366 22222456 22222555 222233335 222233344 22223356 22223446 22223455 22224445 2222566 222333334 22233346 22233355 22233445 22234444 2223466 2223556 2224456 2224555 223333333 22333336 22333345 22333444 2233366 2233456 2233555 2234446 2234455 223666 2244445 224566 225556 23333335 23333344 2333356 2333446 2333455 2334445 233566 2344444 234466 234556 235555 244456 244555 25666 33333334 3333346 3333355 3333445 3334444 333466 333556 334456 334555 344446 344455 34666 35566 444445 44566 45556 55555 Only 294 possible options. However, this is only half the battle. We are more interested not in the layouts themselves, but in the ways in which we can place the points of the taken figure in each of them. I will not bore the reader with detailed reasoning, I will show only the script and the final result of its work:
Script
my @d; my %s; sub out { my ($deep) = @_; for (my $i = 0; $i < $deep; $i++) { print "$d[$i]"; } print "\n"; } sub proc { my ($x, $r, $m) = @_; if ($x == 0) { $s{$r}++; } else { my $n = $x % 10; for (my $i = 0; $i < $n; $i++) { proc(int($x / 10), $r + $i * $m, $m * 10); } } } sub alloc { my ($x, $deep, $res) = @_; if ($x == 0) { proc($res, 0, 1); } else { my $vl = 6; for (my $i = 0; $i < $deep; $i++) { if ($d[$i] < $vl) { $vl = $d[$i]; } } if ($vl < 6) { my $cn = 0; my $ix = 0; for (my $i = 0; $i < $deep; $i++) { if ($d[$i] == $vl) { $cn++; $ix = $i; } } my $y = $d[$ix]; $d[$ix] = 6; $x -= 6 - $vl; if ($x < 0) { $x = 0; } alloc($x, $deep, $res * 10 + $cn); $d[$ix] = $y; } } } sub dice { my ($start, $deep, $sum) = @_; if ($sum == 25) { for (my $i = 0; $i < $deep; $i++) { my $x = $d[$i]; $d[$i] = 6; alloc($x, $deep, 0); $d[$i] = $x; } } if ($deep < 10 && $sum < 25) { for (my $i = $start; $i <= 6; $i++) { $d[$deep] = $i; dice($i, $deep + 1, $sum + $i); } } } dice(1, 0, 0); my $all; foreach my $k (sort { $s{$a} <=> $s{$b} } keys %s) { $all += $s{$k}; print "$k\t=> $s{$k}\n"; } print "\n$all\n"; Result
102 => 1 331 => 1 200 => 1 ... 22 => 93 5 => 106 21 => 152 20 => 152 11 => 152 10 => 220 4 => 259 3 => 584 2 => 1061 1 => 1677 0 => 2407 7954 — , . , «20» , ( 0), , . , , «» , «3333445» (, «» «»). , , «» , 30% (2407/7954) , , 64%!
Especially for such cases, ZoG provides an interesting interface feature. In performing a move, the player indicates two fields: the initial and the final. In the event that there are several different possible moves connecting the selected pair of fields, the player is given a choice (pop-up menu). The simplest example is the transformation of pawns in Chess . Having reached the last rank, the pawn can turn into any of the pieces (from the bishop to the queen) and the choice must be made by the player. This is the option that I decided to use.
For Hansel and Gretel!
— , ZoG , , ZSG-. , . , , , . , ( ) 10, . . ( , ), . , . 0, .
alloc-path « ». , 105 , , . , 4 . , :
, Axiom ( ). ? Very simple! , . ( exchange -), . , .
VARIABLE alloc-path VARIABLE alloc-val VARIABLE alloc-target VARIABLE alloc-pos : alloc-to ( pos -- ) DUP add-pos DUP val-at 6 SWAP - DUP alloc-val @ > IF DROP alloc-val @ 0 alloc-val ! ELSE alloc-val @ OVER - alloc-val ! ENDIF my-next-player ROT ROT OVER piece-type-at + SWAP create-player-piece-type-at ; : alloc ( -- ) 6 0 BEGIN DUP enemy-at? OVER not-in-pos? AND IF SWAP OVER val-at MIN SWAP ENDIF 1+ DUP A9 > UNTIL DROP DUP 6 < IF alloc-target ! alloc-path @ 10 MOD alloc-pos ! 0 BEGIN DUP enemy-at? OVER not-in-pos? AND IF DUP val-at alloc-target @ = IF alloc-pos @ 0= IF DUP alloc-to 0 alloc-target ! DROP A9 ELSE alloc-pos -- ENDIF ENDIF ENDIF 1+ DUP A9 > UNTIL DROP alloc-target @ 0= verify alloc-val @ 0> IF alloc-path @ 10 / alloc-path ! RECURSE ENDIF ELSE DROP ENDIF ; : alloc-all ( -- ) 0 pos-count ! here add-pos alloc ; alloc-path « ». , 105 , , . , 4 . , :
: eat ( 'dir n -- ) LITE-VERSION NOT IF check-pass check-neg ENDIF + alloc-path ! val SWAP BEGIN step SWAP 1- DUP 0= IF TRUE ELSE my-empty? verify SWAP FALSE ENDIF UNTIL DROP from here move LITE-VERSION NOT enemy? AND IF from piece-type-at mark - ABS mark SWAP - create-piece-type ENDIF bump DROP here E5 <> verify enemy? verify LITE-VERSION NOT IF clear-neg set-pass ENDIF + val alloc-val ! + alloc-all add-move ; : eat-nw-0 ( -- ) ['] nw 0 eat ; : eat-sw-0 ( -- ) ['] sw 0 eat ; : eat-ne-0 ( -- ) ['] ne 0 eat ; : eat-se-0 ( -- ) ['] se 0 eat ; : eat-w-0 ( -- ) ['] w 0 eat ; : eat-e-0 ( -- ) ['] e 0 eat ; : eat-nw-1 ( -- ) ['] nw 1 eat ; : eat-sw-1 ( -- ) ['] sw 1 eat ; : eat-ne-1 ( -- ) ['] ne 1 eat ; : eat-se-1 ( -- ) ['] se 1 eat ; : eat-w-1 ( -- ) ['] w 1 eat ; : eat-e-1 ( -- ) ['] e 1 eat ; : eat-nw-2 ( -- ) ['] nw 2 eat ; : eat-sw-2 ( -- ) ['] sw 2 eat ; : eat-ne-2 ( -- ) ['] ne 2 eat ; : eat-se-2 ( -- ) ['] se 2 eat ; : eat-w-2 ( -- ) ['] w 2 eat ; : eat-e-2 ( -- ) ['] e 2 eat ; : eat-nw-3 ( -- ) ['] nw 3 eat ; : eat-sw-3 ( -- ) ['] sw 3 eat ; : eat-ne-3 ( -- ) ['] ne 3 eat ; : eat-se-3 ( -- ) ['] se 3 eat ; : eat-w-3 ( -- ) ['] w 3 eat ; : eat-e-3 ( -- ) ['] e 3 eat ; {moves p-moves {move} split-nw-0 {move-type} normal-priority {move} split-ne-0 {move-type} normal-priority {move} split-sw-0 {move-type} normal-priority {move} split-se-0 {move-type} normal-priority {move} split-w-0 {move-type} normal-priority {move} split-e-0 {move-type} normal-priority {move} split-nw-1 {move-type} normal-priority {move} split-ne-1 {move-type} normal-priority {move} split-sw-1 {move-type} normal-priority {move} split-se-1 {move-type} normal-priority {move} split-w-1 {move-type} normal-priority {move} split-e-1 {move-type} normal-priority + {move} eat-nw-0 {move-type} normal-priority + {move} eat-ne-0 {move-type} normal-priority + {move} eat-sw-0 {move-type} normal-priority + {move} eat-se-0 {move-type} normal-priority + {move} eat-w-0 {move-type} normal-priority + {move} eat-e-0 {move-type} normal-priority + {move} eat-nw-1 {move-type} normal-priority + {move} eat-ne-1 {move-type} normal-priority + {move} eat-sw-1 {move-type} normal-priority + {move} eat-se-1 {move-type} normal-priority + {move} eat-w-1 {move-type} normal-priority + {move} eat-e-1 {move-type} normal-priority + {move} eat-nw-2 {move-type} normal-priority + {move} eat-ne-2 {move-type} normal-priority + {move} eat-sw-2 {move-type} normal-priority + {move} eat-se-2 {move-type} normal-priority + {move} eat-w-2 {move-type} normal-priority + {move} eat-e-2 {move-type} normal-priority + {move} eat-nw-3 {move-type} normal-priority + {move} eat-ne-3 {move-type} normal-priority + {move} eat-sw-3 {move-type} normal-priority + {move} eat-se-3 {move-type} normal-priority + {move} eat-w-3 {move-type} normal-priority + {move} eat-e-3 {move-type} normal-priority {move} slide-nw {move-type} normal-priority {move} slide-ne {move-type} normal-priority {move} slide-sw {move-type} normal-priority {move} slide-se {move-type} normal-priority {move} slide-w {move-type} normal-priority {move} slide-e {move-type} normal-priority -( {move} exchange-1-nw {move-type} normal-priority - {move} exchange-1-ne {move-type} normal-priority - {move} exchange-1-sw {move-type} normal-priority - {move} exchange-1-se {move-type} normal-priority - {move} exchange-1-w {move-type} normal-priority - {move} exchange-1-e {move-type} normal-priority - {move} exchange-2-nw {move-type} normal-priority - {move} exchange-2-ne {move-type} normal-priority - {move} exchange-2-sw {move-type} normal-priority - {move} exchange-2-se {move-type} normal-priority - {move} exchange-2-w {move-type} normal-priority - {move} exchange-2-e {move-type} normal-priority - {move} exchange-3-nw {move-type} normal-priority - {move} exchange-3-ne {move-type} normal-priority - {move} exchange-3-sw {move-type} normal-priority - {move} exchange-3-se {move-type} normal-priority - {move} exchange-3-w {move-type} normal-priority - {move} exchange-3-e {move-type} normal-priority - {move} exchange-4-nw {move-type} normal-priority - {move} exchange-4-ne {move-type} normal-priority - {move} exchange-4-sw {move-type} normal-priority - {move} exchange-4-se {move-type} normal-priority - {move} exchange-4-w {move-type} normal-priority - {move} exchange-4-e {move-type} normal-priority - {move} exchange-5-nw {move-type} normal-priority - {move} exchange-5-ne {move-type} normal-priority - {move} exchange-5-sw {move-type} normal-priority - {move} exchange-5-se {move-type} normal-priority - {move} exchange-5-w {move-type} normal-priority - {move} exchange-5-e {move-type} normal-priority ) moves} , Axiom ( ). ? Very simple! , . ( exchange -), . , .
Strictly speaking, this is not a completely correct solution. According to the Chase rules, it’s not the player who made the move, but his opponent, who should distribute the points. I have no idea how this can be achieved using ZoG, but there is a very simple workaround. The ZoG interface provides a convenient interface for editing the board. Using popup menu commands, a player can delete any piece on the board or create another one. This feature is indispensable for debugging and I often use it. In general, a player who did not like the automatic distribution of points, can easily redistribute them manually (the sequence of turns, while not disturbed). Only minimal care should be taken. In the editing process, you should not allow a situation where one of the players has less than 5 pieces left, since in this case,he will be credited immediately and the game will be stopped.
... count to one!
Since the idea of ​​the "variable" distribution of the eaten glasses failed, I returned to the development of the game, through ZRF. Axiom-implementation, in principle, also worked, but it still lacked AI (the standard ZoG Axiom does not know how to use). In general, this task comes down to the correct coding of the evaluation function (for aesthetes there is also the “ Custom Engine ”), but this is not quite easy! In any case, the standard evaluation function, taking into account mobility and material balance, in Chase showed itself not in the best way.
Few details
, , :
— mobility . — , . , , — , , :
, «» « », . — , . , , Axiom :
«» , . , , ! AI . , . , / , ( , ), Chamber ., , ZRF. AI ZoG- , .
: OnEvaluate ( -- score ) mobility current-player material-balance KOEFF * + ; — mobility . — , . , , — , , :
: mobility ( -- score ) move-count current-player TRUE 0 $GenerateMoves move-count - $DeallocateMoves ; , «» « », . — , . , , Axiom :
{pieces {piece} p1 {moves} p-moves 6 {value} {piece} p2 {moves} p-moves 5 {value} {piece} p3 {moves} p-moves 4 {value} {piece} p4 {moves} p-moves 3 {value} {piece} p5 {moves} p-moves 2 {value} {piece} p6 {moves} p-moves 1 {value} pieces} «» , . , , ! AI . , . , / , ( , ), Chamber ., , ZRF. AI ZoG- , .
There was only one little thing left - there was no arithmetic at all in the ZRF! Chase is a game in which you constantly have to count! In some cases, you can get out. For example, when determining the defeat of a player, instead of scoring points (up to 25) on all figures, it can be limited to a standard check of the number of figures. Since 25 points are obviously impossible to place on 4 pieces, and it is always possible to distribute to a greater number of pieces, the following conditions for completing the game are enough:
(loss-condition (Red White) (pieces-remaining 4) ) (loss-condition (Red White) (pieces-remaining 3) ) The second check is necessary, since the situation in the game is possible when two figures are taken at once (after splitting the figure in the Chamber ). Unfortunately, there is one task in which integer arithmetic is necessary! Of course, this is the distribution of “eaten” points. In ZRF, I'm not trying to offer several possible distribution options, to choose from. I just need to go around all the figures, starting with the younger ones, and correctly add to them not yet distributed points. Here is how I do it:
Mostly from sticks
( ). ZRF- , ( ). ( ) . , «», ( ) :
— :
, , . , . . ZRF — , - !
, . ( , ), , , , «». ! :
, . «» ? , , ?
alloc-all , x ( — 12, ). x 0, , p1 p5 ( , , ). alloc-to . . , ( p1 5 . p2 — 4 ..). , x , — y . ( 4), , .
/
(define clear (set-flag $1-8 false) (set-flag $1-4 false) (set-flag $1-2 false) (set-flag $1-1 false) ) (define inc (if (flag? $1-1) (set-flag $1-1 false) (if (flag? $1-2) (set-flag $1-2 false) (if (flag? $1-4) (set-flag $1-4 false) (if (flag? $1-8) (set-flag $1-8 false) else (set-flag $1-8 true) ) else (set-flag $1-4 true) ) else (set-flag $1-2 true) ) else (set-flag $1-1 true) ) ) (define dec (if (not-flag? $1-1) (set-flag $1-1 true) (if (not-flag? $1-2) (set-flag $1-2 true) (if (not-flag? $1-4) (set-flag $1-4 true) (if (not-flag? $1-8) (set-flag $1-8 true) else (set-flag $1-8 false) ) else (set-flag $1-4 false) ) else (set-flag $1-2 false) ) else (set-flag $1-1 false) ) ) — :
!
(define not-10? (or (not-flag? $1-8) (flag? $1-4) (not-flag? $1-2) (flag? $1-1) ) ) (define calc (clear x) mark START (while (on-board? next) next (if friend? (inc x) ) ) (verify (not-10? x)) back ) , , . , . . ZRF — , - !
(define init (clear $1) (if (or (piece? p1) (piece? p3) (piece? p5)) (set-flag $1-1 true) ) (if (or (piece? p2) (piece? p3) (piece? p6)) (set-flag $1-2 true) ) (if (or (piece? p4) (piece? p5) (piece? p6)) (set-flag $1-4 true) ) ) , . ( , ), , , , «». ! :
-
(define sum (while (not-0? $2) (inc $1) (dec $2) ) ) , . «» ? , , ?
(define try-alloc (if (is-0? x) (inc y) else (dec x) ) ) (define set-piece (if (am-i-red?) (create White $1) else (create Red $1) ) ) (define alloc-to (clear y) (if (piece? p1) (try-alloc) (try-alloc) (try-alloc) (try-alloc) (try-alloc) ) (if (piece? p2) (try-alloc) (try-alloc) (try-alloc) (try-alloc) ) (if (piece? p3) (try-alloc) (try-alloc) (try-alloc) ) (if (piece? p4) (try-alloc) (try-alloc) ) (if (piece? p5) (try-alloc) ) (if (is-0? y) (set-piece p6) else (if (is-1? y) (set-piece p5) else (if (is-2? y) (set-piece p4) else (if (is-3? y) (set-piece p3) else (set-piece p2) ) ) ) ) ) (define alloc (if (not-0? x) mark ST (while (on-board? next) next (if (and enemy? (piece? $1) (not-0? x) (not-position-flag? is-captured?)) (alloc-to) ) ) back ) ) (define alloc-all (alloc p1) (alloc p2) (alloc p3) (alloc p4) (alloc p5) ) alloc-all , x ( — 12, ). x 0, , p1 p5 ( , , ). alloc-to . . , ( p1 5 . p2 — 4 ..). , x , — y . ( 4), , .
As a result, all our “abnormal arithmetic” works with quite acceptable performance and AI does not suffer at all. It must be said that such experiments are not always so successful. For example, this version of the calculator (recall that there is no arithmetic in ZRF) can be considered solely as a joke. Its performance is just awful! But in our case, “abnormal programming” proved to be the best possible solution.
Source: https://habr.com/ru/post/278853/
All Articles