How we ur doing

    This game has no name.

           Victor Pelevin “Generation P” A

    road of a thousand starts with the first step.

           Lao Zi


    Regarding my previous article , the Habr effect worked in an unexpected way. The very first commentary on it, dear Nomad1, asked if I want to create a full-fledged implementation? I, at that moment, as usual, thought about my own and did not immediately understand him. Of course, it was not about creating a universal game engine (the thought of which haunts me), but about developing an implementation of the Ur game for mobile platforms. Although I had little idea, at that moment, how I could be useful, I agreed to help.

    Of course, all my developments for ZoG turned out to be completely useless here. ZRF is such a peculiar language that all its solutions and idioms are of value only to ZRF developers and no one else (for the most part, they all solve the problems of ZRF itself). Fortunately, Alexei already had a ready-made framework, which allowed programming the game logic in record time. My task was to verify the game rules and develop the principles of AI for this game.

    We tried as accurately as possible to reproduce the version of the rules proposed by Dmitry Skiryuk , since we consider it the most interesting (in terms of games) of all the proposed today.

    Remind the rules


    At your disposal are 7 novice fighters. Your task is to lead them across the river and return home. The gods will help you along the way.

    • If white color has fallen on one of the bones, you can take one step.
    • Две белых кости означают, что любой из ваших бойцов может переместиться на два шага.
    • Если белый цвет выпал на трёх костях, вы можете передвинуть любого из своих бойцов на три шага.
    • Три чёрных кости дают право сходить на четыре шага вперёд.

    Если ни один из ваших бойцов не может ходить, вы пропускаете ход.

    Не все места, через которые вы пройдете одинаковы.

    Это врата Иштар — покровительницы воинов.
    Остановившись здесь, вы имеете право сделать ещё один ход.

    Здесь можно разбить лагерь. В лагере могут находиться не более 4 ваших бойцов.
    Пока в лагере есть хотя бы один боец, враг не может войти в это место.

    Это святое место. Враг не может напасть на вас здесь, но и вы не можете напасть на него. Не более 4 бойцов (ваших и вашего противника) могут пребывать в этом месте. Помните, первым уходит тот, кто вошёл последним!

    Пройдя через это место, бойцы-новички превращаются в воинов-ветеранов. Новичек не может одолеть в бою ветерана, но и ветераны не нападают на новичков.

    Никто не может одолеть ветерана, пока он находится в этом месте.
             

    Выйдя из лагеря, вы встретитесь с врагом. Если один из ваших бойцов будет убит, вы получите ещё одного новичка.

    Семь воинов должны перейти реку и вернуться домой.
    Враг не должен вас опередить!

    One of the “highlights” of this variant of the rules is the process of “turning over” chips. Let me remind you that the chips are flipped so that the player does not get confused in the direction of their movement. Ordinary chips move towards the "small" block, inverted from it. But the “flipping" of chips also affects the gameplay. Only the same chips can “chop” each other. Ordinary chips cannot “cut” upside down chips 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 arose during the test run of the Simple Ur game variant, in which the board fields, except for the “outlets”, do not have any special properties. This congestion is not easy to disassemble at all (if there were no chips left in the reserve, the game would have ended on this). No matter how many points any player throws out, none of the chips blocking 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 offload “traffic”.

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



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

    The g2 field is also safe (but for a different reason). In this field “with eyes”, you can also build chips with a “column”, but only chips of the same color! While 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 more effectively introduce new chips into the game.

    Another important feature of the game are the fields with "sockets", which allow you to make an additional move when you stop at them. 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 “go around the sockets”. It is often possible to make 2-3 moves, before the move goes to the enemy.

    A little apart, in my opinion, is a rule that does not allow “cutting down” an inverted chip that has reached a2. You can argue for a long time 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 arose repeatedly when the winnings of one of the parties were determined by whether this rule is valid or not. We realized it also because it brings intrigue to the game. When the opponent brought his last upside-down chip to a2, he should be very lucky so that we could win against him. We can’t cut this chip in any way, and as soon as the opponent has a “one”, the game will be over.

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

    This directly affects the gameplay. Positions at a distance of 3-4 cells from the opponent's catching chips are much safer than a distance of 1-2 cells. But after all, not one but several chips can catch us, in addition, we must take into account the “safe” fields. In general, this game is not at all as simple as it seems at first glance.

    We should also talk about gaming AI. It is very important that the program plays at approximately the same level as the person. The ZoG implementation, for example, plays very weakly. Often manages 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 maintain a balance. The game has four difficulty levels. At the highest level, I manage to win in about half of the games, with a margin of 1-2 chips. A low level of difficulty may be of interest to the "casual".

    We originally wanted to use the alpha beta algorithm.to implement AI, but quickly abandoned this idea. The random nature of the generation of moves has its own specifics. In fact, the only important thing is that you are not “eaten” (with a high probability) the next move. Looking further is unprofitable and, in general, useless. This game does not require “artificial intelligence”, but rather an “artificial instinct”, but the “instinct” is rather complicated. Here is the final pseudocode I got:

    Game AI Implementation
    - Segment 1 вес = 0.5
      - level >= 3
        - level < 8
          - Если есть ходы на "розетки", выбрать из них ход, расположенный дальше от старта
        - level >= 8
          - Если есть ход на "розетку"не оставляющий g2 пустой, выбрать ход расположенный дальше от старта
    - Segment 2 вес = 0.3
      - level >= 5
        - Если имеются ходы со срубанием перевернутых фишек, выбрать наиболее удаленный от старта
        - Если имеются ходы со срубанием обычных фишек, выбрать ближайший к старту
      - level = 4
        - Если имеются ходы со срубанием, выбрать из них ход, расположенный дальше от старта
      - level >= 8
        - Если есть возможность хода на g2 и поле пусто, идти туда
      - level >= 9
        - Если есть возможность занять g1 или h1, ходим туда
      - level >= 6
        - Если можно вывести фишку с поля, выбрать этот ход
      - level >= 5
        - Если на первых четырёх клетках нет фишек, выбрать ход со стартовой позиции
      - level >= 4
        - Если имеются ходы с блокированием, выбрать случайный из них
    - Segment 3 вес = 0.2
      - level < 8
        - level >= 7
          - Если имеется ход на поле не под боем, выбрать любой из них
        - level >= 2
          - Xод фишкой, расположенной дальше от старта
        - level = 1
          - Ход случайно выбранной фишкой
      - level >= 8
        - level = 8
          - Ход на максимальном расстоянии от старта на поле не под боем, не оставляющий g2 пустой
          - Ход на максимальном расстоянии от старта, не оставляющий g2 пустой
        - level = 9
          - Ход на максимальном расстоянии от старта на поле не под боем, не оставляющий g2 пустой, не с g1 или h1
          - Ход на максимальном расстоянии от старта, не оставляющий g2 пустой, не с g1 или h1
        - Любой оставшийся ход
    


    There are 9 game levels defined that take into account various aspects of the current position. In fact, in a more complex game, such as Chess, such heuristics would control the order of enumeration of moves (for viewing the “best” moves in the first place). Our game is simpler. In it, heuristics can be used directly to select the "best" move. As I said above, this is enough to make the program play at about the same level as a person.

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



    This game is really nice to play! She brings me back to the time when we went to visit each other not only to drink and have a bite. Yes, then the grass was greener and the trees were taller, but that’s not the point. We almost stopped playing Chess and Checkers. We're 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. Homo Ludens - “The Man Playing” forgot about board games. Of course, the development of just one game for iOS and Android will not fix this, but, perhaps, to some extent, will help regain interest in board games? I hope so.

    Also popular now: