Dagaz: Looking for talents

Do with us
do as we do
do better than us!

80's telecast

I must admit, I am not very good at developing bots. I am sure there are people who can do this much better than me. And I would really like such people to join the project . In terms of material incentives, I can offer little. Dagaz was conceived as a free and open-source alternative to Zillions of Games . I myself do not mind its commercial use, just have not yet figured out how to do it.
')
The project will certainly continue to evolve and remain free (at its core). Any person who has contributed to its development, I will consider my friend and co-author. Of course, attribution, for all modules in the development of which these people took part, will be mandatory. In addition, I am ready to provide any feasible technical assistance for the project. For example, I can talk about how to develop game bots.

First of all, it is worth noting that far from all games the issue of developing bots is acute. In the case of puzzles, a bot who can find a solution is more a luxury than a vital necessity. In addition, there are games, for objective reasons, much more difficult for a person than for a computer. This fully applies to various mankalam .


Winning at the computer in such a game is hard. And this is not because you can not play it! I know a man who can . So, he won far from the first attempt and with a very small margin. And this is despite the fact that it uses far from the most successful bot , which is much more modest in other games . Mancala seemed to be specially created for computers! But it's not just them.


Here the bot is even simpler , but the game itself is asymmetric. The task of the “fox” (there is everything that is possible) is much simpler than the task of the “geese” (to hold down the “fox”, depriving it of its course) and a computer plays for the “fox”. If someone will be able to win it, inform. Because I have not succeeded yet. The process itself seems to be understandable, but you constantly lose sight of some “trifle”.


Also, there are games that bots do quite well, although they could play much better. Reversi is a great example. I am sure that it will not be difficult for a person who plays this game well to cope with a bot, but for me, for example, this is an impossible task. Alas, my bots cannot cope with most of the most popular games at all. Here is a list of those for which this problem is most relevant:

1. Checkers - first of all " Russian ", " International " and " Frisian ". Bots with them, in principle, work, but they play at the level of a very weak beginner. Also very interesting are the " Turkish checkers ", here the bots play even worse. The closest attention should be paid to the “ Pillars ” and “ Weasel ”. These are really challenging and very interesting games!
2. Chess and everything like them. In these games, all my bots are playing absolutely disgusting. The same applies to the " Chinese " and, to an even greater extent, the " Japanese " chess. Here, I'm not talking about the " big games ", the development of bots for which is quite specific and in which few people play (I know such people). First of all, the most popular options are interesting for me. Shashmatas are also a priority. They generally should be put in a separate category, since they took the most difficult "of both worlds." First of all, I am interested in " Belarusian chess " and " Altai tent ". Fans of very hardcore exotics can try their hand at Platform Chess .
3. Staged games, above all " Renju " and " Go ". This is a very fresh topic, in the sense that I have just begun them. In general, games with resetting pieces to the board (on a par with mancala) are the theme of the current iteration of the project, so there will be more such games soon. And now it is clear that some of them (Guo for example) require a special approach when developing AI. But there are even more confused games .
4. The most diverse games fall into this category. Here are the children’s “ Jungle ” and the French “ Agon ” of the 18th century. Games are big and smaller . The games are completely insane . One thing unites them all. I have no idea how to approach the development of their AI. And, of course, I will be just happy if someone helps bring to mind the AI ​​for my " Spock ".

So how can you write your bot? As a very first step, it is worth downloading the contents of this or this repository to your computer (without which to write, and even less to debug, which will be hard). Although the second of the listed repositories is, in fact, a release, it does not currently use any obfuscation or minification. All applications are very simple. From a html-file several js-scripts are loaded sequentially.


You may notice that from among third-party libraries, I use only very convenient Underscore for me (I do not insist on using it). All bot scripts contain "-ai" in their name. It is they who are interesting to us now. But before you move on, you should tell a little about:


Thus, we have a design that does not change during the game, and a set of game states encoding the arrangement of figures at the time of the start of each turn, but a legitimate question arises:


The whole game is, in essence, a repeating cycle, consisting of the generation of permissible moves and their subsequent application to the game state. The iterations are repeated (with the alternation of moves of the players, given by the rules of the game) until one of the following events occurs.

