A screenshot of that same flash game still welcomes you to toox.com/jeux/jeux-de-cartes/coinche
Statement of the problem and its relevance
Quosh, Belote and Tarot are national French games. According to the rules, this is approximately like playing preference in a closed game, and a pair is played for a pair, so by how many bribes and on what trump card your partner proposes to announce the game during bargaining, you can roughly understand what kind of cards he has. The game is long and the existence of an AI capable of somehow bringing the game to the end in it is simply vital, because one of the players can simply leave the table deciding that he is hopelessly losing, and the winner naturally wants to push it to the final score on the scoreboard. In this case, AI will finish the game for the lost player. But since we have AI why not allow us to start the game by annoying AI-shki on empty spaces. And so we launched these great games to the masses and quickly found out that basically there are two options for how the French like to play.Approximately half of all tables are waiting to be filled with live people until victorious, and half comes to lower down and starts the game against three AI, as in the screenshot above.
In principle, since the game is closed, people are ready to forgive robots for minor miscalculations and alternative giftedness. Mainly because the robot's cards cannot be seen. "Under the player with simak", "under the vistuza with the ace" and similar simple rules that I shook out from our French customer allowed us to make the minimum acceptable thrower. It was nafigched in a week right on the ifs. On the other hand, the game is played "two for two", points are counted for a pair, and quite naturally the player does not want his stupid partner to enter "from the second king", that is, having a king in his hands and some other small card to this suit, instead of letting the opponent play an ace, letting it pass with a small card and taking the next move in this suit with his king. (Actually in these games the second oldest card is 10,but hereinafter I will speak in Russian terms). But if the ace for some reason left the game, and you have a Queen and something else small, then it's almost like the second king. Especially if you pre-order the trump cards. And you, for example, are not playing Belote, where 32 cards are used, but Tarot, in which the game is played with a deck of 78 cards (the same one that some people guess by). And there, in some cases, not even the third queen, but the fourth jack, can take the bribe. In general, all this gives rise to such a number of edge cases that a stupid dummy on ifs becomes somehow completely unacceptably complex. And at this point I said: “Bah! I've read a lotfor example, you do not play Belote, where 32 cards are used, but Tarot, in which the game is played with a deck of 78 cards (the same one that some people guess by). And there, in some cases, not even the third queen, but the fourth jack, can take the bribe. In general, all this gives rise to such a number of edge cases that a stupid dummy on ifs becomes somehow completely unacceptably complex. And at this point I said: “Bah! I've read a lotfor example, you do not play Belote, where 32 cards are used, but Tarot, in which the game is played with a deck of 78 cards (the same one that some people guess by). And there, in some cases, not even the third queen, but the fourth jack, can take the bribe. In general, all this gives rise to such a number of edge cases that a stupid dummy on ifs becomes somehow completely unacceptably complex. And at this point I said: “Bah! I've read a lotBriefly and impressed! " Then I ran away from the office for a few days, sat down with a laptop in a cafe and a few days later spawned something.
Key ideas
What is the Prolog based on declaratively? On facts, for example:
('', '').
('', '').and on terms, or rules, for example, if A is mother B, then A is a girl:
() :- (, ).Of course, I understand that in our time everything is not so simple, and in general it is even a little indecent to say this, but in the days when people believed in formal logic, there was nothing reprehensible in such examples. Let's say for tolerance:
(A, B) :- (A, B).
(, ) :- (, ), (, ).And then you ask me like this:
?- (X, '')And the terribly logical Prologue answers you:
X = ''
X = ''The idea was for the user not to warm his head with the order in which and in what quantity the prologue system would apply the rules to the facts to arrive at an answer. But, of course, it's not that simple. The prologue is overgrown with crutches, functional additions, cutters of various branches of reasoning and the like, and still regularly runs away into infinite recursion.
In the book of that very inspiring Bratko, a whole chapter was devoted to how the prologue machine is realized inside. In short, it goes through the tree of all the rules in depth, trying to apply each of the rules in turn to the set of all facts and variables known to it to get a new state, and if the rule cannot be applied, it rolls back to the previous step and tries to try another option.
Moreover, if you manage to scrape together something useful, the machine takes the list of rules, and at the next step, it starts looking for rules to apply from the very beginning of the list. Moreover, if a variable occurs in the rules, the machine remembers which states of these variables, taking into account the rules already applied, can be. This is called fleshing out. If it can find an instantiation of the variables that makes the question true, it prints that instantiation. Then she can go looking for the next concretization, and so on. In the above artificial example, the system found two concretizations that satisfy the conditions.
I would like to somehow similarly formulate the rules of the game, but of course not literally. Having some experience in debugging programs in Prolog, I was not at all eager to face this debugging and these overhead costs on my product.
First, all this should work not on a bunch of scattered facts, but on the game state tree - a model and apply the results of its work to the same tree as well. Secondly, I want to write the rules so that a specific value, a variable, and an arithmetic expression could be in the same position, and the system should handle this appropriately without asking the programmer additional questions and without requiring additional syntax. Third, of course, it is vitally important to abandon infinite recursion, but some repetition of the application of the rules still needs to be left. Fourthly, the system of rules should be written in some very convenient human-readable format, so that at one glance it is clear what the author wanted to say. And finally, fifthly,all this needs to be tied to some convenient logging and debugging tool so that it is easy to follow the reasoning of this system and understand why certain rules do not work contrary to expectations.
This, of course, is not a universal first-order predicate logic solver, but simply a convenient declarative system of game rules. Which in a practical sense is also very good. For this I came up with the name Logrus much later on one of the following projects. I will describe the final version at once, bypassing all the intermediate stages of the engine development.
The resulting syntax of the Logrus library
There will be a lot of syntax.
1) At runtime, the decision tree is stored in the form of some classes, but the first thing I attached to it, as soon as it worked, was Import and Export in JSON. It turned out that it is also convenient because if your data structure has not changed much, you can update the rules from the file without recompilation. Writing in the form of JSON turned out to be so convenient that on one of the following projects, when programmers were in a hurry, sometimes instead of writing a normal command, they simply did
state.AplayJSON("...");and in it the required action was inserted as a JSON string. This, of course, did not have a very good effect on performance, but if not regularly and only in response to user clicks, then it’s not scary ... All the rest I will illustrate immediately with JSON. I reproduce JSONs approximately from memory, because it was a hell of a long time. Strictly speaking, JSON does not guarantee the order of the nodes in the object, but most libraries still respect it, and here and below the order of the nodes is actively used.
2) The Rule became the main structural unit of the engine. A rule consists of a condition and an action. Usually the rules came in arrays and were applied one by one each one time:
[{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]3) Each rule contains a condition - this is a tree template, possibly containing variables. The system will look to see if the state tree matches the template for any values of the variables. And if it finds such a concretization, it will trigger an action. For instance:
{"condition":{
"player":{
"$X":{"gold" : "<20", "name":"$NAME"}
}},
"action":{}}Such a construction will mean that in order to trigger an action in the tree, there must be a "player" node at the top level in which one or more child nodes, each of which has "gold" fields with a value less than 20 and "name". If such a condition is met, then the action will be called, and as input it will be passed in the X variable - the node's key, and in the NAME variable the player's name. If there are several suitable nodes and, accordingly, there are several possible instantiations, then the action will be called several times with each of the found instantiations at the input.
4) Initially, everything was a little less flexible there, but then Valyard, whom many know from numerous talks at conferences about Unity, screwed us a parser that parses arithmetic expressions into a fast decision tree and flexibility finally blossomed in a violent color.
5) C $ variable names begin. They can appear as a key, such as $ X, and then several instantiations will be selected, as a sheet value, such as $ NAME, can be inserted into arithmetic expressions: for example: {"gold": "<$ X * 10" } And then it can be used to check the conditions, only those players who have more gold than their ordinal number multiplied by 10 will pass the check, and finally They can be directly calculated in some expression, for example: {"gold": "$ X = 3 + $ this "} where $ this is the value of the current point at which the calculation was called. Passing this node concretizes the value of the variable $ X as 3 + the amount of gold the player has. Of the possibilitiesthat came to mind was not implemented, there was only one - the variable cannot first appear on the right side of an arithmetic expression, this will be an error, by the time it is used as an argument it must already be concretized in one of several other ways
6) A variable in an expression can occur as many times as you like, while the first mention of it specifies it, and the next ones will be a test for equality. For example, such a construction will take the first player, check him for money, then look for another player for whom the first would be the target. If it does not find it, it will roll back to the point of concretization X will select the next player, check for money, and so on until it goes through all the possible options X and Y. By swapping the lines, the programmer will change the order of checks, but not the final result:
{ "player":{
"$X":{"gold":">20"},
"$Y":{"target":"$X"}
}}7) The action is also a tree template that can contain variables and arithmetic expressions, and the game state tree will be changed to match it. For example, this template would assign player X an opponent in the form of player Y, but if for some reason player Y did not exist, it would be created. And the "superfluous" player will be removed altogether. At the time of creating the game from the screenshot, the delete sign was null, but then I replaced it with a reserved word, in case someone needs to insert a blank value by key. In general, the principle, I think, is clear, and the meaning of the actions performed with the game is basically the same.
{
"condition":{
"player":{
"$X":{"gold":">20"},
"$Y":{"target":"$X"}}},
"action":{
"$X":{"target":"$Y"},
"superfluous":"@remove"}
}
8) An action can also be not a tree template, but an array of rules. Each of them will be checked not from scratch, but with the initial instantiation with which the action was called. That is, there can be a whole group of rules, and they will all use the X variable.
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":[
{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]
}9) The child rule can be applied not from the root of the state tree, but from some point reached during the application of the action. In this case, all conditions and all actions will use this point as the root. It looks like this:
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":{
"$X":{"@rules":[
{"condition":{}, "action":{}},
{"condition":{}, "action":{}}]}
}10) The repetition of the rule could be specified as another node, this achieved, if necessary, recursion of limited depth. But in practice, such a decision was usually not necessary. It can also be used to repeat a bunch of rules as needed by placing it in an action:
{
"condition":{},
"action":{},
"repeat":5
}11) The rule tree could be loaded from several JSON files, their tree structure was simply superimposed on one another. It was convenient to break the rules into separate meaningful blocks. Probably some Include would also be useful, now I don't remember how it was arranged with us.
12) Logging! Any rule could have a "@log": true node, which led to the fact that this rule began to shit in great detail in the log describing the solution process. What concretizations we try, what branches of reasoning are suppressed and why. Logging was hierarchical, that is, a nested rule could be "@log": false and everything that happens in it and below will not be logged. Ideally, I would like this node to be able to be left anywhere in the conditions tree in order to look only at what is happening in one level of the template, but I don't seem to have completed such an extension. Perhaps debugging went well without it, so it was postponed until "someday."
13) Typing. The toy was so old that some of today's programmers weren't even born. It was written in ActionScript2, which had dynamic typing and inheritance through prototypes available right at runtime. Of the modern languages that are heard, only Python works this way. However, tying to this idea is not particularly difficult. I would do this using the ':' key symbol like this: "$ X: int" but it can be tricky if the first occurrence of the variable did not have any of the specified type. And besides, there can be confusion with the ternary operator.
As they say, it was smooth on paper, but practical use required a number of different crutches. Here are the ones that I remember:
14) One and the same node could be checked not by one, but by several conditions. For example, such a condition first checked that there was more than 20 money, and then specified the variable in which this amount of money was represented. The service symbol '@' if it is not at the beginning of the line meant re-entry into the node, the re-entry identifier going further was not useful in any way. Perhaps a service symbol was used and some other, but nothing, in my opinion, prevents you from using this one:
{
"player":{
"$X":{"gold":"<20", "gold@cnt":"$COUNT"}
}
}15) It took arithmetic operations that could be performed without using any node at all. According to the tradition of the prologue, they were designated '_' and there can be many of them:
{
"_":"$SUM=$A+$B",
"_@check":"@SUM <20"
}16) Since there is a verification pass up the tree, it took a descent downward, done through the "@parent" keyword. This, of course, did not add to readability, but it was impossible to do without it. Here, of course, some analogue of the path function directly suggests itself, which would redirect to the specified place in the tree, but I don't remember if I managed to implement it in the end or not:
{
"condition":{
"player":{
"$X":{}, "$Y":{"target":"$X"}}},
"action":{
"$X":{"rules":[
{
"condition":{
"@parent":{"@parent":{"…":"…"}}
}
]},
}
}17) The action now has the ability to directly pull some class method. This is such a kick in the throat of readability, and I would prefer some analogue of #include, but as it is, you can't throw out the words from the song. I wonder if I can do without this in practice if I reanimate the library now in C #?
18) The rule now has an additional setting to repeat the action not for all found concretions, but only for the first one. I don't remember now what it was called, but for some reason this crutch was useful for some rules.
Results of use
As soon as the library began to be actively used, all AI-shki were quickly transferred to it, and this made it possible to have twice as smart AI while spending three times less programming resources. The fact that the intermediate data of the AI-scale was stored directly in the tree helped a lot. In particular, the rules themselves wrote information about the cards of each suit that had left the game right in the game state tree.
Already in the next project, checking the rules of the game and making possible moves from each position moved to the same engine. And in general, not only for rapid prototyping, but also for games in which there are simply many rules, this would be a very useful thing. In the end, downloadable JSONs with logic can replace half of what programmers do with code, and also win in flexibility.
Of course, in terms of execution speed, all this was noticeably inferior to the mess of ifs, especially in the implementation on AS2 with its prototypes and dynamic objects, but not so much that it could not be rolled out into production.
The next step was to transfer the rules check and determine the action for the AI to the client computer. For the players to check each other. And I even came up with such an algorithm to do this in spite of the fact that the values of the enemy cards are not known to us, but that was a completely different story.
Many years passed, I changed jobs a dozen times, and every time I updated my resume, I went to toox.com and was surprised to find my job still in service. I even stopped by to play another game. And once in Belot I accidentally came across a set of cards giving the maximum possible number of points. The probability of getting such a set is one in three million.
Someday I will gather my will in a handful and make a modern remake of Logrus for C # and Unity3d, for example, for the hexagonal strategist I dream of. But it will not be today, today I will go to bed. The duty of spreading ideas that are worth spreading has been successfully fulfilled.
In conclusion, a couple of anecdotes
We were located in the Novosibirsk Academgorodok. We rented an office at the institute. And the customer is French, completely unfamiliar with the local customs. And so, on the third or fourth month of joint work, he comes to visit us, to get acquainted. I checked in on the weekend at the local hotel "Zolotaya Dolina" and on Monday, he says to the manager, let's meet me in a taxi at ten in the morning, we'll go with the programmers to get acquainted. And take Vovchik and come at 10. In general, they drive up to the institute, knock on the door, and from the other side comes the grandmother of the watchman and looks at them completely without understanding from behind the locked door. At such an early date, there were no scientists or programmers renting offices in the building. They literally woke her up.
And here is another case. Somehow our Sebastian Pereira calls to the manager and says that they miraculously managed to break into the TV and soon we will be shown on TV with our website. After about 8 hours. So what do you do there to make it work more reliably ... On the clock on January 2 ... It doesn't matter what time ... And so Vovchik takes a taxi, starts collecting programmers in dorms and apartments, completely in a state of smut, and take them to the office. That day I saw our system administrator for the first time in my life. Up to this point, he did everything exclusively remotely. And so we twisted each one who could. In particular, I broke this whole system by putting a bunch of ifs in its place back and here we are, looking at the attendance graph and suddenly we see how it starts to go up. Somewhere at the x15 mark, the server crashed. But the admin said that everything is fine, fell gently,now he will rise. The server crashed three more times that day.