I am not a player. And the person is in principle non-gambling. Games, both interactive computer and classic board games, never really hit me. Moreover, I never even wanted to do them. But a year ago, fate brought me a developer to one of the successful Eastern European gaming companies, where now they regularly have to deal with players in games, the games themselves, game designers and game programmers of all kinds. Interest in the theory of game design in such an atmosphere arises by itself, since the region is full of various interesting tasks, and for the last year I have read the various books and articles on the design of games, from strictly theoretical to strictly applied.

Most of the literature on the topic can be attributed to either the first or the second: academic studies traditionally take place in ivory towers, without, as a rule, showing any examples of live games published; applied texts are omitted to the format of recipes and intuitive advice, without giving any tangible model of the work of certain techniques.
')
The book, which caught sight not so long ago, unites in itself both worlds: in it, on the one hand, interesting algorithmic techniques are described in aggregate; the result of the work, the board game “Yavalath” on the attached picture, was published and was quite popular for the abstract game.

So, if you are interested in the theory of game design, machine learning, genetic algorithms, universal players and elegant ideas, then you can read about all this in my short popular science retelling of the essence of the book under the cat.

So how did the book surprise me? In a nutshell: the book is dedicated to Ludi, the automatic generation system for board games by Cameron Browne. The system was developed as part of the Ph.D. work (i.e., the western counterpart of the Kadidatskaya PhD thesis) called Evolutionary Game Design and is able to independently form the rules of the games, play against them, evaluate each one for fun and select the best options. In the end, she even chooses the names for the games on her own!

Well, enough preludes, let's get down to business.

Ludi, evolutionary game design system

The system consists of the following main elements:

• game description language, or Game Description Language;
• universal players (General Game Players);
• strategy module;
• module of criticism;
• synthesis module.

The game description language makes it possible to describe a) finite, b) discrete, c) step-by-step, e) deterministic games with c) complete information. The most common checkers, chess, tic-tac-toe, Go and, in general, a significant proportion of all other classic board games are suitable here.

Universal players interpret the rules formulated in GDL, are able to make a list of legal steps and understand that the game is over.

The strategy module evaluates the current position of each player and assesses possible moves.

The module of criticism evaluates the game itself for various objective and not very parameters, which the author calls “aesthetic”, i.e. evaluating the game in terms of live player interest.

The game synthesis module integrates all of the above subsystems, creating new combinations of rules based on the ratings of the critic module.

In general, the system operation cycle is as follows:

1. GDL describes several dozen (79 in the author’s work) games, universal players read and play them with each other using the strategy module;
   
2. each of the games held receives an evaluation of the criticism module;
   
3. these assessments and rules of games (in the form of a rule tree - akin to the usual abstract syntax tree) are fed to the input of the synthesis module, which, in turn, forms, by crossing, new rules trees - the next generation of games;
   
4. go to claim 1 with a new generation of games.
   

The running time of the algorithm is limited only by the developer’s patience. In the case of the author, obtaining a new game took 2-3 weeks.

That's basically it. Let's look at each of the modules separately.

GDL, game description language

The language is very simple and you can immediately bring analogue "Hello, world!" From the world of game design, the rules of the game "tic-tac-toe":

 (game Tic-Tac-Toe
  (players White Black)
  (board
   (tiling square i-nbors)
   (size 3 3))
  (end
   (All win (in-a-row 3))))

Fans of functional languages ​​immediately recognize Lisp here. Such a lis-like language has at least three advantages: people can read it easily, machines can read it easily and over such a tree (and the Lisp code is the simplest tree) any necessary transformations can be easily carried out. Moreover, the rules of games in such terms are expressed quite succinctly (here there are 19 tokens for 7 lines). The author gave an example of a description of chess, consisting of only 325 tokens on GDL. There are also lower-level languages ​​for such purposes, but they are verbose and less accessible to the modern programmer, as they are usually associated with very exotic logic programming.

Universal player

The player is responsible for reading the rules and their execution: parsing the description of the rules in GDL, responsible for changing the playing sides, the list of available moves, preventing cyclical situations, determining the winner, the user interface (in the case of a live player) and other official things. Simply put, a universal player is a computer game in the usual sense.

