👨🏻‍🎓 🕡 😓 Dagaz: The Sum of Technology 🦀 🤮 🤛🏾

So, technologies are of interest to me, so to speak, out of necessity: because every civilization includes both that which society aspired to and that which no one intended.

Sometimes, and quite often, the path of technology was opened by chance: once they searched for a philosopher's stone, but found porcelain.

Stanislav Lem.

From the very beginning of the project , it was clear that a high-quality AI is vital for me! It’s boring to play with yourself, but the module for playing on the network - it is not known when it will be. I tried to write bots myself, but they all worked either badly or badly and slowly. In the end, I was tired of doing this amateur activity and found a chess bot, the quality of the game which completely suited me. But there was a problem. I needed not only Chess. This article is devoted to how I struggled with this.

If you look at the source code of Garbochess-JS (by the way, on the KDPV photo of Greta Garbo , the famous actress, after whom the project got its name), you can notice that the beauty of the source code is the last of what interested its author. The text contains global variables and other cute little things, conscientiously ported from the original draft .

For me, the biggest problem was that the algorithm itself is in no way separated from exclusively chess specifics, such as position estimation, heuristics, etc. For this reason alone, the code had to be completely rewritten. It was a lot of work (and it is still ongoing), but today there are already some successes that I can share.

A little bit about performance

. , , , . , , . .

, (, ). , «», url, , . .

. . .

You may notice that although this game (which was invented by Robert Price in 2001) is similar to Chess , the original Garbochess could hardly cope with it. This is a good illustration of the task that stood before me. I should separate algorithm for finding the best course, with all of that is specific to particular games. In order to be able to use it in different games, of course. Why else?

Of course, I started with something much less complicated (but already at this stage the first difficulties arose). Pawns here move according to the usual rules (but without jumping the first move and taking on the aisle ). Transforming any shape completes the game. The inability to move means defeat.

Difficulties, of course, arose due to the fact that Garbochess is aimed exclusively at chess. When the king is under the mat or stalemate , the process of finding a move ends naturally. It remains only to check under the Shah whether the king, to determine the outcome of the game is complete. In the "Pawn War" there is another conclusion related to the transformation of one of the pieces.

The bot, in these cases, cheerfully continued to search through the options, despite the fact that the game had already ended. I quite easily defeated this by banning the further generation of moves after reaching the goal of the game. Another difference was that the lack of opportunity to move in this game is always a defeat. There are simply no kings in the game, there is no need to check whether they are under the check. We managed to cope with it even easier. Next in line were large forms.

It is worth making a small theoretical digression

, Garbochess. "--". , — , , . , , .

, , , , , , . , . , , .

, ( , ) , . - , - ! , Garbochess . - !

At this point, performance problems started. The fact is that you can’t just go down to a certain level and evaluate the position there! It may happen, for example, that we end the search by taking the queen with the pawn, not paying attention to the fact that the queen can be taken with the next move, with far from the best outcome for us. Before evaluating something, it is necessary to “lose” to the end all forced moves, which include any captures, as well as any moves in situations where the king is under the check.

That was the problem. The fact is that all checks for the allotted time were performed in that part of the code that was about "alpha-beta clipping", and not that of replay. There are games in which such an after-game is capable of taking monstrously branched forms. There the program execution was dying. At the same time, it was impossible to simply add a time check to “play out”, because as a result, everything would end there, possibly before reaching really good moves. I had to somehow limit this matter (with a loss in the quality of the game, of course).

Another reason for the freezes was that my model was very slow

, , , Garbochess. , , ! , JavaScript , , .

, -

