More than go

When throwing pebbles into the water, look at the circles they form;
otherwise, such a throwing will be empty fun.

Kozma bars " Fruits of meditation "

This game is a real unfinished . I started working on it back in June ! I can’t say that every day I broke up, but she spoiled a lot of blood for me. Today, this is my most difficult project in Axiom . In terms of the (highly non-trivial) code, MarGo is comparable, perhaps, to Rhythmomachia .
')
What is special about this game? Was it worth it to suffer so much? I will tell, and you judge.

Surface similarity

Attempts to “improve” Go were made repeatedly, but they were rarely successful. MarGo, in my opinion, just such a rarity! The main thing that is captivating in this game is the fact that it is above the set of Go. I already wrote about how the seemingly simple rules of Guo lead to unexpectedly complex tactical constructions. I will not repeat myself, let me just say that everything I wrote about Go also applies to MarGo too (as long as we do not go beyond the limits of the plane). So, for example, looks like the famous " latch " - the simplest victim of one stone, in order to get three:

By the way

Using any “clips” on the position above is completely unnecessary! Black is already doomed, there is no need to “finish” it. But why use such small boards in MarGo? The main reason is that the game is not on the plane, but in volume. Players build pyramids and hardly anyone has the patience to do this on a 19x19 board. The standard for MarGo is a 9x9 board, in Go it is used mainly for training beginners!

For me, this was a great relief, because already when using the 9x9 board, I ran into problems of lack of memory. I had to optimize its use by removing extra strings from the array. This moment is quite obvious - by building a pyramid, we can never place figures on most of the fields of a three-dimensional board.

When determining the status of groups, only empty points located in the plane of the board are important. Each stone of a “living” group must be connected (directly or through other stones) to at least one of such points (called “ dame ”). As soon as the last dame is closed, the group becomes dead and is removed from the board.

How it works?

The basis of Go functionality is the mechanism of removing stones in the environment. It works quite simply. To begin with, it is necessary to identify the stones that are certainly alive (they are adjacent to empty points on the board). Then, all stones (of the same color) adjacent to any of the previously added stones should be added to the group of “living” stones.

Everything would be fine if it were not for the stupid semantics of the progress in ZoG / Axiom. Throughout the course of construction of the course, the contents of the board looks like at the time of the start of the calculation (all changes made by the course will become visible only after its completion). In simple cases, this can be fought, but our game has never been easy! Due to the fact that we create the illusion of three-dimensionality, adding only one piece to the board can lead to the displacement of a large number of tile-figures. Handling all these "special cases" in a special way is completely unrealistic! I had to divide the addition of a new piece to the board and the subsequent deletion of the “killed” pieces:

{players {player} W {player} B {player} ?C {random} players} {turn-order {turn} W {of-type} normal {turn} ?C {for-player} W {of-type} clean {turn} B {of-type} normal {turn} ?C {for-player} B {of-type} clean turn-order}

In order for the “cleaning” to be performed automatically, we had to create another player acting on behalf of the owners of the figures. His move consists in placing a special (invisible) figure on one of the unused board fields (there are a lot of such fields, despite optimization ). All actions to remove the "dead" groups are performed as a "side effect" of this move:

 : drop-m ( -- ) here a1 = verify (   ? ) drop (   ) ['] my-enemy? (    ) init-alive (       ) proceed-alive (     ) capture-all (         ) captured-tiles @ 0= IF (       ) ['] my-friend? (        ) init-alive proceed-alive capture-all ENDIF add-move (    ) ;

This code solves two problems at once:

Deleting all enemy groups killed by the last move
A friendly group's suicide, if the move was suicidal and you could not kill any of your enemies

More details

 TOTAL [] alive[] (    ) VARIABLE alive-count (    ) : not-alive? ( -- ? ) (    ) TRUE 0 BEGIN DUP alive-count @ < IF DUP alive[] @ here = IF SWAP DROP FALSE SWAP TRUE ELSE 1+ FALSE ENDIF ELSE TRUE ENDIF UNTIL DROP ; : add-alive ( -- ) (    ) not-alive? alive-count @ TOTAL < AND IF (    ! ) here alive-count @ alive[] ! alive-count ++ ENDIF ; : check-alive ( 'op 'dir -- ) (     ) EXECUTE IF EXECUTE IF add-alive ENDIF ELSE DROP ENDIF ; : init-alive ( 'op -- 'op ) (   ) 0 alive-count ! 0 BEGIN (       ! ) DUP empty-at? IF DUP to OVER ['] n check-alive DUP to OVER ['] s check-alive DUP to OVER ['] w check-alive DUP to OVER ['] e check-alive ENDIF 1+ DUP PLANE >= UNTIL DROP ; : proceed-alive ( 'op -- 'op ) (   ""  ) 0 BEGIN (     ) DUP alive-count @ < IF DUP alive[] @ to OVER ['] n check-alive DUP alive[] @ to OVER ['] s check-alive DUP alive[] @ to OVER ['] w check-alive DUP alive[] @ to OVER ['] e check-alive 1+ FALSE ELSE TRUE ENDIF UNTIL DROP ;

The small size of the board leads to high competition for dame . Those of you who play Go must know that the fights on a small board (9x9) can be much more fierce than playing on a standard board (19x19). From the very first move, players enter into tight contact and are forced to continuously solve the “life and death” tasks. Such is the game in MarGo, but if that were the case, I would not talk about it.

Main difference

The name of the game consists of two words: "marbles" (balls) and "Go". Together it turns out - “the game of go balls”. What is the difference from the traditional game? In its three-dimensionality! Attempts to play Go on three-dimensional boards were made several times (I wrote about a program that allows you to play on arbitrary graphs), but in most of these cases, the game balance was seriously affected. The exception, perhaps, is only a board that imitates a diamond crystal lattice. It is much like a classic flat board. Each node has from 2 to 4 neighbors:

MarGo's approach is completely different. The ball can not just "hang in the air." In order to “rise above the board,” he must rely on four other balls (his own or his opponent's). Of course, in order for this ball to remain alive, it must be in contact with a group that has access to at least one dame . Vertical directions are added to the orthogonal connections lying in the plane of the board, connecting the balls at the base of the pyramid with its top.

This connection works both ways. Access to the dame not only gives life to the "top" of the pyramid, but can also move on to the lower layers, bending around enemy figures lying in the plane of the board. This alone can make the game more interesting, but there is another, much less obvious point. As long as the stone at the top of the pyramid remains “alive”, the stones from its base cannot be removed, even if they belong to the “dead” group!

Such stones, deprived of access to a dame and crushed by figures of a different color, are called “zombies” and they remain on the board when the rest of the “killed” group leaves it. Zombies are equated to captured stones (removed from the board), but as long as they remain on the board, they can “transfer” access to the dam to other stones (if it suddenly appears). In addition, zombies can be brought back to life by removing the top of the pyramid.

Invasion of three dimensions

I already wrote that to create the effect of three-dimensionality, I had to divide each figure into 4 tiles. It works, but the snag is that tile figures have to be placed on a “three-dimensional” board in a rather bizarre way. There is no way to avoid this. All tiles visible "from above" must be in the same plane. This layout pattern also has its own additional advantages, but the navigation in it is too intricate. For starters, I needed a meditation mandala :

 4 AA 3 8 8|9 9 2 5 5|6 6|7 7 1 1 1|2 2|3 3|4 4 + ABCDEFGH 1 1|5|8|AA|9|7|4 2 1|2 2|3 3|4 3 5|6 6|7 4 8|9

I agree that the picture is so-so, but it allowed me to somehow orient myself. I needed directions for the natural movement within this scheme. Fortunately, from the point of view of the Axiom, directions are just functions that change the position of the current position marker as a side effect of its call (the main result of calling such a function is returning a boolean value indicating success of the move). In general, the directions could be redefined and, soon, I had a whole hierarchy of them:

The diagram shows only functions that lead strictly to the "north" (in a sense). Some of them I have used previously. The direction of ' n ', for example, I had to enter when I threw out extra lines from the “board” array, in order to optimize memory usage. The main part of the "rocket science" is a function that allows you to move in a plane parallel to the plane of the board:

I will not even try to comment on this.

 : common-internal ( 'dir -- ? ) here is-plane? IF get-height SWAP EXECUTE IF get-height - DUP 0= IF DROP TRUE ELSE 0> IF FALSE ELSE BEGIN d NOT empty? OR UNTIL empty? IF u verify ENDIF TRUE ENDIF ENDIF ELSE DROP FALSE ENDIF ELSE here OVER EXECUTE NOT empty? OR IF to BEGIN u NOT UNTIL EXECUTE ELSE 2DROP TRUE ENDIF ENDIF ;

Most of the subsequently found errors were associated with this function (and I am still not sure that I fixed them all). On its basis, such movements as north-internal, south-internal, etc. are constructed:

 : north-internal ( -- ? ) ['] n common-internal ; : south-internal ( -- ? ) ['] s common-internal ; : west-internal ( -- ? ) ['] w common-internal ; : east-internal ( -- ? ) ['] e common-internal ;

These are practically full-fledged functions of moving, possessing only one drawback. In case of unsuccessful movement, the position position of the current position becomes undefined. It is easy to fix. It is enough to remember the location of the marker before moving and restore it if it was not possible to move for any reason:

 : wrap-direction ( 'dir -- ? ) here (   "" ) SWAP EXECUTE IF (      ) DROP TRUE (    ,    ) ELSE to FALSE (   ,  ""    ) ENDIF ; : north ( -- ? ) ['] north-internal wrap-direction ; : south ( -- ? ) ['] south-internal wrap-direction ; : west ( -- ? ) ['] west-internal wrap-direction ; : east ( -- ? ) ['] east-internal wrap-direction ;

There are very few. In addition to the "horizontal" movements lying in the plane of the board, directions are needed leading from one plane to another ("up" and "down"):

Some more strange code without comment

 : up-internal ( -- ? ) here is-plane? IF FALSE ELSE d NOT empty? OR IF BEGIN u NOT UNTIL ENDIF TRUE ENDIF ; : down-internal ( -- ? ) here is-plane? IF d NOT empty? OR IF FALSE ELSE BEGIN d NOT empty? OR UNTIL empty? IF u verify ENDIF TRUE ENDIF ELSE u verify here is-plane? NOT ENDIF ; : up ( -- ? ) ['] up-internal wrap-direction ; : down ( -- ? ) ['] down-internal wrap-direction ;

That's all! Now we have a complete set of directions required for the detection of "connected" groups.

Zombies - an interesting new entity, generated by simple and logical rules of the game. Interesting, but not the only one! MarGo stockpiled other surprises.

Bridges and gorges

The stones at the top of the pyramid “pass” access to the dam to friendly stones, which might be surrounded, everything happens on a plane. There is another way to avoid the environment! But wait, this is exactly the reason why it is not very interesting to play Go in three dimensions . Groups getting too hard to kill! There is a way to fix it.

In Go, such a connection is considered not to be cut in principle, regardless of the possible errors of the player who built it. The stones standing nearby live and die together. They can not be separated, but not in MarGo! In this game, standing stones can be "cut" by building a bridge over them. The stones that are on the bottom, on opposite sides of the bridge, turn into two separate groups.

On the other side of the bridge

The essence of the "cutting" is that we can not move in the chosen direction. This means that we will have to expand the hierarchy of directions, which I wrote about above, adding a new direction, controlling the presence “above the head” of a bridge built of foreign figures. Since the rule of “cutting bridges” is very similar to the option (the game can be interesting without it), we define a constant flag that controls its operation:

 TRUE CONSTANT BRIDGE-CUTTING

Then everything is simple

 : is-covered? ( -- ? ) player up empty? NOT AND IF player <> ELSE DROP FALSE ENDIF ; : check-bridge? ( 'dir piece-type -- ? ) piece-type SWAP equal-types? IF here is-covered? IF SWAP OVER to EXECUTE IF is-covered? SWAP to ELSE to FALSE ENDIF ELSE to DROP FALSE ENDIF ELSE DROP FALSE ENDIF ; : common-cutting ( 'dir 'dir piece-type 'dir piece-type -- ? ) BRIDGE-CUTTING IF check-bridge? IF 2DROP TRUE ELSE check-bridge? ENDIF ELSE 2DROP 2DROP FALSE ENDIF IF DROP FALSE ELSE EXECUTE ENDIF ; : north-cutting ( -- ) ['] north ['] east nw-piece ['] west ne-piece common-cutting ; : south-cutting ( -- ) ['] south ['] east sw-piece ['] west se-piece common-cutting ; : west-cutting ( -- ) ['] west ['] south nw-piece ['] north sw-piece common-cutting ; : east-cutting ( -- ) ['] east ['] south ne-piece ['] north se-piece common-cutting ;

Is all the magic hidden in the check-bridge? . To define a “bridge” above your head, we “look” up in search of someone else’s tile. We do the same on the next tile. If both tiles are “covered” with figures of another color (different), we “chop” the corresponding direction, replacing the value returned by them with a false one.

Do you think the surprises are over on this? No matter how wrong!

The most difficult case

Suicidal moves are forbidden (and for the most part useless). A player can not put his stone "in the environment", if it does not take a single opponent stone. In Go, this is simple. If we take a group of stones, it must be in contact with the newly added stone and its “killing” will reveal the dame we need for survival. But in MarGo there are zombies!

Even taking a stone at the top of the pyramid, the white stone will still be “surrounded”, thereby creating an unacceptable position! Two black stones make up a “virtual group” protected by a “zombie” underlying it. It's funny that this protection is very ephemeral. If white, for some reason, manages to take any of the four stones next to him, the protection of the “virtual group” will cease to act. This is not just an artificial construction. Virtual groups - an important tactical component of the game MarGo! What do you say, for example, about the status of this position?

It looks like a completely surrounded group (with one “eye”), which the white began to eat. In principle, the way it is, but to “finish” the black group is not so simple. White can not just go to the lower left corner. Since two white stones surround only “zombies”, such a move will be considered suicidal. But black should not be in a hurry to eat the invading white stone:

Black adds a non-“zombie” stone to the board, thereby destroying the protection of the “virtual group”. White gets the right to go to the same place where his stone had just been eaten, taking five black stones. It turns out that the best solution for black is not to do anything? Of course, it is not. White has another opportunity to kill the group.

If black ignores this threat - his group is doomed! By connecting their groups, the white player will be able to safely occupy the last dame . Protection against such an invasion is obvious. The best opponent move is your best move!

Really difficult

As I wrote above, I had to divide the addition of a stone and the removal of “dead” groups into two successive moves (otherwise it would be very difficult). Among other inconveniences, this means that I cannot forbid a player to make a move, simply on the basis that he is "suicidal." In principle, this is not a very big problem. Let us make a move and let the added stone just die (maybe with a group of other stones of its color), but this is only part of the problem! Remember, I wrote something like this code?

 : drop-m ( -- ) here a1 = verify drop ['] my-enemy? init-alive proceed-alive check-zombies capture-all captured-tiles @ 0= IF ['] my-friend? init-alive proceed-alive check-zombies capture-all captured-tiles @ NEGATE update-variables ELSE captured-tiles @ update-variables ENDIF add-move ;

We are trying to remove the enemy’s stones and, if this failed, we try to remove ours (while counting the stones taken). So, this code does not work! Indeed, if you look at our cunning case, you can see that the enemy’s stones are removed, but the added stone still remains surrounded! This is really a problem. In order for everything to work properly, we must remove the dead stones of the enemy, then our own and, if we succeed, return the enemy’s stones to their place. Yes, in Axiom there are functions that allow you to create a copy of the board, make some changes to it, and then roll back everything, but I would not like to use them here! Fortunately, there is another, well-functioning mechanism for rolling back changes.

We divide the code for deleting "dead" groups into two parts

 {players {player} W {player} B {player} ?C {random} players} {turn-order {turn} W {of-type} high-priority {turn} ?C {for-player} W {turn} B {of-type} high-priority {turn} ?C {for-player} B turn-order} {move-priorities {move-priority} normal-priority {move-priority} low-priority move-priorities} {moves w-drop {move} drop-w {move-type} high-priority {move} drop-nw {move-type} high-priority moves} {moves n-drop {move} drop-n {move-type} high-priority {move} drop-ne {move-type} high-priority moves} {moves e-drop {move} drop-e {move-type} high-priority {move} drop-se {move-type} high-priority moves} {moves s-drop {move} drop-s {move-type} high-priority {move} drop-sw {move-type} high-priority moves} {moves m-drop {move} clear-e {move-type} normal-priority {move} clear-f {move-type} low-priority moves} {pieces {piece} M {drops} m-drop {piece} tw {drops} w-drop {piece} zw {piece} ww {piece} bw {piece} tn {drops} n-drop {piece} zn {piece} wn {piece} bn {piece} te {drops} e-drop {piece} ze {piece} we {piece} be {piece} ts {drops} s-drop {piece} zs {piece} ws {piece} bs pieces}

With a higher ( normal ) priority, the removal code of the enemy's dead groups (clear-e) will be executed, and with a low ( low ) - removal of their dead groups ( high level, outside the priority list, we reserve for the usual addition of stones to the board). Now everything works as it should. First, the move generator attempts to perform a higher-priority clear-e , at the end of which we check whether the added stone has got into the environment (prohibiting the move, if this happened). If the priority move fails any of the checks, the move generator itself rolls back all the changes, and fulfills the low - priority clear-f . This code is always successful. Sometimes a side effect of its execution is the removal of “suicide” groups.

Cleaning code too complicated

 : clear-e ( -- ) 0 captured-count ! here a1 = verify drop ['] my-enemy? init-alive proceed-alive check-zombies capture-all captured-tiles @ 0> verify captured-tiles @ update-variables ['] my-friend? init-alive proceed-alive check-zombies check-not-captured add-move ; : clear-f ( -- ) 0 captured-count ! here a1 = verify drop ['] my-friend? init-alive proceed-alive check-zombies capture-all captured-tiles @ 0> IF captured-tiles @ NEGATE update-variables ELSE DROP ENDIF add-move ;

In general, a little confused, but it works.

Without Ko no Go

Well, there is another difficult case , safely inherited from a more traditional version of the game. Since, as I said, in the plane of the board, all the rules of Go remain in force, it is possible to do the following focus:

If you somehow do not break off all this fun, players will be able to devour each other’s stones indefinitely. Of course, MarGo cannot allow this and prohibits moves leading to the repetition of the previous position. In the rules of the game , we are talking about the situational superko

Black cannot eat a white stone immediately and has to walk in another part of the board. The next move, white can connect.

From life invisible

Alas, I do not realize the detection of any positional or situational superko. This requires information about previous positions (at least hashes), but I do not have it! Fortunately, all these " cyclical ko ", " eternal life " and other exotic positions do not make the weather. In real Co-wrestling, almost always, simple Ko . We will catch him.

To prohibit a move to an “empty” item, you must make it non-empty.

 : drop-marks ( -- ) 0 BEGIN DUP captured-count @ < IF mark OVER captured[] @ create-piece-type-at 1+ FALSE ELSE TRUE ENDIF UNTIL DROP ; : clear-marks ( -- ) 0 BEGIN DUP empty-at? NOT IF DUP piece-type-at mark = IF DUP capture-at ENDIF ENDIF 1+ DUP PLANE >= UNTIL DROP ;

We can place invisible tiles on the board to make it impossible to move to the selected position. When making a move to any permitted item, we will simply remove this interference. Here, one of the important properties of MarGo plays into our hands. Any Ko-fight will always occur in the plane of the base of the board! So that the added "empty" tiles do not interfere with the determination of the status of groups, we will change the function of determining the void node:

 : my-empty-at? ( pos -- ? ) DUP curr-pos ! - empty-at? IF + DUP empty-at? SWAP piece-type-at mark = OR IF TRUE ELSE ... ENDIF ;

It remains to add Ko-mark on the board. We do this in the place of the enemy's stone shot, provided that if this stone had not been removed, the “suicide” group would consist of exactly one stone that had just been added. Sounds hard? In general, yes, the way it is.

What is behind the scenes?

Of course, not everything went smoothly. I simply could not implement some rules. Suicidal moves, for example, in MarGo are absolutely prohibited. This means that the player does not have the right to make a move which deprives a group (possibly consisting of only one stone that has just been added) of the last dame , provided that it does not take the opponent’s stones.

I was forced to divide the moves that performed the addition of a stone and the removal of the stones taken, which deprived me of any possibility of prohibiting "suicidal" moves. This may seem like a trifle. In the end, although the “suicidal” moves are prohibited in most variants of the Go rules, the Inga rules allow them. There is a good reason for this. There are (very rare) positions in which the killing of one’s own group allows the player to escape in a completely hopeless situation .

Seki will not bring points, but compared to the total loss of the group, this is a serious help, because the enemy will not receive points either! Unfortunately, one pulls the other. In MarGo (unlike Go), players are forbidden to miss a move. , , , , , . ? , .

, , . AI . ! «» , . AI ( ZoG DLL-engine ). AI, , , .

«» ( ), ( , , ). , . MarGo . , , «», . , . «» . , ! , .

, , , . , . MarGo , «». , 4x4, 16 , «» 4 ( , ). , 4x4 , . , ForthScript.

— . , , , , «» (, ), , , , , ( — ). , , «» , ZoG !

, , AI . , , .

Source: https://habr.com/ru/post/274043/

All Articles