How I Made a Game of Indians of Central America

I want to bring to your attention a short article about how I did for Android Puluk - the board game of the Indians of Central America.

I started “teaching” computers to human games barely learning how to program. The first was a calah (a type of mankala ) for the MK-61 calculator. Later - Wolf and Sheep , first for MS-DOS, and then for Android.

General information about the game

While reading GlukKazan articles on Habré, I came across an interesting LiveJournal by Dmitry Skiryuk with descriptions of board games from different nations of the world. One of them, the puluk , fascinated me so much that I decided to implement it for Android.

The history of the game , as well as its sacred significance for maize harvests, can be read in the LiveJournal of Dmitry. I will give here only the rules.

The board for puluk consists of 11 strips, the first and the last serving as "cities" for player chips. Each player has five chips. Instead of a dice, four corn kernels are usually used, in which one of the sides is marked in some way. Points are considered as:

1. one of the four grains fell empty side up - one point
2. two grains fell out empty side top - two points
3. three grains - three points
4. four grains - four points
5. all grains are marked up - five points

At the beginning of the game all the players' chips are in the "cities". During his turn, the player throws the grain and moves one of his chips to the corresponding number of strips in the direction of the "city" of the opponent.

Two chips of one player can not occupy one strip (except the "city"). But you can put your chip on a strip, on which the opponent's chip stands - to take this chip captive. Further, this column continues to move as one (top) chip and can capture other opponent's chips.

If a column is taken into captivity, then all the lower pieces of the player who performed the capture that were in captivity are released.

When a player brings a column to the "city" on the other end of the board, all the captive chips are removed from the game (fighting), and their own returns to their city and can again enter the game. Accurate throw for entering the "city" of the enemy is not needed.

The winner is the player who captures or hits all the opponent's pieces.

As Dmitry writes: “Despite the seeming simplicity and unusually small board, the pulook is very fascinating. Its tactics are unique, it does not look like the games of other nations: they are not pursuit races, not a war game and not“ transitions ”like Corners, but some tricky "Catch-uvodilka" ".

In my version of the game I made two changes. First, he made the scoring more similar to the dice - the number of points corresponds to the number of grains, dropped marks up. If all four grains fell empty side up, this is considered to be five points.

The second change is associated with the release of their chips from captivity. Dmitri said: "and the bottom chip, the former captive, is released and continues on its own." But in the case of simultaneous release of several chips, a situation arises when they all occupy one strip. And this is contrary to the rule "Two chips of one player can not occupy one strip." In the English-speaking rules, the release of their chips occurs only when the column reaches the "city" on the opposite side of the board - all of their chips are released, and the opponent's chips are beaten. In my version, the released chips immediately move to their city. This does not lead to a violation of other rules and allows you to enter chips back into the game very quickly.

Technical features

In technical terms, the game is probably of no particular interest, since I did not use any special tricks during development. I programmed the Android application using the AndEngine framework. Although it has practically not been developing lately, I had enough of its capabilities.

The only subtle point associated with the animation of the movement of chips. Initially, I animated the movement of each piece. For example, when moving a column of three chips, despite the fact that only the top chip is visible, the program still moved all three. Naturally, this approach led to a rather tangible resource consumption. Therefore, I made two pseudo-columns to demonstrate the movements. During the move, the moving chips first became invisible, the pseudo column set the desired height and the movement animation started. After the animation was completed, the bar became invisible, the chips were placed in a new position and made visible. This option turned out to be a bit more complicated than the previous one, but it was much more economical to spend computing resources.

AI development

The random nature of the drop-down game points does not allow predicting the next moves and using, for example, an alpha-beta algorithm for implementing AI. During his turn, the player can perform (if possible) one of the following actions:

• take the chip out of the "city"
• capture the opponent's chip
• free your chip from captivity
• take out enemy captive chips

For example, in the following situation:

A player can either take another chip from the “city” to the field, or capture a chip from the third strip on the fifth strip with a chip from the third strip or take the chip from the 8th strip and remove the opponent chip from the game.

With the availability of several of the actions presented at the same time, the choice of one or the other will determine the nature of the game. If we assign a certain weight to each of the actions, then in general, the algorithm can be represented as follows:

1. Find all available moves
2. Assign its weight to each turn.
3. Choose the course with the greatest weight.

Using different sets of scales, you can get several options for AI:

public class OpponentAIFirstController extends OpponentAIController { protected static final int WEIGHT_IND_HOME = 0; protected static final int WEIGHT_IND_CAPTURE = 1; protected static final int WEIGHT_IND_RELEASE = 2; protected static final int WEIGHT_IND_CAPTURED_MOVE = 3; protected float movementWeights[]; public OpponentAIFirstController(...) { super(...); initMovementWeights(); } protected void initMovementWeights() { movementWeights = new float[] {1.0f, 1.1f, 1.1f, 1.5f}; } private void calcInitialScores(int pCornsValue) { for(i = mFirstChipIndex; i < mLastChipIndex; i++) { ... int newRow = mFieldController.calcNewRow(curChip, pCornsValue); if (mFieldController.isHomeRow(newRow)) { mMoveScores[j] += 1 + curChip.capturedCount(); mMoveScores[j] *= movementWeights[WEIGHT_IND_HOME]; continue; } ... } } ... } public class OpponentAISecondController extends OpponentAIFirstController { ... @Override protected void initMovementWeights() { movementWeights = new float[] {1.0f, 2.0f, 1.1f, 1.1f}; } } 

In fact, some predictions can be made based on probability theory. For example, if before the situation considered above, the values ​​5, 5, 4, 3, 2, 3 fell out, then with a high degree of probability we can assume that the opponent will fall to the value 1 . In this case, it is highly desirable to save the chip standing on the 8th strip from captivity. Therefore, the third algorithm, which I developed, remembers the dropped values ​​of the grains and attributes the high weight to those moves that save the chips from potential capture.

I did not know in advance which strategy would be the most optimal. On the other hand, call the AI ​​options as usual Beginner , Master , etc. pretty trite. Therefore, I named each of the options in honor of a certain Indian deity. The first algorithm, which first of all tries to save its chips - in honor of Quetzalcoatl - is probably the most famous Indian deity. The second algorithm, seeking to capture the opponent's chips - in honor of the deity of war Camaxtli . The third algorithm, which, according to my assumptions, should be the best, is in honor of the deity of the maize Centeotl . After all, the deity to whom the game is dedicated should play it better than anyone.

In order to introduce some educational element into the game, I added links to relevant articles on Wikipedia in the AI ​​selection dialogue, and a link to Dmitry’s article on Puluk in the About dialog. After a number of games I received the following statistics:

Total

Puluk is really an original and fun game. Now you can “play party after party until exhaustion” at home. With the help of the Internet and Google Play Game Services, you can even fight with the real Maya. Well, farmers can test its effect on corn yields.