New project: very general engine for variants

[hgm]

I already made some progress along this line. I took the model TCP server from the MicroSoft website, (which just echoed the received messages), and changed it into a simple HTTP server capable of serving HTML, JavaScript and image files from the directory it runs in. I put a HTML page there that displays the GUI output, and links to a js file with the GUI script, both for serving by this simple HTTP server. I also included a HTML start page, which explains how to use things, and contains a link to open the GUI page on localhost. For now all graphics used by the GUI refer to the chessvariants.com website.

This all works. So all what is left to do now is make this localhost HTTP server run an engine (in a separate thread, or even as a separate process connected by pipes), and provide requests to control that and serve its accumulated output. That would solve the GUI issue.

[hgm]

In the mean time I am still thinking about the engine design. With just leapers and sliders as you have in orthodox Chess things would be simple enough. Move generation would consist of associating cells in a trajectory for a piece with board squares, by putting the cells in a doubly linked list for that square. (And then dissociating them again on takeback.) Depending on the occupancy (empty, friend or foe) of the square the associated cell represents a potential move and a conditional continuation. For a Rook trajectory there would be a move if the square contains a foe or is empty, and would have a continuation if the square was empty.

A change in occupancy could thus result in a change of the move possibility as well as the continuation. In the latter case downstream cells of the trajectory would have to be associated or dissociated. Actually each square would have two doubly linked lists of associated cells, one for trajectories of white pieces, the other of black pieces. Whether the potential move is realized is interesting when we extract moves for searching. For captures no testing for this is needed; you just take the opponent pieces, look up the square they are on in the piece list, and then run through the list of associated cells of pieces of your own color; each such cell would give you a capture. For the non-captures we have to account for the fact that the trajectory can be blocked at some point, and maintain a counter for how many non-captures are realized. This will be the first N cells in the trajectory, and we would search those. So after a change in occupancy we would have to adapt this counter.

So far, so good. The problem is that fairy pieces often are divergent, i.e. capture differently from how they move to empty squares. In orthodox Chess Pawns do already do that, but at least these are not sliders. They can also be lame, i.e. their move to a distant square can be blockable on a square they cannot move to when it would be empty. (Such as the Xiangqi Horse and Elephant.) In both cases trajectories might first go through a number of squares where no move is realized, despite the fact that they are associated and have a continuation. E.g. when a capture-only slide is en-route to a distant victim. So it is not always true that the first N cells in the trajectory are the realized moves, it can also be the one move at the end.

Xiangqi Cannons present another problem; their trajectories can have two phases. First they can only move to an empty square, until they encounter an occupiece square, and then the trajectory continues beyond that, but now only with the possibility to capture. So there isn't only continuation at empty squares, but initially you continue with any occupation. If a blocker appears in the path, that doesn't change the continuation there, but it alters the properies of the downstream cells, in that these now only get continuation at empty squares, and that only captures are realized, while before it were only the non-captures.

And it can be worse! There are fairy pieces that jump over occupied squares, but then change direction as a consequence. When a square on their trajectory gets occupied, the downstream cells not only get different rules for realization of moves and continuation, but they hev to be associated to different squares.

To handle all that we could put separate trajectories for each phase of the move in the move table. When the cell is associated with an empty square continuation would go to the next cell in the move table. But an occupancy that would cause a change in direction or move/capture capability would cause continuation elsewhere in the table. It is a bit like interpreting computer code with branch instructions in it; depending on the occupance continuation could happen in different places. The cells would have to indicate where, for each of the possible three cases of occupancy. Trajectories of such pieces are in fact trees. It is even imaginable that pieces can move on trajectories that split up to continue in several different directions for the same occupancy...

[op12no2]

Just a suggestion, you could consider WebSocket as a variation on the HTTP server model. They are slightly higher up the food chain and bi-directional. At work we use them in exactly the way you are thinking of (browser in comms with executable) and it works well allowing our users to create their own UIs.

[hgm]

Thanks for the advice; I will take a look at this websockets technology.

Something that worries me, though: the simple HTTP server I made printed the names of the requested files in the terminal window it was started from, for debugging purposes. But after leaving it running for some time, it printed requests for files I had never heared of. Did I somehow leave the HTTP port in my router open for outside access??? Perhaps it is safer then to let the server use another port; the connection to this server is made from a link in a page that is opened in the browser locally, and I can easily add a non-standard port specification in that URL.

Or can there be malware that installed itself in my browser, and is spying on websites that I visit?

[MTaktikos]

When I may add some suggestions:

If we look at the project from the usual programmer sight, it will at the end make usual leaper/ stepper/ slider moves and be yet another chess variant engine with similar limitations. Let's look at it from the user perspective (which range of games can be played?) and build on some existing project not to reinvent the wheel.

The free site with the most games I found so far is
https://dagazproject.github.io/index-map.html
In this site you can test the game rules as first player against a (weak) Javascript based engine. It contains games with high space complexity like Battle of the Kings, Storm the Ivory tower, Crazy Tiles Chess, Litera Chinese Chess and Turnover. If you click on an icon, say Chess, you will find there this subvariants. And also the Shogi variants you mentioned are there
(It has also a text based UI, if you want to browse the games by name,
https://dagazproject.github.io/)
And it also contains a server, to play with humans, registration is free:
https://games.dtco.ru/
(From there you will never receive ads or annoying eMails)

Now to the programing aspect:
The whole project is open source in
https://github.com/DagazProject/DagazProject.github.io
The engine used is a modification of the Javascript chess engine GarboChessJS, for which there exists also version in C, but it appears that the programmer Valentin Chelnokov can handle Javascript better than C.
So the easiest way for you doesn't seem to start from scratch, but to contribute in this existing project. For example, as a C/C++ expert you could try to implement the modifications made in GarboChessJS in it's C/C++ pendant or in another easy-to-change C engine, and replace the existing Javascript engine by a 100 times faster one.

Just my 2 cents

[hgm]

If we look at the project from the usual programmer sight, it will at the end make usual leaper/ stepper/ slider moves and be yet another chess variant engine with similar limitations.

Not at all. The existing JavaScript GUI and built-in AI support a very wide variety of moves, that most other variant engines do not support. Such as lame leapers, bent sliders, crooked pieces, reflecting bishops, hoppers, bifurcation pieces, locust capture, multiple capture, bieces that burn their neighbors on moving (cf. Atomic Chess), pieces that passively burn their neighbors, paralize them, prevent pieces from moving past them. It supports automatic piece-type changes, dependent on where you land or what was there, can enforce anti-trading rules. Even games as complex as Tenjiku Shogi are no problem. It can play a large fraction of the variants presented on the chessvariants.com website. Some of those listed here.

I am not convinced that the JavaScript engine in the project you mention can handle more Chess variants that the JavaScript AI that I already have, if it is derived from an engine for normal Chess. In the Chess section I don't see any really complex chess variants. And I am only interested in the Chess variants; it doesn't mean much to me whether it could play Checkers or Bridge at a high level.

[MTaktikos]

Not at all. The existing JavaScript GUI and built-in AI support a very wide variety of moves, that most other variant engines do not support. Such as lame leapers, bent sliders, crooked pieces, reflecting bishops, hoppers, bifurcation pieces, locust capture, multiple capture, bieces that burn their neighbors on moving (cf. Atomic Chess), pieces that passively burn their neighbors, paralize them, prevent pieces from moving past them. It supports automatic piece-type changes, dependent on where you land or what was there, can enforce anti-trading rules

That is awesome indeed! Agree that this AI may support more variants than that of the Dagaz project.
But I didn't see the later as a antagonist to the chessvariants project, after all it is open source and perhaps it is possible to combine the best of both projects?
For example, it may become possible to add the fog-of-war mechanism and support Dark Chess, Dark Shatranj etc.?

In the Chess section I don't see any really complex chess variants. And I am only interested in the Chess variants; it doesn't mean much to me whether it could play Checkers or Bridge at a high level.

Then obviously you overlooked the games I mentioned, first of all Battle of the Kings. It is played on a normal 8x8 chess board with normal chess pieces. If this cannot be classified as chess variant, then why can other chess variants. As about complexity, after I wrote a Zillions zrf for it, I noticed that the Zillions engine can forelook only 2 to 3 half-moves, so it can be expected that the complexity is higher than Shogi.

Again, I wanted just to give a hint to another existing project, and since both projects are written in Javascript, may be there exist similarities that make it possible to combine the best of both worlds.

[hgm]

Well, I was not very much impressed by the complexity of Battle of the Kings. It is a small game, with only normal Chess pieces. The board is 8x8, so the players together in the end can never have more than 64 pieces. In Tenjiku Shogi each player already starts with 78 pieces, some of them incredibly strong. It is true that creating pieces out of nothing is not a feature for which the 'Interactive Diagram' can be configured, although it does allow displacing of a captured piece to the square you came from. The move encoding would allow such moves, though, and the JavaScript I have supports the opportunity to post-process moves after their generation with the aid of a user-supplied custom script. Which in this case would be completely trivial: just add the 'unloading' of the next-higher piece type on the from-square for every move. If there really was demand for this kind of thing (I had never seen it before...) it would be trivial to think up a way in which the user could specify such piece creation as a general option.

As to the difficulty in playing it... That is of course another matter. Conventional search algorithms for orthodox Chess can easily completely backfire in chess variants. In particular conventional all-captures (or all-good-captures) Quiescence Search is prone to search explosion, so that even a 1-ply search cannot be finished in a reasonable time by an engine that runs at 1Mnps. There is a Zillions implementation of Tenjiku Shogi that suffers from this, and I suspect that the low depth you report is caused by the same effect. To handle a wide range of chess variants you need to use more stable algorithms for the AI, which probably would cost you a couple of hundred Elo when used to play orthodox Chess.

Note that the Dagaz project mentions on the pages for all these games you mention: "no AI". Well, without AI anything is trivial. Battle of the Kings is never worse than Hecatomb, right?:

theme=MV firstRank=1 files=8
ranks=8
promoZone=1
maxPromote=0
squareSize=33
borders=0
firstRank=1
symmetry=mirror
useMarkers=1
newClick=1
Queen::::a1-d1,f1-h1,a2-h4
King::K::e1

The AI of the Interactive Diagram doesn't choke on this position. I expect Zillions would. Although at normal Chess Zillions crushes the AI, as it searches some 7-8 ply ahead, against 2 or 3, The ID easily beats Zillions at Tenjiku Shogi, usually in 2 or 3 moves.

Storm the Ivory Tower seems a simple game. Pieces change their moves depending on where they stand. Difficult for humans, but for a computer it doesn't matter. The ID handles such games by automatic promotion to a type that has the moves suitable for that square. It supports both location-triggered promotions, and capture-triggered promotions (dependent on what you capture). The spirit of this game is a bit similar to KyotoShogi, where pieecs change identity after every move they make.

Crazy Tile Chess is similar; it is basically a shuffle version of Avatar Chess, which further down on the page contains an ID where you can play against the AI. It isn't any more difficult than orthodox Chess; it has the same number of pieces, of similar types. The ID supports it completely by standard means. (Except that the graphics of the board was hand-drawn.)

[MTaktikos]

Well, I was not very much impressed by the complexity of Battle of the Kings.[...] In Tenjiku Shogi each player already starts with 78 pieces"

I was impressed that it is more complex than Shogi, but, hmkay, compared with Tenjiku Shogi...

As to the difficulty in playing it... That is of course another matter. Conventional search algorithms for orthodox Chess can easily completely backfire in chess variants

To let you try that out, I implemented a (quick-and-dirty) BattleOTK engine (i.e. no undo moves possible yet) that can easily beat the Zillions engine,
https://pixeldrain.com/u/oUQanB5f

Can't deny that I hope that you or another programmer will feel challenged to write a better one - but on the other hand, such a single-variant engine appears off-topic here, your general-engine-project is much more thrilling and other themes should not slowdown it.

Note that the Dagaz project mentions on the pages for all these games you mention: "no AI". Well, without AI anything is trivial

You misinterpreted that. The "No AI" button means that an AI is predefined, simply try to make moves on such a board and you will see the answer by the AI. If you click on "No AI", you disable the AI and can make moves for both sides, usually to test some unclear rules, or if you have another human player nearby, you can play with him human vs human

Although at normal Chess Zillions crushes the AI, as it searches some 7-8 ply ahead, against 2 or 3, The ID easily beats Zillions at Tenjiku Shogi, usually in 2 or 3 moves.

This phenomenon is very similar like in BattleOTK. In complex variants where Zillions cannot look ahead more than 2 ply, the result depends almost completely on the right evaluation function.
It may be interesting to test also some MCTS algorithms like McGrave (pre-implemented in Ludii) in Tenjiku Shogi.
I did that in 16x16 Othello. Although the Zillions engine beats easily algorithms like McGrave or UTC on smaller boards, when things get so complex, then McGrave and UTC are better - on the 16x16 board, Zillions loses.

[hgm]

To let you try that out, I implemented a (quick-and-dirty) BattleOTK engine (i.e. no undo moves possible yet) that can easily beat the Zillions engine,
https://pixeldrain.com/u/oUQanB5f

Just for fun I also tried to make the ID play this here. Since unloading pieces that were not captured first is not a standard feature, I had to add a very simple custom script on the page to extend all the generated moves with the unload:

Code: Select all

  function battleTinker(m) {
    if((m[-6] & 511) != 6) { // mover not King?
      m[-2]++; m[-5] = m[-6] + 1; m[4] = m[0]; m[5] = m[1]; // add unload to move (type and square)
    }
  }

That ran into the problem that this is a game with royals, where the royals initially are not present, which the AI assumed to be a game-terminating condition. So I had to build in a kludge to make the AI believe it has one royal in the beginning, even though it isn't on the board. (This can now be configured by adding the line baring=-9 in the game definition.) That seems to do it.

Of course the play sucks. But it does play. And (playing with white) it did beat the Dagaz AI:

Code: Select all

1. c4 h5 2. Nd4 g6 3. Bxg6 fxg6 4. Rc3 Nf8 5. Rb3 Bg8 6. Ra3 Rh8 7. Rxa7 Qh6 8. Ra8 Qg5 9. h4 Qxh4 10. Qe3+ Qf4 11. Qxf4#

Can't deny that I hope that you or another programmer will feel challenged to write a better one - but on the other hand, such a single-variant engine appears off-topic here, your general-engine-project is much more thrilling and other themes should not slowdown it.

Well, it should certainly be possible with the engine I have in mind for this new project to play it at a strong level. It might need some tuning of the default evaluation; it is not clear whether piece values still can be guestimated in the normal way for pieces with a piece-creating side effect. One assumes that the value of the unloaded pieces would somehow have to be reflected in value of the piece itself. In any case extra royals in a game with absolute royalty would have to be negatively valued. (Something that the AI of the Interactive Diagram currently doesn't do, as it assumes it is not possible to obtain those anyway. Considering the game above the Dagaz AI doesn't know it either...)

You misinterpreted that. The "No AI" button means that an AI is predefined, simply try to make moves on such a board and you will see the answer by the AI. If you click on "No AI", you disable the AI and can make moves for both sides, usually to test some unclear rules, or if you have another human player nearby, you can play with him human vs human

OK, I see, sorry about that. I now tried Tenjiku Shogi, but it turns out it plays this according to the Wikipedia rules, and not to the modern rules I am used to. (Entirely my fault, BTW, as I am largely responsible for the Wikipedia rules, which were written down in an era that I thought the modern rules made the game too unbalanced. But now that I wrote an engine for the modern rules, which uncovered a lot of opening theory, it turns out that the modern rules are very playable, and could very well have been the original historic rules.) Anyway, when I open with 1.j5-j6 (chess coordinates) against the Dagaz applet, it immediately blunders away a Bishop General through 1... BGk13xa3. (Zillions also always plays a move like that, because it apparently did not even manage to finish QS from the root, and just plays the capture of the most-valued piece under attack, even if this is a hugely losing capture.) In the modern rules it would have been immediately checkmated through 2.VGj4-o10#, which was what I played. But in Wikipedia rules the VG cannot check with a jumping move, so we played on with 2... a12-a11 3. VGo10-p8, attacking his smothered Fire Demon, for which there is no rescue, basically deciding the game. (A Fire Demon has almost infinite value; even ten Queens would be no match for it.) The Interactive Diagram seems to play it much better, and does find the only defense against the mate threat after 1.j6 in 58 sec at the default depth of 2.5 ply.

This phenomenon is very similar like in BattleOTK. In complex variants where Zillions cannot look ahead more than 2 ply, the result depends almost completely on the right evaluation function.
It may be interesting to test also some MCTS algorithms like McGrave (pre-implemented in Ludii) in Tenjiku Shogi.
I did that in 16x16 Othello. Although the Zillions engine beats easily algorithms like McGrave or UTC on smaller boards, when things get so complex, then McGrave and UTC are better - on the 16x16 board, Zillions loses.

The built-in AI of Jocly uses MCTS search, and I did implement Tenjiku Shogi for it. (The 2d representaion uses western-style pictograms.) It is of course infinitely weaker than my alpha-beta engine Inferno (it is both MCTS and JavaScript, and very inefficiently implemented as well, while Inferno is a C program and uses advanced incremental algorithms), and needs an opening book to survive the first few moves. But someone let it participate in the correspondence championship, and it actually beat one of the human players there.