1. The list of moves generated by one of the players turns out to be empty (depending on the game, this can be regarded as a defeat, a draw or even a player's victory)
2. The Dagaz.Model.checkGoals function returns a non-null value.

The second point allows you to program the correct completion for almost any game.


The checkGoals function is an integral part of the game design. At the time of the development of the bot, it is already defined and it is quite enough just to be able to call it, to correctly determine the positions that complete the game. The function can be called for any game state and takes three arguments: the design of the game, the current state of the game and the player's identifier from the point of view of which the position is evaluated. The result of the call is interpreted as follows:

1 - player win
-1 - player loss
0 - draw
null - not a terminal position (the game can be continued)

Another important thing that you need to know before you start developing any bots is an evaluation function. I have already written about it in some detail before, but I repeat once again. The objective of the evaluation function is the numerical evaluation of the position, from the point of view of one of the players (the greater the value, the better the position).


Usually (but not necessarily) the assessment of the position, from the point of view of one of the players, coincides with the assessment of the same position by his opponent, taken with the opposite sign. Without compliance with this condition will not work, for example, minimax algorithms . There are games (for example, those in which more than two players participate) in which it is not possible to comply with this condition. Also, there are games in which the use of the minimax is difficult, for other reasons (for example, a complex sequence of passing a turn).


In these cases, heuristics come to the fore (when using a minimax, they are also very useful, since they allow you to pre-sort possible moves by their potential "strength"). Unlike the evaluation function, heuristics evaluate the move itself, and not the position on the board after it has been completed. Heuristics can be both very complex and as simple as possible.


Not for all games to build a qualitative evaluation function is easy. In particularly difficult cases, “little tricks” are good at helping. About the "cover", very useful in chess-type games, I wrote earlier . Another possibility is to store auxiliary values ​​in the attributes of the shapes.


In Rendzu , the most important aspect is the presence of “triples” and “fours” on the board, oriented in four different directions. This information is used not only by AI, but also to identify situations of various “fouls” (long rows and “forks”) prohibited for the first player, as well as to determine the end of the game (5 stones “in a row”). Meanwhile, the search for such configurations on the board is quite a resource-intensive task.

On the other hand, if we already store counters with row lengths, for all stones previously placed on the board, the task of updating these counters, when adding a new stone, becomes trivial . Slightly more complicated (but quite realizable ) is the calculation of the number of " dame " for groups of stones in the games of the " Go " family. In any case, it is much easier to store these values ​​than to calculate again and again, whenever they are needed. Of course, these little things, by themselves, will not turn a bot into AlphaGo , but can make its development much more comfortable.

So we come to talk about bots. The task of the bot, in Dagaz is the selection of the best (in a sense) move from the list of all allowable moves generated by the game state. Here is the simplest bot:


Already on this listing you can understand the following:

1. Any bot must “integrate” into the Dagaz.AI.findBot call chain (so that the controller can find it. The bot is searched by its type. There are three main types: “opening” , “common” and “random” . Found bots also lining up “in a chain.” This is done so that the best move first looks for a bot destined for debuts ( sgf-ai , for example), followed by the main bot ( maxmin-ai , in most cases), and if it is not found (found it all moves too bad), the game turned on random-ai , just to go at least as a something. For the decision of the head Omoko uses a special type of bot "solver".
2. For each player with whom the bot works, a “context” is created (this is done so that one bot can serve several different players simultaneously). Inside the context, you can store any data shared between successive calls to the bot (for example, a tree of game states). Before requesting the “best” move from the bot, the controller sends the bot the current state of the game (by calling the setContext method).
3. The bot's move is requested by the getMove method. The method returns a hash containing the move field (the desired move). Also, if the bot has completed the search for a move, it must pass true to the done field of the returned hash. Currently, this functionality is not used, but it is understood that the controller may request the bot to move several times in a row. If the bot did not manage to find the best move in the allotted time, it can return the best move from those already reviewed, but not set the done field for the controller to continue polling.

Let's look at a slightly more complicated bot:


This is not so much "artificial intelligence" as "artificial instincts." Just choosing the course with the maximum heuristics, without any use of the evaluation function. This bot is fast and transparent in debugging, but this is where its merits end. The depth of his intellect, you can appreciate the current level of the game " Renju ", " Wars of viruses " and especially " Atari Go ". Ideally, I would like to achieve normal operation of something like this (my implementation of a minimax with alpha-beta clipping is, alas, not working yet).

Speaking of debugging bots, it is worth noting that this is a painstaking, tedious thing and does not have much fun. Any tool to facilitate this process is definitely worth using. First of all it concerns the common-setup module. It is enough to add it to the list of loaded scripts and in the log (how to enable the log in the browser, I think it is not necessary to explain), after each turn, records like this will start to appear:

 Setup: ?setup=+19;0:1=4;+2;0:1=4;+5;0:2=3;+7;0:1=2;0:2=5;+7;0:2=5;+29; 

By adding this entry to the address bar of the browser (like this ), you can recreate the corresponding position immediately, without tedious playing of the previous moves.And with some skill, you can make yourself ready to read this notation and even edit it directly in the address bar.

Another useful feature is provided by the controller. If you replace app-v2 with app-auto in the htm-file , you can make bots fight each other without being distracted by clicking on the board with the mouse. Remember the weird numeric bots in heuristic-ai.js ?

 ... Dagaz.AI.findBot = function(type, params, parent) { if ((type == "heuristic") || (type == "common") || (type == "1") || (type == "2")) { return new Ai(params, parent); } else { return findBot(type, params, parent); } } ... 

A bot with type " 1 " will be loaded for the first player, and with type " 2 " for the second. This is certainly not an autoplay from the Axiom , but also a very useful thing. In addition, unlike autoplay , app-auto is not limited to only two players .

The debug-ai module is another useful tool worth adopting. Sometimes, when debugging game logic, it is not enough just to reproduce the position. In such cases, it is sometimes necessary that the bot play the moves on a given list and debug-ai knows how to do it. It was with his help that I debugged the Apocalypse .

Well, in general, and all wisdom. As I said, the tedious thing, but not supernatural. And I will be glad if anyone joins me in this matter. By the way, literally two days ago, the first letter arrived at the project mail. Garrick Wells great help to me with debuts for Micro Shogi . Along the way, I discovered and fixed a serious bug that affected this and several other games. This is exactly the form of cooperation I seek.