New project: very general engine for variants

[hgm]

I am considering to embark on a new project: writing an engine that would be able a very wide range of chess variants. I currently have a JavaScript program that does something like that, for embedding in web pages. But because it is JavaScript, and doesn't use the most efficient programming methods (as it evolved from a project that mainly focused on a user interface), it is very slow. It does support a much wider range of chess variants than any of the engines I have written, though. So what I would really want is to have a true engine that can do the same, but perhaps 100 times faster, so that it is capable of playing at super-human level, rather than just acting as a sparring partner for novices.

A first step would be to define some (generous) limits on what it is able to do. In JavaScript arrays are always of infinite size, so that problem did not occur there (although the move encoding put a limit on the number of piece types). The chess variant with the largest board I am aware of is Taikyoku Shogi: 36x36. For efficiency the board should of course be mapped on a linear array. I am still not sure whether I would want a 0x88-type of layout for that array; the efficiency of 0x88 tricks (such as easy detection of attackers) dwindles in the presence of pieces that can jump over others, turn around corners, etc., so that attacks can basically come from anywhere. But suppose for now that we do; a 4KB array could then hold a 90x45 board. That means square numbers would need 12 bits.

Another issue is whether the board should contain piece types or piece numbers, the numbers referring to an entry in a piece list that would contain the type as well as the location. Having a piece list is very nice, because you can quickly locate pieces of a given (colored) type. But in variants where pieces frequently change type or color it would require frequent resorting of the piece list to keep that advantage. Storing the types directly in the board would reduce the number of required piece codes compared to giving each piece a unique number, and you could change type and color whenever you want in the board without further action being required for preserving consistency of the game state.

The disadvantage of storing types is that you have no idea where your pieces are, and have to scan the board even to find your own pieces. Now the cost of that is perhaps not as large as feared; in most variants for a large part of the game about 25% of the pieces is your own, so after examining on average 4 squares you will find one. And the piece will usually have many more than 4 moves (or at least move attempts, when some of its moves are blocked), so the overhead of examining 3 other squares in vain to find it is not very large.

Besides, there are accelerating tricks possible. If each square is represented by a byte, allowing 127 types of two colors (which seems enough), you could acces those in groups of 8, extract the color bits with a mask, and use a bit-scan instruction to find your own pieces in the group. If you are prepared to do some extra work in MakeMove/UnMake, you could keep white and black 'bitboards' (actually arrays of 'rankboards'), and extract your own pieces a rank at the time. (Or multiple ranks if these would fit in a word.) You could also put all occupied board squares in two doubly-linked lists, one for each player, and remove all squares that get evacuated from the list, adding newly occupied squares at the end. Then you would just have to loop through the list of the required color to find the (actually present) pieces of that player, and nothing else, albeit in unspecified order.

Given the fact that even in large variants usually only two pieces of each type are present, it is not so very expensive to track the location of the pieces even when the board contains types rather than piece numbers. The location for a piece of a given type can then only be in two places of the piece list. (And if there occasionally happen to be more pieces of that type, you can always artificially split them up into different types with the same properties.) Sometimes you want to remain aware of the location of pieces with special properties (such as royals, or pieces that affect their environment such as Immobilizers), and having to scan the entire board for finding one or two special pieces is a no-no. In the JavaScript program I use this method: just reserve two location variables per type. If that type is removed from a square, you test if variable1 contained that square number, if so, you clear it, if not, you clear the other. If you put a piece of that type in some square, you test if variable1 is zero, if so, you put the square number (supposed to be non-zero) there, if not, in the other. This kind of thing can be done with branchless code, using the 0/1 result of the comparison as index in the location array.

You could use a thus updated piece list to loop through for finding your own pieces, and even in the face of promotions and color changes it would stay nicely sorted per type. In a variant with very many types, though, looping through the piece list is hardly better than looping over the board, even when the board empties. The piece list would also get sparsely populated. I suppose you could compact it in the root, by renumbering types, but if you have two entries per type, the list could still be half empty. It is probably better to keep a bitmap in which you record which entries in the piece list are still occupied. One for each color. Then you can use bitscan to loop through the pieces that remain. In most variants you would not have more than 64 pieces, in which case a single word per color would be sufficient.

So for now it seems best to go for a mailbox 0x88-style board containing colored-type codes of 1 byte, allowing two copies of each type (splitting up types as necessary), and use a piece list plus presence bitmap.