Dagaz.Model.BuildDesign = function(design) {
    design.addDirection("w");  // 0
    design.addDirection("e");  // 1
    design.addDirection("s");  // 2
    design.addDirection("ne"); // 3
    design.addDirection("n");  // 4
    design.addDirection("se"); // 5
    design.addDirection("sw"); // 6
    design.addDirection("nw"); // 7

    design.addPlayer("White", [1, 0, 4, 6, 2, 7, 3, 5]);
    design.addPlayer("Black", [0, 1, 4, 5, 2, 3, 7, 6]);

    design.addPosition("a8", [0, 1, 8, 0, 0, 9, 0, 0]);
    ...
    design.addPosition("h1", [-1, 0, 0, 0, -8, 0, 0, -9]);
    ...
    design.addCommand(0, ZRF.FUNCTION,	24);	// from
    design.addCommand(0, ZRF.PARAM,	0);	// $1
    design.addCommand(0, ZRF.FUNCTION,	22);	// navigate
    design.addCommand(0, ZRF.FUNCTION,	1);	// empty?
    design.addCommand(0, ZRF.FUNCTION,	20);	// verify
    design.addCommand(0, ZRF.IN_ZONE,	0);	// last-rank
    design.addCommand(0, ZRF.FUNCTION,	0);	// not
    design.addCommand(0, ZRF.IF,	4);
    design.addCommand(0, ZRF.PROMOTE,	4);	// Queen
    design.addCommand(0, ZRF.FUNCTION,	25);	// to
    design.addCommand(0, ZRF.JUMP,	2);
    design.addCommand(0, ZRF.FUNCTION,	25);	// to
    design.addCommand(0, ZRF.FUNCTION,	28);	// end

    design.addCommand(1, ZRF.FUNCTION,	24);	// from
    design.addCommand(1, ZRF.PARAM,	0);	// $1
    design.addCommand(1, ZRF.FUNCTION,	22);	// navigate
    design.addCommand(1, ZRF.FUNCTION,	1);	// empty?
    design.addCommand(1, ZRF.FUNCTION,	20);	// verify
    design.addCommand(1, ZRF.IN_ZONE,	1);	// third-rank
    design.addCommand(1, ZRF.FUNCTION,	20);	// verify
    design.addCommand(1, ZRF.PARAM,	1);	// $2
    design.addCommand(1, ZRF.FUNCTION,	22);	// navigate
    design.addCommand(1, ZRF.FUNCTION,	1);	// empty?
    design.addCommand(1, ZRF.FUNCTION,	20);	// verify
    design.addCommand(1, ZRF.FUNCTION,	25);	// to
    design.addCommand(1, ZRF.FUNCTION,	28);	// end
    ...
    design.addPiece("Pawn", 0, 800);
    design.addMove(0, 0, [4], 1);
    design.addMove(0, 1, [4, 4], 1);
    design.addMove(0, 2, [7], 1);
    design.addMove(0, 2, [3], 1);
    design.addMove(0, 3, [1, 4, 4], 1);
    design.addMove(0, 3, [0, 4, 4], 1);
    ...
    design.setup("White", "Pawn", 48);
    ...
    design.setup("Black", "King", 4);
}

var step = function(ctx, params) {
    if (ctx.go(params, 0) && !ctx.isFriend()) {
        ctx.end();
    }
}

var pawnShift = function(ctx, params) {
    if (ctx.go(params, 0) && ctx.isEmpty()) {
        if (ctx.inZone(0)) {
            ctx.promote(4);
        }    
        ctx.end();
    }
}

var pawnLeap = function(ctx, params) {
    if (ctx.go(params, 0) && ctx.isEnemy()) {
        if (ctx.inZone(0)) {
            ctx.promote(4);
        }    
        ctx.end();
    }
}

var pawnJump = function(ctx, params) {
    if (ctx.go(params, 0) && 
        ctx.isEmpty() && 
        ctx.inZone(1) && 
        ctx.go(params, 0) && 
        ctx.isEmpty()) {
        ctx.end();
    }
}

var enPassant = function(ctx, params) {
    if (ctx.go(params, 0) &&
        ctx.isEnemy() &&
        ctx.isPiece(0)) {
        ctx.capture();
        if (ctx.go(params, 1)) {
            ctx.put();
            if (ctx.go(params, 1) &&
                ctx.isLastFrom()) {
                ctx.end();
            }
        }
    }
}

var jump = function(ctx, params) {
    if (ctx.go(params, 0) && 
        ctx.go(params, 1) && 
       !ctx.isFriend()) {
        ctx.end();
    }
}

var slide = function(ctx, params) {
    while (ctx.go(params, 0)) {
        if (ctx.isFriend()) break;
        ctx.end();
        if (!ctx.isEmpty()) break;
    }
}

var O_O = function(ctx, params) {
    if (ctx.go(params, 0) &&
        ctx.isEmpty() &&
        ctx.go(params, 0) &&
        ctx.isEmpty()) {
        ctx.put();
        if (ctx.go(params, 0) &&
            ctx.isFriend() &&
            ctx.isPiece(1)) {
            ctx.take();
            if (ctx.go(params, 1) &&
                ctx.go(params, 1)) {
                ctx.end();
            }
        }
    }
}

var O_O_O = function(ctx, params) {
    if (ctx.go(params, 0) &&
        ctx.isEmpty() &&
        ctx.go(params, 0) &&
        ctx.isEmpty()) {
        ctx.put();
        if (ctx.go(params, 0) &&
            ctx.isEmpty() &&
            ctx.go(params, 0) &&
            ctx.isFriend() &&
            ctx.isPiece(1)) {
            ctx.take();
            if (ctx.go(params, 1) &&
                ctx.go(params, 1) &&
                ctx.go(params, 1)) {
                ctx.end();
            }
        }
    }
}

games.model.BuildDesign = function(design) {
    design.addDirection("w");  // 0
    design.addDirection("e");  // 1
    design.addDirection("s");  // 2
    design.addDirection("ne"); // 3
    design.addDirection("n");  // 4
    design.addDirection("se"); // 5
    design.addDirection("sw"); // 6
    design.addDirection("nw"); // 7

    design.addPlayer("White", [1, 0, 4, 6, 2, 7, 3, 5]);
    design.addPlayer("Black", [0, 1, 4, 5, 2, 3, 7, 6]);

    design.addPosition("a8", [0, 1, 8, 0, 0, 9, 0, 0]);
    ...
    design.addPosition("h1", [-1, 0, 0, 0, -8, 0, 0, -9]);
    ...
    design.addPiece("Pawn", 0, 2);
    design.addMove(0, pawnShift, [4], 0);
    design.addMove(0, pawnJump, [4], 0);
    design.addMove(0, pawnLeap, [7], 0);
    design.addMove(0, pawnLeap, [3], 0);
    design.addMove(0, enPassant, [1, 4], 0);
    design.addMove(0, enPassant, [0, 4], 0);
    ...
    design.setup("White", "Pawn", ["a2", "b2", "c2", "d2", "e2", "f2", "g2", "h2"]);
    design.setup("White", "Rook", ["a1", "h1"]);
    design.setup("White", "Knight", ["b1", "g1"]);
    design.setup("White", "Bishop", ["c1", "f1"]);
    design.setup("White", "Queen", ["d1"]);
    design.setup("White", "King", ["e1"]);
    design.setup("Black", "Pawn", ["a7", "b7", "c7", "d7", "e7", "f7", "g7", "h7"]);
    design.setup("Black", "Rook", ["a8", "h8"]);
    design.setup("Black", "Knight", ["b8", "g8"]);
    design.setup("Black", "Bishop", ["c8", "f8"]);
    design.setup("Black", "Queen", ["d8"]);
    design.setup("Black", "King", ["e8"]);
}

, ! , , . , , . , , . !

, . 128 . , , . , . , (, , ).

It is worth noting that the issue of performance is not always an acute issue. There are games that are objectively difficult for people to play. The use of algorithms in such games that do not miss a single opportunity leads to completely killer results:

We take all the balls in one of the two holes on our side and sow one at a time in the following holes, counterclockwise. Who first ran out of all the balls - he lost. The irony is that if the first player does everything right - he (in most cases) wins. In terms of computing, this is a very simple game, but it’s difficult for a person to play it. Less extreme examples can be given:

And this is even more interesting! However, in this game, a person already quite easily wins. If he knows the rules and doesn't yawn, of course. In general, in the chess world, there are quite a few different mini-games. And with them the current implementation of the bot is already quite coping.

The new bot also has disadvantages, of course

, , . ( ) . , . , . . - .

, ! -- , . , , . , .

, . , , (, ). , , ( — ). «» " " ( , ). , .

But, in general, I am quite pleased with the (intermediate) results. There is still work to do. So far, I have connected far from all Garbochess optimizations. And the question of position evaluation is a topic for a separate big conversation. All these are the fruits of the long collective work of many, many smart people. I am very grateful to all of them for this work. I myself would not have thought of much of all this.

Dagaz: The Sum of Technology

More articles: