Creating a tree of chess moves

[Jon12345]

I want to create a tree of chess moves, but where each node in that tree can also have alternative moves.

e.g. e4 is the first move and so the root node. Next you have move 2, which can have c5, e5, g6 etc. Then each of these alternative moves can have a variety of different moves.

So, after some Googling, I've seen buzzwords like Binary Trees, Game Tree, Rose Tree etc. But I am not sure what data structure would suit and how to create it in Javascript. After looking at bits of code, I sense it might be relatively easy, but I am not sure how to do it.

The purpose of this project is to create my own opening repertoire that stores all the potential replies to my opponents nasty moves!

Anyone here got some pointers or code snippet that might help?

Thanks.

[hgm]

It sounds like you want to create an opening book. The question is why you want to program that yourself, if there already is so much software around that can do that.

[dangi12012]

Just use this:
https://github.com/nguyenpham/oobs

With this:
https://database.lichess.org/

[Jon12345]

It sounds like you want to create an opening book. The question is why you want to program that yourself, if there already is so much software around that can do that.

No software can do what I want it to do. For example, import all my chess.com games and then find where I deviated from my set repertoire. Rank the frequency of deviations to find the lowest hanging fruit. etc. Do spaced repetition reviews of these position and a bunch of other features.

[dangi12012]

It sounds like you want to create an opening book. The question is why you want to program that yourself, if there already is so much software around that can do that.

No software can do what I want it to do. For example, import all my chess.com games and then find where I deviated from my set repertoire. Rank the frequency of deviations to find the lowest hanging fruit. etc. Do spaced repetition reviews of these position and a bunch of other features.

All of the things you have listed can be done -again with this:
https://github.com/nguyenpham/oobs

Pick all games of an enemy or yourself (pgn) and look where he/she most often makes a non optimal move in an opening. group that by year, opening or elo or do whatever you want to! You have a turing complete language at your disposal to query literally anything.

[Jon12345]

All of the things you have listed can be done -again with this:
https://github.com/nguyenpham/oobs

Pick all games of an enemy or yourself (pgn) and look where he/she most often makes a non optimal move in an opening. group that by year, opening or elo or do whatever you want to! You have a turing complete language at your disposal to query literally anything.

I've been searching for some images of what this program does and can't find any. It sounds interesting, although there seems to be a misunderstanding. I am creating my own app with a feature set that I want to develop. Not sure what you are referring to when you say "turing" complete language.

Edit: I found an image of OOB and it is nothing remotely like what I am seeking to develop.

My question is really only about seeing an example of the tree I described, using javascript, as opposed to the validity of my idea.

[hgm]

You can implement the tree as an array of structures {move, nextMove, nextPosition}, or as 3 separate arrays move, nextMove and nextPosition. The latter two would contain the index in the array where you would find the next move from the same position, or the first move for the position to which the move leads, resprctively. These could hold the invalid index value -1 if there are no more moves, or the move would lead to a position that is not in book.

When building the tree you could just fill up the array from index 0 on; you would never want to remove anything. This would make it hard to look for transpositions, though. You could of course add a 4th info to identify the position (e.g. holding the FEN), and for any new position you reach do a linear search through the array to see if that position was already there. This is a slow method, but if your repertoire is not too large it could be satisfactory.

A faster method would be to use the array as a hash table: put the first move for any position in a location derived from the position. In JavaScript you can even do this by using a structure rather than an arrray, i.e. an array indexed by the position FEN. But since this is space consuming, and only needed for the first move from any position, it would be better to use an auxiliary arra 'dictionary' that is indexed by the FEN, and contains the number of the first move for that position in the other array(s).

[Jon12345]

You can implement the tree as an array of structures {move, nextMove, nextPosition}, or as 3 separate arrays move, nextMove and nextPosition. The latter two would contain the index in the array where you would find the next move from the same position, or the first move for the position to which the move leads, resprctively. These could hold the invalid index value -1 if there are no more moves, or the move would lead to a position that is not in book.

I am a little confused by the move, nextMove, nextPosition structure. So move would be the move under consideration, be it your own or your opponents. nextMove would be a number indicating which entry in the move array that contains the next move. And nextPosition would be ???

Did I get that right? Not sure what nextPosition would contain.

[smatovic]

Idk how Lc0 stores the MCTS tree in memory, maybe worth to take a look, I used a single array of structs for an BestFirst search with game tree in memory:

Code: Select all

__global NodeBlock *board_stack_1;

// node tree entry
typedef struct
{
  Move move;
  Score score;
  s32 lock;
  s32 visits;
  s32 child;
  s32 children;
  s32 parent;
} NodeBlock;

With child and parent as index to an array element, child points to the first move of the subtree, and then via the numbers of children you can iterate through the next n items in array, the siblings.

--
Srdja

[hgm]

You can implement the tree as an array of structures {move, nextMove, nextPosition}, or as 3 separate arrays move, nextMove and nextPosition. The latter two would contain the index in the array where you would find the next move from the same position, or the first move for the position to which the move leads, resprctively. These could hold the invalid index value -1 if there are no more moves, or the move would lead to a position that is not in book.

I am a little confused by the move, nextMove, nextPosition structure. So move would be the move under consideration, be it your own or your opponents. nextMove would be a number indicating which entry in the move array that contains the next move. And nextPosition would be ???

Did I get that right? Not sure what nextPosition would contain.

NextMove would be where you find an alternative move from the same position. NextPosition would be where you find the first move from the position that will result from playing the corresponding move. For what you want only the opponent would have alternative moves, so nextMove for your own moves would always be -1.