How we ur did

This game has no name.

Victor Pelevin "Generation P"

The road to a thousand li begins with the first step.

Lao Tzu

')
In relation to my previous article , the Habr effect worked in unexpected ways. The very first comment to it, dear Nomad1, asked if I wanted to create a full-fledged implementation? I, at that moment, as usual, thought about my own and did not immediately understand it. Of course, it was not about creating a universal game engine (the thought of which does not bother me), but about developing the implementation of the game Ur for mobile platforms. Although I had little idea, at that time, with what I could be useful, I agreed to help.

Of course, all my achievements for ZoG were completely useless here. ZRF is so peculiar language that all its solutions and idioms have value only for ZRF-developers and for no one else (for the most part, they all solve the problems of ZRF itself). Fortunately, Alexey already had a ready-made framework, which made it possible to program the game logic in record time. My task was to reconcile the game rules and develop the principles of the AI ​​for this game.

We have tried to reproduce as accurately as possible the version of the rules proposed by Dmitry Skiryuk , since we consider it the most interesting (in the game relation) of all proposed to date.


One of the "highlights" of this version of the rules is the process of "turning over" the chips. Let me remind you that the chips are turned over so that the player does not get confused in the direction of their movement. Ordinary chips move in the direction of the "small" block, inverted - from him. But "turning over" chips affects the gameplay. Only identical chips can "chop" each other. Ordinary chips can not "cut down" inverted and vice versa. This greatly diversifies the gameplay, but creates a threat of "congestion." For example, in the process of debugging a ZoG application, I had the following situation:



This is the real position that has arisen during the test run of the “Simple Ur” game variant, in which the board’s fields, apart from the “sockets”, do not have any special properties. This congestion is not at all easy to disassemble (if there were no chips left in reserve, the game would have ended with this). No matter how many points any player has thrown, none of the blocks that blocked each other will be able to move. I think this is the main reason why Dmitry introduced special fields into the game. Fields c2 and f2 (in chess notation) are designed to relieve “traffic”.

In these fields, chips of any color can be arranged in a "column" on each other (but not more than 4 pieces). In this case, the lower chips do not return to the reserve, but simply remain blocked until the upper chip passes further. This simple rule change has a magical effect on gameplay. Congestion ceases to exist. Faced chips easily diverge! But the surprises associated with turning the chips do not end there. Look at the following position:



According to Dmitry's rules, the chip turns over not when it gets on the transformation field (h1 for white and h3 for black), but passing through it! As a result, the white chip cannot cut black on h3, since it must be turned upside down, making any move with h1. But she easily hits an inverted black chip on h2, turning over in the process! This rule, in fact, makes the fields g1, h1, g3 and h3 safe. These fields are the perfect place for ambush.

The g2 field is also safe (but for a different reason). In this field with eyes, chips can also be arranged in a “column”, but only chips of the same color! As long as this field is occupied by at least one of our chips, the enemy chip cannot enter it. Similar fields on b1, b3, d1 and d3 help to more effectively introduce new chips into the game.

Another important feature of the game is the field with "sockets", which allow when you stop on them, make an extra move. The introduction of these fields gives the game a truly hurricane character. If we play with a group of chips, it is not necessary to throw out the “fours” each time in order to “walk on the rosettes”. It is often possible to make 2-3 moves before the move goes to the opponent.

A little apart, in my opinion, is the rule that does not allow "to cut down" an inverted chip that has reached a2. One can argue long about the validity or usefulness of this rule, but the fact that it works is an indisputable fact. During the test runs of the game, situations repeatedly arose when the winning of one of the parties was determined by whether this rule is valid or not. We implemented it also because it introduces intrigue into the game. When the opponent brought his last chip up to a2, he must be very lucky so that we could win him. We can not cut this chip in any way, but as soon as the enemy has a “one”, the game will be over.

If you think that on this game surprises from Ur end, you are mistaken! Why are three D2 bones used for the game, and not one D4? D4- type game dice (with four facets) were widespread in the ancient world. Why in the game was not used one "bone" instead of three? This is not obvious at first glance, but when using such a game scheme, the ejected points are not equally probable. Units and twos fall out three times more often than threes and fours.

This directly affects the gameplay. Positions at a distance of 3-4 cells from the enemy’s catching chips are much safer than a distance of 1-2 cells. But not one but several chips can catch up with us, moreover, “safe” fields should be taken into account. In general, this game is not so simple as it seems at first glance.

We should also talk about the game AI. It is very important that the program plays at approximately the same level as the person. The ZoG implementation, for example, plays very poorly. Often it is possible to win her "dry". Playing with her is not very interesting. But if the program will constantly win, it can also “scare away” the user. We tried to keep a balance. The game has four levels of difficulty. At the highest level, I manage to win in about half of the games, with a margin of 1-2 chips. The low level of complexity may be of interest to “casual players”.

Initially, we wanted to use the alpha-beta algorithm to implement AI, but we quickly abandoned this idea. The random nature of the generation of moves has its own specifics. In fact, it is only important that you are not “eaten” (with a high probability) on the next turn. Looking further is expensive and, on the whole, useless. This game requires not “artificial intelligence”, but rather “artificial instinct”, but “instinct” rather complicated. Here is the pseudo-code that I ended up with:


Here, 9 game levels are defined, taking into account various aspects of the current position. In fact, in a more complex game, like Chess, similar heuristics would control the order of iterating moves (to see the “best” moves first). Our game is easier. In it, heuristics can be used directly to select the “best” move. As I said above, this is quite enough for the program to play at about the same level as the person.

Here it is, “Forgotten Game of Ur”, which we received as a result:



This game is really nice to play! She brings me back to the times when we visited each other not only to drink and eat. Yes, then the grass was greener and the trees higher, but that was not the point. We almost stopped playing Chess and Checkers. We are not going to families to play Bridge. Go and Shogi are unattainable exotic for most of us. Even the old dominoes disappeared from the yard somewhere. Homo Ludens - “The Man Playing” has forgotten about board games. Of course, the development of just one game for iOS and Android will not fix this, but perhaps in some way it will help to restore interest in board games? I hope so.