Another issue is the move format. In the JavaScript the move is an array, that for each board mutation contains the square coordinates and the mutation of it. In addition there are elements that tell how many squares are mutated, and a list of squares where e.p. rights are generated. In JavaScript the size of these arrays is not limited, and the list of e.p. squares uses the first 'undefined' element as a sentinel to indicate the list ends. In the engine we would have to explicitly record how many e.p. squares there are in the move. Most moves would mutate only two squares, and generate no e.p. rights. With two bytes for the square numbers, one byte for the leaving and one for the arriving piece type, and two size bytes, that would be 8 bytes. Castlings, double pushes and e.p. capture would already need more, and variants can make many additional pieces disappear (Atomic Chess!), or relocate them (pushing other pieces away, or swapping location with those). So some moves must have more storage available. I suppose this could be done by using a variable-length move format, each move potentially stored in a number of consecutive 64-bit words, the mutation counter and e.p.-square counter indicating how many continuation words follow.

[phhnguyen]

Q:
- You have known some disadvantages of Javascript, why do you use that in your new project when you may have some other choices, say WASM?
- You have already some similar projects in C, don’t you?

If you have a similar project in C/C++, or you should start a new one in C/C++ since I know you are an expert at C/C++, then just convert it into WASM for websites. Much easier, faster and the code is also much faster.

[hgm]

The JavaScript was the existing project, which evolved from an applet for interactively showing move diagrams for unorthodox pieces on HTML pages explaining the rules of some chess variant. But over the years it has grown into a very versatile configurable web GUI for chess variants, with a rather weak built-in AI (that was added as an afterthought) to act as a sparring partner for those trying to get acquainted with the rules.

The new project would try to provide the same functionality, but as a downloadable executable for running on a PC, written in C. And to avoid some of the design characteristics that contribute to the slowness of the existing JavaScript applet (such as the fact that the board is a two-dimensional array, and there is a lot of creation of new objects that then have to be disposed of by garbage collection). I have no experience with WASM, but I had the feeling that automatic conversion would not be able to get rid of such design flaws, which crept into the JavaScript project because of the way it historically evolved.

By making something that is compatible with the existing JavaScript, I can save a lot of work. This JavaScript code contains a parser for game definitions, in particular description of the moves of the participating pieces, which is a kind of compiler: it translates the input text of the game definition to a number of arrays that can be efficiently interpreted by a move generator. It also estimates piece values. By using this as a front-end the existing applet could be used to create game definitions in a computer-friendly form, that could be copied to a config file used by the C program when it must play a game in the corresponding variant. Then the C program does not have to deal with the user-friendly form of the game definitions, and can focus on the search.

There even exists a web-based wizard for assisting in creating the user-friendly game definitions, by dragging pieces of a wide variety of types from a table to a board (of interactively specified size). This could be used to create the computer-friendly game description for the C program, as it already does for configuring a server for on-line play of chess variants. So there exists a lot of infrastructure I can draw on. What is lacking is an AI that could play, say, at around 2200 Elo CCRL, when it would be configured for orthodox Chess. The goal here is to surpass the commercial program Zillions of Games (which already struggles to beat Fairy-Max).

It seems a good idea to start the development of this new AI from scratch, based on an improved design, now that I better know what exactly it should be able to do (in terms of move complexity and other rule support).

[phhnguyen]

I don’t have much experience about WASM either. I treat it as a black box. The converting from C/C++ into WASM is quite straightforward with high success rate. Perhaps, it’s a work of one or a few days, you should try. The most important thing is that WASM is much faster than JavaScript. You don’t have to maintain code in another programming language and avoid debugging in JavaScript which is not easy for chess engines.

Just remind you try not combining GUI code and engine code. It should be separated as you did with the Winboard. GUI code could be developed in pure JavaScript, using any existing library. JavaScript is surely good for GUIs. Engines could be JavaScript or WASM.

Good luck and have fun with your new project

[hgm]

Thanks for the advice! I currently have nothing in C/C++ that could be converted, though, but once this new project produces an engine, I understand that WASM would be a good way to also make it available in the web applet.

I was indeed planning to separate GUI and engine, but had not yet any clear ideas how I should implement the GUI. It would be nice if I would not have to write anything new for that, and could just use the JavaScript web applet that already exists in combination with a Windows executable to cough up the moves. I have never done anything like that, so I don't know what possibilities there are to achieve this.

What I could think of is writing the engine as a HTTP web server that installs itself on a socket as 'localhost', which you then would visit with your browser. It should be able to serve the HTML page with the applet, and all image and JavaScript files to which it refers. But instead of using its own AI, it should use AJAX to request moves from that same server at some other URL that stands for the engine.

I suppose this isn't very hard to do; I already have C code for an 'engine server' (connect.exe), which starts up an engine process on the machine where you run it, and then allows I/O to that engine through a permanent TCP/IP connection to the socket it was started at. I just would have to change that to also serve ordinary files, which seems easy enough.

[phhnguyen]

- GUI:
If you have developed any chess GUI in C/C++ you have a high chance to convert it into WASM to run on websites. My chess GUI is C++, developed with Qt and I have converted it successfully into WASM. It is not hard since Qt supported that converting. I guess almost all C/C++ GUI libraries could do the same.

If you prefer a GUI in pure JavaScript and you don’t want to reinvent the wheel, look at the program chessboardjs. It is very good one. You may learn from it and/or convert it to support other variants.

- GUI, engines connection:
You should keep their code be separated as much as possible. However, at some points they should connect together. JavaScript doesn’t have console connection, you can’t connect them with Winboard way. You may invent any new way here. However, for me, the simplest and also the most realisable is… by hard coding

You need a few special functions. Say, one named “go(fen, moves, time)” from the engine. GUI will call it when it wants the engine computing. The engine will call some special functions, say “info()”, “havebestmove()” when it wants the GUI to display some info or make a move…

BTW, the chess engine can’t keep the main loop as it typically has in C/C++ code. In the websites it should work as a flat/dump code, run only when GUI calls.

If you want more dynamics/freedom or want run a few more engines, use some indexes, use/assign some callback functions.

[hgm]

Well, I already have a GUI in JavaScript, and I have nothing like it in C/C++. That is my starting point. But it is HTML-based, in the sense that it displays the board (and whatever else it wants to show to the user) by modifying HTML elements (e.g. the image URL in the cell of a HTML table representing the board). I don't know if it could work in any other context than a browser.

So it would be a big boon if I could keep it that way, and just had the browser obtain the moves that it now obtains by calling the AI function in its JavaScript from another source running compiled C code. Since browsers communicate with servers through TCP/IP connections using HTTP this seems a natural way to do it. The GUI JavaScript running in the browser could send a HTTP POST request to the engine through the socket the latter is listening on, submitting the data that tells the engine what to do (through an asynchronous XMLHttpRequest). Like you mention, this would probably contain UCI-like info, a position (with indication what variant it is for) plus a sequence of moves to define a game history, and information about the time control.

That would set the engine thinking, and it could start sending thinking info back to the browser as a response to the request, and finally a move. When it receives the move the JavaScript would call the same routine for updating the board that is now called by the JavaScript's AI function when it finishes.

[Edit] I wonder now if this would display the thinking output as it was received, or save it up until the engine moves, and then display everything together as the server closes the TCP connection. I fear the latter. So perhaps it would be better to have the GUI poll the engine with several HTTP requests. Ofiicicially HTTP is stateless, but for this application we don't have to respect that, of course. The GUI could open the TCP connection, and send a POST request to the engine to set it thinking, which the engine would only acknowledge and then close that connection. The GUI can then submit GET requests for the same URL, and these would be replied to by the thinking output that the engine has produced in the mean time, or wait as a 'long poll' if there is nothing in the buffer, until the engine coughs up the next thinking output. If the engine finally moves that move would be appended to any yet unread thinking output as a signal that the engine is now done, and any further GET requests should then just be answered with a 404 error until the engine is set thinking again.

I also wonder if it would not be best to configure the engine for a particular variant through the TCP/IP connection, rather than through config files. A POST request that has the function of starting a new game could submit the move-generator tables and other rule info as it was already compiled to the computer-friendly format by the JavaScript in the GUI to configure it. This info would also contain the start position, so the POST requests for setting the engine thinking could then use a symbolic code for it (like UCI uses 'startpos').

[hgm]

To get back to the design of the engine's search: since some variants are quite large, and variants are on average larger than orthodox Chess anyway, I wonder if I shouldn't go to a fully incremental design from the start. I could use an 'attack map' that would consist of a doubly-linked list for each board square, which would contain a cell for each attempt of the move generator to go to or through there. Moves would be characterized by 'trajectories' visiting a sequence of squares, for leapers only a single one, and each square of the trajectory would be marked this way, even when following that trajectory had not resulted in a legal move. (E.g. because it was a sliding capture-only move, and the trajectory ended on a friendly piece or the board edge, so that there was nothing to capture.)

Each cell would then identify the piece and trajectory to which it belongs, as well as a flag that indicates whether that trajectory in principle could have continued if the occupancy of the square had been different. All leaper moves would only have one 'terminal' square, for finite-range sliders the square at the end of their range would be terminal, and for unlimited-range sliders the square just before they hit the board edge would be terminal.

This attack map would provide fast insight in which moves could be affected by a change in occupancy of a given square. The list at a square occupied by an opponent piece could serve to generate captures of that piece, so that it would be easy to generate captures in MVV order. It can also be used to update the attack map for discovered moves when a square gets evacuated (all downstream moves of non-terminal cells would have to be added to the attack map), or which moves get blocked when an empty square gets occupied. This update would take the place of move generation, as the moves to be searched would be read directly from the attack map. Of course the moves of the moved piece and those of the captured piece(s) would have to be taken out of the linked list as well, and moves from the new location of the moved piece would have to be added. But in general this would take the amount of work equivalent to from-scratch move generation of just a few pieces, while the board might hold dozens.

The cells belonging to one trajectory could be stored contiguously in an array, and each trajectory originating from each piece would have its own place in this array, with the maximum length that it could have for the applicable board size. So in Chess each Rook would have 4 trajectories, each 7 cells long. The cells would contain the to-square number relative to the start point of the trajectory (so the board step), the number of the piece to which it belongs, the first cell of the trajectory, flags indicating whether it is terminal and whether the trajectory currently ends there because of blocking. Only the latter would be dynamic information, together with the pointers to hook them in the doubly-linked lists; the rest is constant during the game.

Information that is stored for each piece would include the index of the start of each trajectory originating from it (static), and whether the trajectory leads to any moves. (Or perhaps better: how many moves, as this would facilitate incremental update of the mobility evaluation term.)

Incremental update of these datastructures would be quite fast compared to from-scratch move generation, because the volume of the involved data is so much smaller. But even though the attack map can be kept up to date cheaply, in the end you want to search the moves, and for that you would have to loop through the map. For the captures through the linked lists at the squares of the victims, and for the non-captures through the pieces and their active trajectories. Since in variants with very many pieces typically many pieces are hardly mobile for a large part of the game (because they have yet to be developed), it might be good to have a fast way to loop through all the trajectories. E.g. by storing the number of non-captures currently provided by each trajectory in a byte, and store all these 'mobility counters' contiguously, you could read them 8 bytes at the time, and use a bitscan to extract the next active trajectory, quickly skipping trajectories and pieces that won't provide any moves. That way it doesn't hurt that the attack map contains all potential moves, in contrast to a conventional move list which only contains the pseudo-legal ones. (But there of course you had displaced the problem to the generation of that list.)

Now searching non-captures is usually not so much of a speed issue; because of QS almost all moves that are searched will be captures. And for those you will just loop theough the potential victims in MVV order, and get the moves from the linked lists for the square they are on. You would have to sort these by LVA, but ther will never be very many, and often not more than one. In cut-nodes you can stop this when you reach the futile victimes, in all-nodes you would have to try all.

[phhnguyen]

- So, you want to implement a client/server model for your chess system. I think it should work since you are an expert about that model. The other advantage is that your chess engine could be a normal program, multi threads, strong and fast, without being limited may ways as a JavaScript one (weak, slow, 1 thread only)
- The main disadvantage of server/client model is that you have to pay yourself for all computing from your users because they run on your server. You have to pay more for a stronger server but I doubt you can gain any cent back. It may be so expensive when the number of concurrent users is more than a few, say, from 5th
- If your chess engine is a JavaScript/WASM and connect/be glued directly with your GUI, they all could be downloaded and run on user computers, not your server. You don’t have to pay for their computing, they can’t complain you about having weak/cheap computers. The number of concurrent users is not matters any more
- In any scenario, UCI/stateless is the best since you can’t control all seconds/bits of computing

[hgm]

The idea was actually that people would download the server, and run it on their own PC. So they would pay for the computation themselves.

From the user POV it is not very different. By the standard definitions a conventional engine is a server, and a GUI is a client. Just not a HTTP over TCP/IP server, but a UCI/WB over pipes server. The users download an executable, which is the engine, and a HTML file, which is the GUI. The main difference is that they have to start the engine directly from the OS. After that they can start the GUI by double-clicking the icon of the HTML page. This will open the page in their standard browser. The page will contain a link to the server on the 'localhost' domain (by convention translated to IP address 127.0.0.1) that they have set up by running the engine executable, and by clicking it they will be connected to the engine and can start playing.

To make life even simpler the server and the browser could be launched from a batch file, so they would only have to click that.

But of course the port on which the engine server listens could also be approached from outside the PC, so that the engine does not need to be on the same machine as the GUI. People could for instance play it from a different machine on their LAN, or from their telephone or tablet over the WiFi. (They might have to do some port translation in their router for that, though.) The engine might run only on a PC, but the GUI, being browser based, would also run on Android or iOS.