What is important here is that the player can both interact with a living person and use ...

Strategy module

... strategy module. There is no breakthrough in artificial intelligence: a minimax algorithm with alpha-beta clipping is used . You should not be afraid of these terrible words: on each move a tree of possible moves is built, in which as you build, branches with a low preliminary estimate are discarded. Specifically, in this system, all subtrees with a depth of more than 1 are discarded, and for each variant, therefore, an estimate is immediately given. It is conditionally possible to say that an inexperienced player is playing, unable to analyze the complex perspective of the game.

Estimates for each of the possible moves are given by the so-called Advisors: a large set of functions (more than fifty), each of which gives a potential move an estimate in the range from 0 to 1. For example, in games like chess you can check how mobile figures are in the checked position (it is believed that the more moves available to the pieces, the greater the player’s tactical advantage).

Different Expert Advisors are important for different games (mobility, for example, does not make sense in “tic-tac-toe”), therefore different Policies are introduced for each game (each set of rules): coefficient vectors for advisors, derived from the rules of the game.

Evaluation of the possible course, respectively, is obtained as follows:

 E (S) = A_1 (S) * P_1 + ... + A_n (S) * P_n,

where S is the state of the game, E is the final score, A_n is the value of the nth Advisor,
P_n is the nth Policy.

Entirely each batch is evaluated using ...

Criticism module

... module criticism. The critique module generates an assessment of each individual game on the basis of two groups of parameters: those based on the evaluation of rules and the following from the games of computer players. In total, criteria evaluating various parameters, as many as 57 pieces, they describe all aspects of the game, from the complexity of the rules to the probability of a “draw”. In essence, these are functions that return values ​​from -1 to 1; and each such function should have weights evaluating their contribution to the resulting estimate.

The final score will be, as in the case of a strategy module, the sum of the values ​​of the functions multiplied by the coefficients.

It makes no sense to describe all the criteria here, of course, and I’ll just give some interesting examples:

• drama criterion - how often in the course of the game the advantage passes from player to player;
• the criterion of balance is the ratio of the number of victories of one side to the other, that is, the game must be balanced;
• duration criterion - the game should not last for hours;
• ambiguity criterion - the result of the game, if possible, should not be determined on the very first moves;
• the criterion of killer moves (killer moves) - the presence of moves that dramatically strengthen the position of one of the players;
• and others.

Manually handing out weights to so many functions is, of course, stupid; and here, obviously, there was a sense to turn to live players.

The author turned to the players of one of the largest online communities of board game lovers for evaluations of 79 initial games. The survey was conducted by pairwise comparisons and the method of cross-entropy . Thus, it turned out a set of ratings of each of the original games.

Having these estimates and criteria functions, it is already possible to obtain the coefficients for each of the criteria by the most trivial of machine learning methods: linear regression.

The result is a fairly accurate function (about 95% accuracy) of the “interesting” score for each of the games, which allows us to proceed to the construction of the mechanics of synthesizing new sets of rules.

Synthesis module

If there is a language for describing rules, a method for evaluating a game and computer players, assembling the system becomes an obvious step. The authors chose the usual genetic algorithms for the synthesis of new games from the old ones.

The general scheme of work here is clear:

1. the first generation of games receive ratings and are sent to a pool of individuals;
2. individuals cross and mutate to produce a new generation of rules;
3. the rules of a new pool of individuals pass the test for validity, during which meaningless combinations of rules are discarded; rules, the calculation of moves in which takes too much time; games, almost no different from the original generation, and so on;
4. go to step 1 with the latest generation of rules.

And so on until there is enough time.

Impressions and remarks

In just a week of work, the algorithm proposed 19 sets of rules, two of which were later published as commercial games. I tried to play them, and really - these are simple, elegant and interesting games. "It's Alive!"

I was surprised at the slenderness of the system: in none of the subsystems did the author of the system use algorithms that were complex or unfamiliar to the general public; everything is clear, even obvious.

And, of course, isn't the opportunity to generate games automatically impressive? In the end, many of today's popular computer and board games are fairly simple in the rules.

Related Links:

• original work of the author
  
• book about Ludi
  
• play on google play
  
• game page on the author's site