Computer Moves

While putting together the move calculator with all the required testing, my mind did occasionally drift towards the complexity around the computer player, how it was even possible to work out the next best move. Where do I even start with something like this? This is not the first time I have had this type of problem. I do remember working on an old project, a very long time ago, a tiny Othello (Reversi) game, which also had a computer player. Not as complex as a chess game, but the basic principles can still be used here too.

The method I used was based on calculating a weight value for the current state of the board. If the white player makes a move, the ending result would be a board with a rating of 3.34, but if a different move was made, the board would end up with a rating of 4.56. The second move would be seen as better than the first, because the rating value was higher.

With this board rating method. I can check each possible move, seeing which rating is best and selecting the one with the highest value. This can be used to work out the next move too. After white has made its move, I can check all the possible moves the black player could make, find the highest rating (the best move) and then subtract that from the previous white move. Branching down through all the possible moves and counter moves to find the next best possible move. This does sound like it will grow into something very big and complex.

There are two main parts to all this. The first is how to calculate the board's rating/weight value. The second is handling the branches of possible moves and putting all the rating values together to search for the next move. This is what it may look like when I put them together.

At the top I have the current state of the board (white to play). In the level below is a list of possible moves the white player can make, showing what the board ratings would be if the moves were made. Below that are the possible moves the black player could make (if the 3rd white move was made), also containing the ratings values. I am not sure how one level would affect the ratings of the move before it, whether to average them out, or pick the largest value (or smallest depending on the player). This is only a theory at this point. I'll take the gamble that this is the way ahead and just hope it is correct when I get to the point of building it.

Boards Rating

How do I rate a board's state? Do I have a value for the white player and another for the black one? Perhaps I should only have a single value for both players, plus values mean good for the white player, negative values mean good for the black player? What do I look at, where do I even begin? I have come up with a list of things I believe I need to include.

• Each piece has a value. A pawn is 1, a rook is 3, and a queen is 10, for example. The more pieces you have on the board, the higher the value is.
• If a piece is attacking an opponent's piece then this increases the value.
• If a piece is under attack then this decreases the value.
• If a piece is defended by another piece then this increases the value.
• If the opponent is under check then the value is increased.
• If the player is under check then the value is decreased.
• Putting the opponent into checkmate, or being in checkmate, increases or decreases the value by a very large amount. This is the final state I want so it will be given a very large value.

What values do you give the pieces, and how much weight of importance should be given to that part of the rating calculation? I want to have this type of adjustment inside some type of configuration, so that it can be adjusted to change the overall outcome and rating value. Perhaps I could create different types of bots, one that puts more weight into attacking moves, and another that prefers a defensive rating.

So, I now need a module for calculating the board's rating and class for holding the configuration settings, but what do I call them? What is a good name for the board rating calculator class? Maybe "board-rating", "rating", and what about the config, "rating-config", "bot-config" or "computer-player-config"? The configuration may include other settings that are not just related to the rating process. I may have a list of different configurations somewhere, for different computer player types.

I think I will have "board-rating" and "computer-player-config". There will be a "computer-player" module too in the future, that will handle all the parts needed to make a computer work out the next move.

Intrinsic

I am going to start with what I am going to call "intrinsic", the basic value of each piece on the board, no matter where it is located. I want to give a value for each type of piece, a queen will have one value, where pawns will have a different one. All these intrinsic values are added together to give a total. I also want to include an "intrinsic coefficient" that is multiplied against the total.

Here is the start of the computer player config class, which has some default intrinsic values. I didn't include one for the king, as this seems somewhat pointless, as both players always have a single king. This is also going to be an object, which means there can be multiple copies of them in memory, so that it is possible to have one computer player compete against a different computer player (with different config settings). Also, each of the properties will have their own getter and setter.

Inside the BoardRating class I have created the calculate function. The first part of this is to call the private _calcaluteIntrinsic function, which will work out all the intrinsic parts of the ratings. The coefficient part will be used later, however.

The process is to move through each of the board's squares looking for pieces, and depending on the piece found, it will increase (if white) or decrease (if black) the total. If the piece is empty or one of the kings then nothing is done, and the total is not adjusted. Splitting up the calculation into sub parts allows me to test each one individually.

Attack

The next part is to look at each piece and see how many other opponent pieces are attacking it. The rate will be based on the type of piece being attacked, a pawn would have the value of 1, and the queen would be 10. Then I multiply this against the number of different opponent pieces attacking it. For example, if a rook (5) is under attack from a pawn and a bishop, the "attack" rate would be 5 * 2 = 10. The result is that the more valuable pieces you have under attack, then greater the rating value will be.

The computer player config constructor now includes attack related properties. I don't have a setting for the king, because this being under attack would make it be in check, and that type of thing will be processed elsewhere.

Working out how many times a piece is under attack is more complex to work out. I will need to look in all directions to see if the piece can be seen by pawns, rooks, queens and so on, in the same sort of way as when I looked to see if the king was in check.

To calculate the attack rating I need to go through each of the pieces on the board. I can do this by looping through each row and then each column within.

After getting the piece, the first thing to do is to see if it is empty or one of the kings. There is no need to continue processing the piece if it is one of these.

The next part is to get the total number of pieces that are attacking the location. This will use the _getAttackCount function, which is created so that it can be used to calculate the number of opponent pieces that are attacking a square, and can also calculate the number of pieces defending a piece too. If there are no pieces attacking, then it stops and moves on.

The final part is to set the attack value, depending on the piece, and then multiply that by the number of attacks made on it.

I was not sure what to call these functions, because though they are used to work out the number of "attacks", it will also be used to work out the number of "defended by" pieces too. There doesn't seem to be a good word to describe what it is doing. Maybe I could use the word "link", or "attached", "capture", but there is nothing that doesn't seem to lose its meaning. I'll use "attack" and just make sure I have spelt out what it is I'm doing in the comments when using the function to do something a little different.

Some of this is going to look familiar because I have taken large parts of it from the _inCheckKnight function. I am doing the same type of thing. I first set the knight piece I want to look for, then set the list of knight move adjustments, and loop through them. I am keeping a count of all the knights I find and return the result at the end.

Inside the adjustment loop I make the changes to the next row and column, then make sure they are not outside the board, get the piece at the adjusted location, and then check to see if the piece is the knight I am looking for. If it is, then I increase the count. I do this for each of the possible knight locations and not stopping if one is found.

All the other attack count functions do the same type of thing as the inCheck related functions. When it comes to attacks with pawns, I have ignored any "en passant" checking, because it doesn't seem to fit when working out the defence parts of the rating, and it doesn't add much to the overall rating calculation. It seems like too much work for little to no return.

I have added a king attack count function, but this is a little different, as only one king can possibly be attacking at once. Therefore, instead of counting the number of attacks, I just return the value 1 when I find the first king.

The testing required for these functions was long and detailed, taking a long amount of time and effort. I know it's important and everything, but it can be very boring writing them all out and double checking everything works correctly. Also, there is no real guarantee I have covered everything, and there aren't some edge case bugs waiting for me later. I have an uneasy feeling of impending doom, a belief of inadequacy and failure, which no amount of testing can help with. I say to myself that I have done enough and whatever happens in the future is in God's more than capable hands.

Defence

This is very similar to the attack rating, but I want to look at how many pieces defend another piece. If one rook is defended by nothing, then it could be captured by the opponent without any counter-capture event. But if the rook is defended by one or more pieces, then the opponent is less likely to capture it, because it could be re-captured in return.

Just like the attack rating, each defence piece will be given a value, making the queen more important than a pawn. There will be a defence coefficient to help calibrate how this all adds to the overall rating.

Again, this is very similar to the attack rating but in reverse. The function for calculating the defence rating is also very similar.

The two functions start off looking exactly the same. Set the total, loop through each row and column, and then finish by returning the total rating value. The parts inside the row column loops look very similar too.

Again, I am getting the piece and checking to see if it is empty or one of the kings. I only want to look at pieces that are not kings, because these are processed later, when looking at checks and checkmates.

The next part is a little different. I do not want the opponent/attacker player type, like I did last time, but I want the piece's player type. When I call the _getAttackCount function, I want to use it in reverse. Instead of looking for who can attack the piece, I want to know who can defend it. If no one is defending it, then I move on to the next piece.

Depending on the piece, a defence value is assigned, which is then used with the defence count to calculate an overall defence amount, which is then added to the total rating value. White pieces are given a positive value and black pieces a negative one.

Check and Checkmate

Putting the opponent player into check is great. Putting them into checkmate is even better and is the final goal. If the board is in either state then I need to give it a rating to match. The check rating should be large, highlighting to the computer player that this is the better move and one that should be taken. The checkmate rating would need to be even higher still, in affect forcing the move to be chosen.

The configuration will contain the check and checkmate rating values. There really isn't much more to this, if the board is in check, then the rate total will have 100 added to it, for a white player, or -100 for a black player. Also, if the board is in checkmate, then the value 10,000 is used instead.

Final Equation

I can put all the different rating parts together and come up with a final ratings value. It works by using the coefficient values for each ratings type to rise and lower how important each one should be seen within the final score. If the value is above zero then the white player has a stronger position, but if the value is negative then the black player is better off. The larger the value the greater the status is, the more likely it is that the player will win.

The first section is to get all the rating values for the different parts, the intrinsic, attack, defence, check and checkmate values. These are then put together into one single ratings value. I can now use the computer player config settings to adjust the final ratings value depending on what factors I want to promote.

The result is that the more the players are equal in strength the closer the board rating will be to zero. If the white player is stronger in an attacking position, but the black player has a greater defence, then the rating value will even out and be close to zero, though this would depend on how the attack and defence coefficient values compare.

Branching Overview

I can now give each board a rating value that will help me pick which move is the best one to perform next. The next part is to create a branch of different possible moves, not only at the next level, but one move ahead, and then probably the one after that too. How many branches deep I can go will depend on the computer player's config settings and maybe some other factors too. I want to take the following things into account before I make a start.

• How many levels down the branch can I go. Different computer player configurations can have different values for this. The starter player can go 1 or 2 branches down, but the higher-level player could spend more time thinking, going 5 or 6 plays into the future.
• After calculating all the different ratings, the end result may be a number of moves that have very close ratings values. I don't just want to always pick the best, otherwise the computer will be playing the same game all the time, but I want to have a top 5% - 10% of move ratings to randomly pick from.
• The computer move calculations will need to be performed in a worker thread. The calculations may take time to perform and would create problems if performed on the main thread.
• All the calculations need to be broken down into smaller sections and not performed in a single function call. There needs to be an option to cancel the computer player, just in case it is taking forever.
• It should be possible to save some future moves and rating values that were calculated in one move, so they can be used again after a move has been made. This way there would be no need to recalculate the same boards and ratings for the next move.

My first design for this will involve the creation of nodes that will build up a large tree of moves. I will then process the tree of nodes to work out the final move to make. The whole process of creating the branch of nodes will look something like the following.

1. The "computer-player" module will have a function that starts off the whole process.
2. The "next move" processing will be done in a "branch-worker" thread.
3. This will take the starting current board and use the "node-worker" thread to create a list of nodes. These nodes are the possible next move with their rating values.
4. The nodes are returned to the branch worker and added to the tree it is creating.
5. If these new nodes need processing, then each one will be given to the node worker for it to create the next level of nodes.

There will only be one branch worker, running in its own thread, but there can be any number of node workers, in their own threads, all running at the same time. This all sounds great, but putting it together and testing it will take some thinking, time and hard work.

I am not sure what to call all these things. They are all inner parts to the "computer-player" module and could be named to take that into account, something like "cp-branch-worker", "cp-node-worker", where "cp" is short for "computer-player". I could put the source files into a "computer-player" subfolder? As the number of source files continues to grow, the more complex the whole library becomes, and the less orderly everything feels. I see a list of different file names that are starting to lose their meaning. What does "node.js" do again?

The tree of possible moves will be made up of node objects. Each node can contain a list of child nodes and will also contain a link to the parent node (unless it's the root node). It is called a tree but it starts at the top and works its way down, fanning out its branches as it goes, so it is more like an upside-down tree. Each node has the following parts.

• A board object that reflects the state after the move has been applied to it.
• The possible move that was made to the board.
• The board's rating value.
• Each player's move and counter move is a new level.
• List of child nodes.
• A link to the parent's node. If the value is null, then the node is the root.
• Flag used to state if the node has been processed or not.

I may need other properties in the future as I can't be totally sure what is required to build the computer player at this stage of development.

I am not really sure how to create and use worker threads, so I need to create some prototype example code to see what is possible and how to pass messages and data between the different worker threads. The code will look a bit rubbish and hacky, but at this point it's all guess work, hope and reading online documentation.

This is my ruff computer player class with some starter functions. I want to be able to create more than one computer player at once, so I can end up having one playing against another, both with different configuration settings. This is why I am not using static functions. It will be used by creating a new ComputerPlayer instance, then calling the initialize function once, followed by calling the play function each time the computer needs to work out its next move.

When creating the worker object, I am using the URL object to create the full web address of the "branch-worker.js" file on the server. Because the chess library may be located in an unknown location on the server, it needs to work out where the worker JavaScript file is located relative to the "computer-player.js" file. This is why I am using the "import.meta.url" parameter, which gives the full URL location of the source file.

When the play function is called, the board and the computer player config object data is posted to the branch worker using a message. It will not wait for the branch worker to perform the tasks, but it will just return from the function right away.

I do include the _onMessageEvent function that is used to receive messages from the branch worker. This will include progress information and the final chosen move that was calculated. I am using the bind function on the event, which is used to control how the "this" keyword is used inside the event. I want the event to be linked to the computer player object when it receives messages.

At the moment the "branch-worker.js" file is very basic. It contains the BranchWorker class which has the single messageEvent function. This will receive messages from the computer player and process them as required. It only logs the event data for now. There is also a self.addEventListener line, which is used to link the received message to the static messageEvent function. The keyword "self" is only used within a worker and is related to the worker and its functions. If I were to use this source file outside a worker then it would fail to load.

As workers can only be used within the browser, testing needs to be done differently. I have created a "web-computer-player.html" file that loads in a "web-computer-player.js" source file and then perform all the testing within it.

The HTML file is very basic. All it does is load the required source file and run the test.

The testing JavaScript file does not do much at the moment. It creates the computer player object, plus the other required objects, initializes the computer player and finally calls the play function. I use a NodeJS Express server application to show the page in the browser and look at the console to see the results.

Node Worker

I am going to start looking at the node worker before I build the other, higher level, sections. I believe this should be a simple and easy worker to create, compared to the branch worker, as it doesn't really need to do much. Basically, it does the following.

1. Receive a node from the branch worker.
2. Create a list of possible moves for that node.
3. Calculate the ratings for each of the moves.
4. Create a list of nodes for each possible move.
5. Return the list of nodes back to the branch worker.

This is the start of the node worker. The message event will receive posted messages from the branch worker. I created some testing code to make sure it will work as required.

Everything seems like it should work nicely, however I came across a problem which breaks the worker design, possibly stopping things from moving forward. When I create the ComputerPlayerConfig object, it looks like this.

It contains private properties and the getter and setter functions. However, when the object is sent to the worker, I get this.

All the functions, including the getters and setters, are not sent to the worker, in fact the ComputerPlayerConfig object is no more, replaced by a standard Object with only private properties. The object cannot be processed like the class it should belong to. It has lost what it is.

It seems that transferring data to and from a worker is done using a structured clone of the objects, which loses what the object is and only keeps the inner properties. I could do the following.

This creates the ComputerPlayerConfig object and copies the property from the worker data into it. It is extra work, but it does solve the problem. This type of thing will also need to be done for the node data, which itself contains board and move objects. However, it does end up creating an extra object that is unused. I just don't like this approach. I need to come up with a better method of dealing with these structured clones and workers.

The Board class has a clone function that creates a new board object and copies over all the private members, which is the sort of thing I want to do. I think it would be best to use "clone" functions for all the objects I transfer between workers. I send a board object to the worker, then the worker clones the data it gets to create a new Board object. It's not perfect but it could work.

I have added a clone function to the computer player config class. This takes either another computer player config object, or a basic object that contains the same private properties from the structured clone of a computer player config object. I have done this for the Move class too.

The node clone function requires some extra work. It needs to create a clone of the board and move objects. It also needs to go through all the child nodes and clone each one of those too. Then it needs to clone the parent if that exists (which it shouldn't do, as this is never used when being transferred to and from a worker).

Cloning does seem to have fixed my structured clone problem, and I can now send and receive node data back and forth between workers without losing any information.

While creating the node worker and thinking about what data to send back to the branch worker, I wondered how it would handle the data it received back. The branch worker is going to be sending lots of node data to a number of different node workers, but how will it know which data it gets back belongs to which node it sent. It will send nodes A, B, C, and get back possible move node lists X, Y, Z, but which one belongs to which starting node?

I think I need to give each node its own unique ID number. The branch worker assigns the ID number before it sends it to the node worker. After the possible moves are created and the node list is sent back, it also includes the starting nodes ID number. The branch worker will then use the ID to find and set the node it was processing.

I can start to build the node worker now. This will receive nodes to be processed and return a list of child nodes it has calculated.

I start by creating the NodeWorker class which contains only static properties and functions. This will be receiving messages from the branch worker, which is done with the messageEvent function. It is called each time it receives data. To link this function to the event, the addEventListener function is called with the event type of "message".

I have also included a static computer player config object. This will be set once by the branch worker before it sends any node data to be processed.

Inside the message function there are a number of different parts to be performed. The first step is to check the data received contains the computer player config information. This will be used later when processing the board's rating values. I use the clone function to convert the structured clone data into a real ComputerPlayerConfig object.

The next line makes sure the data type being processed is only for node data. This isn't really needed as it should only get "config" and "node" data types and nothing else. But I like to make double sure, you never know what you'll end up doing in the future. After this I convert the structured clone node data from the branch worker into a real Node object. This will be the parent node that will be processed. The next part is the creation of a node list, which will contain all the nodes that are going to be sent back.

The node worker will then perform its primary job, by creating a list of all the possible moves the parent node can make. This uses the parent node's board, and the board's current player, along with the move calculator, to return a list of moves.

The next part is to go through all the moves and process each one to create a node object that will be returned to the branch worker. There are a number of steps for each possible move. The first one is to check if the move is invalid or not. It may be that the possible move puts the player's king into check, which isn't a valid move. These invalid moves can be overlooked.

The next part is to create a new node object. This is followed by creating the board, from the parent's board with the move applied to it. The node's move object is then set. Now that the new board is created, the board rating calculation is performed to work out its rating value. The node's level is set to the parent's level plus one. Finally, the new node object is added to the list of nodes.

After all the calculations are made and the list of nodes is finalized, the last part is to send the data back to the branch worker. The returned message contains the "result" type, the parent node's ID value and the list of nodes it created. This is all that the node worker needs to do.

Starting the Branch Worker

I have a feeling this part is going to be more complex than the other worker. It must do the following tasks.

• Get the computer player config information.
• Receive requests to process the next computer player move.
• Keep a tree of node moves.
• Create node workers, send messages to them and process the messages received back from them.

I also want to send progress messages back to the computer player object, to give the user some type of indication of how much time is left before the move is worked out. There may be other tasks to perform that I haven't thought about yet too.

This is the start of the BranchWorker class. It looks somewhat similar to the NodeWorker class, with it containing and handling messages. I have split the incoming message into sub-functions that are used to handle the different data types. Messages will come from both the computer player object and from the node workers ("result"). There may be other message types in the future, but for now these are the only ones I think I need.

I have also included a number of static (global) properties that will be used by all the other functions. The computer player config object will help control how to process the computer moves. The node id property will be used when assigning new nodes their ID value. Each time it is used it will be increased, making sure that each one will be unique.

The root node is the base of the node branches. The node list will contain the same nodes but they will be stored in a flat list, which will make it easier to move through them one at a time. I also need to keep track of all the node worker objects that exist, so I can reuse or terminate them.

All the config message function does is set the static computer player config property. This will be used elsewhere in the other functions but will also be passed on to the node workers.

My first look at the play message function looks simple, but it passes the more complex parts on to other functions. I first want to check that all the node workers have been created, set up and are ready to be used. I then create the Board object from the event data, which will be the starting place to look for the next possible move. After this the node list is recreated, so that any new unprocessed nodes can be added to it. Then I reset the root node. This will look at the old node tree and find where the current board is located and use that as the new root. After this I look for the next unprocessed nodes and use them to get the next level of possible moves.

All these functions are just ideas of what is needed. The parts relating to resetting the root node have me troubled, as I am not sure how to find it with just the board. It would be nice if I could pass the node ID, but I don't have that information. Once the human player makes a move the ID value is lost.

Let's take a closer look. The play function is given a board to process. Because this is the first move, a new node is created containing the board and is given the ID value of 1 and then added to the node list. The next node is then looked for, and because there is only one in the node list, node 1 is sent to the node worker to be looked at. The node worker takes node 1 and creates a list of possible moves, adds them into a list of nodes and returns it to the branch worker.

The possible move nodes are given the ID values 2 to 5 and added to the root child node list and the other list of nodes. All these child nodes will each be processed, starting with node 2, which results in child nodes 6 to 10. Later on, node 6 is processed, resulting in nodes 11 to 13. Now if the moves made in the game are node 2 (the computer player), then node 6 (the human player), then the next play will be for node 6, which should be the new root node. All the other nodes, 3 to 5 and 7 to 10 (plus their child nodes), will be removed from the tree.

After thinking about this more, I believe it would be best to move all this branch node tree functionality into its own class, so that I can keep the branch worker less cluttered. Sometimes when the tasks look too big to handle, splitting it up into smaller blocks can help.

Branch

My goal here is to handle all the node branch related tasks I was trying to do in the branch worker. The tasks and functions it needs to handle are as follows.

• Keep a tree of nodes.
• Keep the same nodes in a list for easy access and processing.
• Add a list of nodes to a parent.
• Get the next unprocessed node.
• Check to see if all nodes have been processed.
• Reset the root node.

I have called the class and the file "branch", which seems to fit well for what it will be used for. I have added some properties and function names that I think will perform all the tasks required.

The played function will be used for each move that is made in the game, starting from the first board, followed by each move the human and then computer makes. It will update the root node and node list each time it is called. It will also update the node levels and any other parts that need resetting, ready for the next move.

The next function will be called to get the next unprocessed node. Each unprocessed node will be sent to the node worker and will be returned with a list of child nodes. These nodes are then added to the branch tree by calling the add function.

While processing the branch, looking for unprocessed nodes and adding child nodes, there will come a point when all the nodes, up to a given level, have been processed and the whole computer move calculation task has come to an end. Calling isFinished will work out if this state has been reached, or if there are still unprocessed nodes that need looking at. Hopefully these are all the functions required by the branch worker.

The start of the played function looks to see if there is no root node, or if there is, if it contains any child nodes. This can happen at the start of a new game, or if the human made the first move (there would be no computer moves in the branch, the add function has not yet been called). It can also happen if the board is refreshed in the middle of a game.

If the root node exists and there are child nodes, then possible future moves have already been calculated, and their child nodes are part of the branch. Therefore, it now needs to find which of the first row of child nodes the given board belongs to. This will be the new root node. To do this I loop through all the root node's child nodes and compare their board to the given board. The Board.compare function does not exist yet, so I'll need to create it.

Comparing two boards to see if they match requires me to check each of the different properties one by one. I cannot perform a simple "board1 === board2" comparison because that would only check to see if the two boards are the same object, where I will have two different objects that may have the same board layout and setup. It requires each square on each board to be compared too, looking at each piece in the same location on both boards.

The next part is to create the _resetRootNode function. This takes the found child node, which is one of the current root node's children nodes, and sets this as the new root. However, there are a number of other tasks that need to be performed.

This shows the starting point of what I want to do. I have a tree of nodes and a list of the same node objects. The ID of the node is also the index of it within the list. This should make it quick to find a node using its ID, as it is the index in the list. In the example above node 1 is going to be reset as the root node.

After the reset has been performed, node 1 has become node 0, and is the first node in the list. The node list is cleared and each of the nodes are added back in, but while doing so their ID values are also reset. The levels are changed too, as the older level is removed, all the levels above them are moved down.

The first part of the reset process is to clear the parent property of all the nodes that belong to the current root node. They all point to the root node and therefore have a reference to that object. By clearing the reference, after removing the root node, it can be removed from memory. If I didn't clear the parent property, then it would stay in memory and create a memory leak. The root node is no longer needed, therefore why keep a reference to it.

The next step is to set the root node to the new node given, reset its ID, level and parent values, clear the list of nodes, and then add the new root node as the first item in the node list. The final part is to add all the node children, and sub children, to the list of nodes, which will reset their IDs and level value. This is done by calling the _addNodeChildrenToList function, which will call itself as it moves up all the node tree branches.

This function is called using the root node and level 1 as its starting parameters. For each child node it resets the ID and level values, adds it to the node list, and then calls the same function again but with the sub child node and the next level up. This uses recursion to move through all the nodes within the tree branches.

Moving on to the next function, which is used to fetch the next unprocessed node that needs to be looked at. The returned node will be passed on to the node worker, which will return a list of possible move nodes.

The function has a level parameter, which controls how far ahead it is to look. This function is going to be called a number of times, and I didn't want to start looking at the list of nodes from the very start each time. It would be a waste of time to loop through the whole list again and again. Instead, I am using a _lastNextIndex property that is used to record the last index that the loop had gotten to before, so that the next time the function is called, it starts off where it last finished. The only extra thing I need to do to make this work is to reset the property back to zero whenever the root is reset.

While going through the loop of nodes, it checks to see if the node is already processed. If it has then it skips that node. It also checks the level the node is on, making sure that it does not process any node that is over the level limit. Once a node is found, it records the last index used (for next time) and then returns the found node.

I now move on to creating the add function, which takes the parent node ID and a new list of children nodes to add to it. The node's ID is basically just the node list's index value, so getting the parent node is very simple. For each node in the list a number of steps are performed. This includes adding the node to the parent, setting the ID, level and parent properties, and then finally adding it to the main node list.

The final part to the branch class is the isFinished function. This is used to work out if there are any more nodes that need processing, and if not then the next stage of calculating the next computer move can be performed.

To work out if there are any unprocessed nodes, I need to go through the node list, checking each node to see if it is within the level limit. There will be nodes on the last level that will not need to be processed themself, therefore these are not checked. Only the nodes on or below the level limit are checked. Each one of these is checked to see if they are processed or not. If they are not yet processed, then the function returns that the branch is not finished. However, if after checking all the nodes in the list there are no unprocessed nodes, then the function returns that the branching has finished.

I have added a number of tests to make sure all the branch functions perform as required. They do not need to be done within the browser, even though they are going to be used only within the branch worker module.

Back to Branch Worker

Returning to the branch worker class I can now remove some of the older node handling parts and replace them with the new branch instance.

I am also going to change the names of some of the events.

The old event "play" is now called "run" and will be used to run the computer player operations and calculate the next move. I have added the new "played" event that will be used to tell the branch worker that the human player has made a move.

The renamed _playMessage function has also been changed. It calls the branch's played function with the board that was given with the message. This will start the computer player move calculation process. The first step is to check all the node workers are set up and ready to be used.

I have a question about node workers. How many should be created? The more there are, the more nodes can be checked at the same time, but the more computer resources are used up. If a small computer only has 4 CPUs then should there only be 2 or 3 node worker threads? It is not possible to know how many threads are available, so what happens if I create 8 node workers when there are only 4 available threads? Should the number of node workers be hard coded or configurable? I am going to add an extra property to the computer player config class to control the number of node workers that will be created.

By default, the number of node workers that will be created is 4. The browser can handle occasions where there are not enough threads available and still allow things to operate as normal. I can now create the _checkNodeWorker function and create all the node workers required.

The first thing the function does is to check to see if the node worker list already exists or not. If the list has been created before then it just stops and exits the function. After this it creates the node worker list object and moves on to filling it up with node worker objects. I loop for each of the node workers required, creating the worker object, pointing to the "node-worker.js" file, adding the event listener, and then adding it to the list of node workers. The final part in setting up the node worker is to post the computer player config object. Before I move on, I want to make sure I handle the "cancel" event.

The cancel event will be called while the computer player run process is underway, to stop it and reset the branch worker, so that it can restart a new computer player run. The first check is to see if there is a node worker list, and if there isn't then it just stops, as this would only happen if the computer player run hasn't yet started. After this it loops through all the node workers, removing the message event listener, and then terminating the worker, which stops it running and removes it from the computer. The node worker list is then cleared, which will allow it to recreate a new set of node workers the next time the run message is received. The final part is to recreate the branch object, so that all the old possible move nodes are cleared and stopping any invalid board data corrupting the branch tree of nodes.

I have another question. The branch class uses a level limit when calling some of its functions. What level should I use and where should it be stored? I think each different computer player config should have a different level, the less challenging bot would have a lower-level limit, and the best bot would have a higher-level limit. I am not sure how high to go, how many moves in the future is enough, and at what point does it no longer matter or will it take too long to calculate.

I have added another property to the computer player config class. This controls how many levels, moves ahead, the computer player should look. The current board will be level zero, one move ahead (the one the computer is looking at next) is level 1, and the following human move is level 2.

Inside the _runMessage function I made a call to _processNextNode to start the whole run process. This will be used to look for existing unprocessed nodes inside the branch object and send them to the node worker, so that they can create the list of possible moves.

The processing is split into two parts. The first part continues to loop, getting the next unprocessed node from the branch object. Only when there are no more nodes to look at (for the time being) does it stop looping. I cycle through all the node worker objects, so that I do not end up only using one but instead spread the node processing to all the node workers. For each unprocessed node I post a message to have it processed. Afterwards I set the node as processed, so it doesn't get looked at again.

The second part is to check if the whole run is finished, which is done by checking with the branch object to see if there are any unprocessed nodes remaining. If the run is finished, then the final move can be calculated and sent back to the computer player object. Before I move on to this final part of the whole branch worker process, I still need to finish some other parts first.

This function is called whenever the node worker posts a message containing the result of it processing a node. It returns the ID of the node that was sent to it, plus a list of the next possible moves that it could make, stored within nodes. The list of nodes needs to be converted into node objects, because at this point, they are just structured clones of the nodes that were sent from the node worker. Then they are added to the branch to continue building up the final node tree structure. After this I call the _processNextNode function again, which processes any new nodes that may still exist.

The last message event that needs to be added is used to handle when the human player makes a move. When this happens the branch object needs to be told, so that it can adjust the root node and all the node IDs and level values. The function doesn't do much, it just creates the board from the event data, and calls the branch's played function.

Final Calculation

The last thing to do within the branch worker is to take the finished node tree of data and use it to work out which move is the best one to make. I have had this in my mind for a little while now and I am still not sure how to do it. Below is a diagram of the type of thing I will have to work with.

The result is a tree of nodes. Each node is shown with its board rating value and its index value in the top left corner. At the top of the tree is the root node, which is the current board's status. It may have a rating for the board, but it will not be used in the following calculations.

Below the root node are two possible moves that the computer player needs to pick from. The ratings values reflect which move is best depending on the player's type. For the white player, the higher the number the better it is, and for the black player, the lower the number the better. So, if the computer player is black, then move 1 (-0.4) would be the best move to make, because it is the lower value. But if the computer player is white, then move 2 (1.5) is better, because that is the higher value.

The next level is for the opponent player and therefore the opposite value choice needs to be made. For example, if the computer player is black, I am looking for the lowest value in level 1, but it is the white player who will be moving in level 2, and therefore I am looking for the highest value move instead. But how do the highest values in level 2 change the values in level 1?

I am taking the highest value in level 2 and adding it to its parent node board rating value. Therefore, the highest value 4.3 is added to -0.4 to become the new 3.9 value. This is also done with the other node, adding 2.0 to 1.5 to make the new value of 3.5. The level values have now changed, from -0.4 and 1.5, to 3.9 and 3.5. Now when selecting the best move, instead of the previous move 1, using information from level 2, the new better option is move 2. But what happens if I look at level 3 as well.

Nodes at level 3 are moves made by the computer player again, which in our example is the black player, and therefore the rating values I want to look at are the ones with the lowest values. The process is the same as before, where the lowest value is added to the node's parent board rating value. This changes the values of the nodes on level 2. This has the effect of changing which of the nodes are chosen on level 2, and then has the knock-on effect of changing which node is selected in level 1. Using level 3 node information has made move 1 the best looking option.

If the computer player was white instead then the results would be very different. I would be looking for the highest value on levels 1 and 3, and the lowest values on level 2. I now need to create the functions needed to process the tree of nodes in this way.

To help with all this, I need to add a new property to the Node class to save the adjusted rating value. While going through the tree nodes, picking the best move to make, and adding that node's rating value to its parent, the new adjusted rating value needs to be set, so that current rating value does not get changed. The rating value needs to remain unchanged because it will be reused again in future computer moves.

The function that will set the branch tree node's adjustedRating property was going to be part of the branch worker, but I now believe the best place for it is in the Branch class. This way I can perform a number of tests on it, making sure it is processing the nodes and setting the correct adjusted values.

The Branch class now has the new adjustRating function, which will set each node's adjustedRating property. This is done by calling the private _calculateAdjustedRating function on the root node.

This function calls itself for each child node that belongs to the given parent node. This way it sees all the nodes getting the very root values and passing them back down the tree branches, adjusting the rating values as it goes along. It starts off by creating the best rating value and marking it as unset. If there are no child node items, then the best rating is automatically set to zero.

It then loops through each of the nodes, calling the same _calculateAdjustedRating function, which returns the node's calculated adjusted rating value. This is then compared to the best rating value, so that I get the highest value (for white player turn) or the lowest value (for black player turn). At the end the adjusted rating value is set using the parents current rating plus the best rating value (of the child nodes). This final adjusted rating of the parent node is then returned, so the parent node can use it.

After all this I have a root node that contains all the possible moves the computer can now make with adjusted board rating values, which will help me see which one will be the best one to choose. All I now need to do is select the largest rated move (for white player) or the smallest rated move (for black player) and then post a message back to the computer player object. Job done. However, there is just one more addition I want to make.

Final Move

If after all this processing and calculations I end up with a list of moves that all have similar ratings, then picking the highest (or lowest) could end up with the computer player always making the same moves. I want to add an element of randomness into the last part. I am thinking I could take the highest (or lowest) value, reduce the rating amount by 10%, and then randomly select from all the moves that are over this value. I would be selecting from the top 10% of the best moves. This would need to be configurable depending on the bot used.

I have added a final rate coefficient value to the computer player config class. The value of 0.1 can be seen as being the top 10% of the best move rating value. A value of 1.0 would end up selecting all the possible moves, both bad and good ones, and then randomly select from one of them.

I now move on to working out the final move. This starts by calling the branch's adjustRating function, which sets all the adjusted rating values for each of the nodes in the branch tree. I then want to find the root node's best child node move.

This is done by setting the first node as the best and then looking through all the others. This depends on the player's type. If the player is white then I want the highest adjusted rating value, but if the player is black then I want the lowest. If a better node is found then that is used as the best node.

After I have found the best node, then I can use the final rate coefficient value to calculate the final rate limit. Any node that has a better adjusted rating value than this limit will be part of the final node list and could be selected as the final move.

The next part is to create and fill the final node list. I again loop through all the root node's child nodes and compare the adjusted rating to the final rate limit. If the node is over the limit then it gets added to the list.

The final part is to randomly select one of the final nodes and post it back to the computer player object.

Progress

Now everything is finally finished within the branch worker class. At this point I have no confidence that any of it will work. I have created a large amount of code and tested almost none of it. Also, after thinking about how it will be used, I have thought of something that is missing. Should I send back progress information? It would be nice to show the user how long the whole process is going to take. Should they wait 10 to 20 seconds, or is 10 minutes too long?

But I don't think you can tell how long it will take, because I have no idea how many future moves there are going to be until after checking all future moves. How long is a piece of string when you can't see the end?

My first idea is a little complex so I hope I can describe it clearly. First take a theoretical count of all the pieces on a board and the moves they could possibly make, for example, a pawn can make 1 move, a rook can move 7 vertically and 7 horizontally, and so on. Then use this total amount and multiply it by itself a number of times relating to the level limit the computer player is configured to use. If the total was 25, and the number of levels is 4, then the overall number of nodes to be created and processed is, 25 * 25 * 25 * 25, which ends up being 390,625 nodes. This is a guesstimate and will probably be larger than the real number of nodes processed.

As the nodes and levels are processed the overall total and the current progress values are adjusted to be more and more accurate. Sounds possible but it also sounds difficult to build and test. I think the best approach is not to give progress information that contains a fake overall total, but maybe a better idea would be to just send a total count of the number of nodes that have been processed. It may also be possible to send how many levels have been processed too, which could give the user some idea of how long things are taking. However, checking if level 6 is finished could end up looking through over 100,000 nodes, which could take a lot of time to process.

The easiest method is to just send the total number of nodes created so far. The user can see something is happening and get an idea of the speed of the whole process. In the future I could add a better method, but this project has been going on for so long that I am looking for lazy options.

In the Branch class I have added a nodeCount getter function that returns the number of items in the node list. This is a very quick and easy way of counting the number of processed nodes so far within the branch tree.

Inside the _processNextNode function, which is called to check for new nodes and sends them on to the node worker, I have added some additional code which gets the current node count and posts it back to the computer player object. This seems like an easy solution to handle progress. I just hope it is good enough.

Testing

Before I make a start on the computer player class, the one that talks to the branch worker, I want to create some testing code. This is all done using the "web-branch-worker" HTML and JavaScript files. It's a good thing I did these tests. Here are the errors I fixed.

When receiving the "config" message, I was not using the clone function with the structure clone data that was passed with the event data. This was a problem later when I was using the nodeWorkerCount property that didn't exist and wasn't working.

I was using the forEach function on the root node, instead of using it with the list of nodes in the root node. I missed the property when writing it, a simple error to make.

This next problem is related to the node's "processed" property and the branch's isFinished function. The root node is added to the branch and the _processNextNode function is called for the first time. For each child node it posts a message to the node worker to get it processed, and after doing this it marks the node (the root node at this point) as processed. Now whenever the branch's next function is called, it will not pick the same root node again, because it has been marked as processed.

A little later now the branch's isFinished function is called, but at this point there is only one node in the list (the root node) and that is marked as processed, therefore it will believe that all the nodes are processed and everything is finished. The problem is, there are node workers busy doing their thing and they haven't returned the resulting nodes yet. There are waiting nodes.

I need to mark the node as "waiting for results" and only once the results have been received does the node get marked as processed.

In the Node class I have removed the processed property and replaced it with processWait and processDone. After the node is first created and then sent to the node worker, the processWait property will be set to true, and after it has returned with the resulting data, the processDone property is set to true.

In the Branch class, in the next function, instead of checking the processed property, the new processWait and processDone properties are checked. The same thing is done within the isFinished function.

In the branch worker class, inside the processNextNode function, after posting the node to be processed, instead of setting the node's processed property, it now sets the processWait property.

The last part of this processing issue is done within the add function of the Branch class. At the end it sets the processWait property back to false (as it is no longer waiting for anything) and also sets the processDone to true (as it has now been fully processed).

The next bug is within the result message function. I was using the nodeId property, which isn't being sent from the other worker, when I should be using the id property instead.

Inside the Node class's clone function, I was not copying the id value, which was making all nodes the root node. I was also processing the parent property and making a clone of that. This ended up cloning itself forever and creating a stack overflow. I have removed it.

I performed some tests to make sure the cancel process works correctly, but it turns out that my approach was completely wrong. I created a long test, with a computer player config setup so that the level value was set very high, which meant the branch worker would spend a very long time trying to calculate the next move. This gave me time to start and then to cancel the process before it could finish and return the result. The branch worker looks out for a "cancel" message and would then terminate all the node workers. The problem I was having is that the node workers were constantly sending results to the branch worker, which was blocking any messages being sent from elsewhere. I was sending a "cancel" message, but the branch worker was not getting it, or it was stuck in a queue. The whole process was not being stopped but carried on.

I have removed everything related to the "cancel" message type in the branch worker. Instead, later, I will terminate the branch worker from within the computer player class. Calling the worker's terminate function will not only remove the branch worker but also remove all the node workers it created too.

Well, that was fun. Debugging and fixing the issues was a real challenge. Working inside the browser's developer tools made it all possible, adding break points and moving through the code line by line helped me see what was going on. But still, the complexity was high, with a number of different threads all working at the same time, passing data between themselves, falling over or infinitely going on forever, it was a real puzzle at times.

Back to the Computer Player

I last looked at the computer player class while I was prototyping some designs and trying to work out how everything was going to look. It is time to return to it and finish it off. There will need to be some additional parts for handling progression and maybe some other parts too. Just a reminder though, this class will be used in the main GUI thread, and its primary goal is to interact with the branch worker.

I start off by adding in the private properties inside the constructor. I use the bind function to make sure the keyword "this" always points to the ComputerPlayer instance. The even listener list will be used later and is a way of adding and removing progress and move events.

Before the computer player object can be used in a game, it needs to have the begin function called. This is used to create the branch worker object and set up the message event.

Whenever the computer player object is finished with, it is important to call the end function. This will remove any event message links and then terminate the branch worker, freeing up resources. You can call the begin function again afterwards if you want to resume using the computer player object.

The config function is used to send the computer player configuration object to the branch worker, which will then at some point send it on to the node workers too.

The run function is used to start the computer player off, to have it look for the next best move. It sends the board to the branch worker, which in turn starts off the node workers.

After the human player makes their move, this played function will need to be called to readjust the internal branch tree, ready for it to make the next computer move.

After the computer player has started its run, this cancel function can be called to stop it. It removes the message link, terminates the branch worker, and then recreates it and the message link. It does away with the current branch worker and recreates everything relating to it anew. You can continue making another computer move afterwards.

I wanted to add away to pass events from the branch worker onto whoever wants to know. Elements use a function to add and remove listeners, which are called whenever those events are triggered. Even though I am not using element objects, I still want to use the same function names to perform a similar task. This way the coder will understand what they are for. In this addEventListener function, the type and listener callback function are added to an object and then added to the list.

When removing the event listener, I must go through each of the events in the list, and check to see if there is a match. If a match is found, then it is removed from the list.

When events are received from the branch worker, they go through the _messageEvent function. I loop through all the event listener objects in the list and check if they match and call the listener function when required. I check if the event listener's type is either "progress" or "move" and pass the data on to the listener callback function.

There really isn't much to the computer player class, because most of the hard work is done in the branch worker. Below is a diagram of the steps needed to operate the computer in the browser.

You only call the begin and end functions when adding the computer player to the browser, and if you need to remove it to free up some resources. When starting a new game you need to set the computer player's configuration information. After this you take turns between the human player and the computer player, calling either the played or run functions. When a move is made, the board is then checked to see if the game is over, and if not, then the next turn can be performed.

Second Approach

While testing the computer player in the browser I started having some problems with the Branch class. Starting with the full default board I made the first move by computer, then followed that with a simple black pawn move, but it was here that the bug happened in the Branch class, in the played function, it could not find the played board in the list of nodes.

Though this is being tested in the browser, I want to test it using the same testing progress as the other parts of the chess library, but because it uses web workers that just isn't possible. This got me thinking. Maybe someone will not want to use the web workers to calculate the computer move. Instead of using multiple threads, I should create a computer player that runs on the calling thread (no web workers). It will block the thread until the calculations are finished but that is up to the developer using the library.

But what should I call it? I was thinking of renaming the current "computer-player" class to "computer-player-web", as it is only used on a browser. Then I would recreate the "computer-player" to work without threads and web workers. This seems like a good idea.

I start off with the constructor which sets the computer player config to null and creates a new branch object. There are no begin and end functions, and no event listener functions either, as these are all web related and are not needed here.

Some of the functions will be similar to the computer player web class. The config function doesn't need to send the computer players config anywhere, it just needs to store it locally to be used later.

The played function only needs to pass the board on to the Branch object for it to reset the root node.

The run function will perform the computer player calculations to work out the next best move to make. This takes different parts from the branch worker and node worker modules, putting them together to perform the whole process in one place. It first tells the branch object that the current board has been played, setting up the board ready for the computer player. It then loops forever, getting the next unprocessed node and processing it, which will add new nodes to the branch, that are then themselves processed within the loop. This continues until all the nodes, to the required level, are processed, at which point it breaks from the loop. The final part is to work out the final move and return it.

To process the node I need to get, and check over, all the possible moves the computer player could make. All the valid moves are added to the node list and then added to the branch.

A move could be invalid. This is when a move puts their own king into check. These invalid moves are skipped and not added to the list. Each move needs to be added to a node. The move is applied to the board and that board is then rated. The node's level is set to be one higher than its parent. This whole process is very similar to how the branch worker and node worker were performing these tasks.

The _workoutFinalMove function is very similar to the branch worker's version, except instead of posting the move to the computer player object, it returns the final node's move object.

I am now able to perform some testing that isn't done within the browser. I wanted to perform the same test as the web version that is creating problems.

This performs a computer player run, then a human player moves, at which point it throws an exception in the same place as the web version. This is good news. It fails in the same place doing the same thing. The question is, why, what am I doing wrong, what is the bug?

Branch Problem

I believe the problem I am getting is related to the Branch class and the played function. This is used to find and reset the root node, depending on the move that either the human or computer player made. I think this is related to when the played function is being called.

To illustrate what I think is happening, take a look at the branch tree of nodes above. I want to make the computer player start the game. This is done by calling the computer player's run function which calls the Branch's played function with the starting board. Because this is the first time the branch object has seen a board, it creates a new node and uses that as the root node. So far, there is no node tree, only the root node.

The computer player run process looks for all the possible moves and adds them into the branch tree of nodes. The result after this process looks something like the diagram above. The computer picks a move (2.9 in this case) and returns it. The board is adjusted with the computer's move. However, the root node has not been changed to the one containing the move that was returned.

The human makes a move and the Branch's played function is called to update the root node. The problem is that the branch was not updated with the computer's move. The played function looks through all the root node's child nodes to find the one that contains the move that was made by the human (by comparing boards), but it is looking at level 1, which are the computer moves, not the human moves, which are currently on level 2. I hope you are following me here. I think, after the computer makes its move, I need to automatically call the played function to update the branch's root node.

In branch worker and the computer player classes, at the end of the workoutFinalMove function, after I have selected the final node, the final move to make, I tell the branch object that the computer player has played that move. This will reset the root node to the new board.

After making this change, even though it fixed the problem I was having, I did come across another issue. When the computer player run function is called, it starts off by calling the branch's played function, even though it may not be required. The board parameter passed to the function may be the current root node already.

In the Branch class, inside the played function, after I have made sure the root node exists, I check to see if the board parameter is the same as the current root node, and if it is then no extra work is required. With both these changes made, all the testing made up to this point passes. Success at last.