A better algorithm for picking the opponent's lines

[olleeriksson]

Hi

I've been looking for over a year for a site or mobile app that allows you to actually "play" out your repertoire against the computer, as in the computer responds but only with responses from your repertoire. I used Chess Position Trainer (CPT) for a while because it allows random lines, but CPT has no mobile app and it's just so old and slow. Then I found the Android app Chess Trainer (Pro) which has random lines. And suddenly (instantly) training opening lines was just FUN. I'd take out my phone when I had a few minutes over, practiced a few lines and then put it away. And I learned a lot of lines really really fast.

But then I realized their algorithm is just too simplistic. I'll explain below. So I went looking again for another site and found yours, and was so happy to see that it also allows you to "play" your repertoire, and pick any of your own lines that you like. But then I realized your site also suffers from the problem I found with Chess Trainer Pro.

So, the problem I find is how the algorithm appear to work by picking the next move randomly among the variations available, at each position. On your site it doesn't actually seem random, but I think you go through them sequentially. But the problem is that if the repertoire branches are not evenly distributed the whole thing breaks down. If you have a big e4 tree in your repertoire, and one short non-e4 side line (no tree, just one line) the algorithm will choose this one non-e4 side line 50% of the time, even if 99.99% of your repertoire's positions are in the e4 tree. So, what's needed is something a little bit more advanced.

1. From the current position in the repertoire, find all possible tree leaf nodes.
2. Pick a random leaf node from that list and use the first move in that line as the move for the computer to make.

This way there is not this heavy weight placed on an early side line if there is only one or a few sub-branches inside it.

Would you consider allowing the algorithm that picks the line to be random and to work according to the way I described above?

If you want to I could maybe even give it a go and try to create a Pull Request for this. I've never programmed in Elixir but about 10-12 other languages. Maybe you could even give me a pointer as to where in the code this algorithm is implemented. I tried looking around a bit but could use some pointers.

[ArneVogel]

Hi,

I see what you mean. But I have to defend my algorithm. It does not pick randomly of the variations available.

Consider the PGN 1. e4 e5 (1... a6 2. d4 b5) 2. f4 f5 3. g4 (3. h4 h5) (3. b4 b5 4. c4 (4. d4)) 3... g5 (3... d5) (3... c5) (3... b5) 4. h4 *. It will mostly stay in the e5 reply lines, only rarely going into the a6 line.

---

The study interface is all done in JavaScript.

If you want to look into improving the algorithm the responses are generated here: https://github.com/ArneVogel/listudy/blob/8fa1618934714863f63e449030c65c9a6e981eec/assets/js/study.js#L205

From the possible moves at the current position we use the one with the lowest value: https://github.com/ArneVogel/listudy/blob/8fa1618934714863f63e449030c65c9a6e981eec/assets/js/modules/tree_utils.js#L164 while requiring it has at least one grandchild so the player has to make a response to the ai move.

A value in this context is how good somebody is at remembering the move. 0 being not learned or did a mistake at the move and 1-5 being how many times in a row a correct response was made at the move position.

Now there are some situation where it could allow for "weird" behavior. Consider this move tree:

It could happen that it always picks the left subtree (since it has the lowest value with the 2 child). Now if you always pick the left most move, unaware of the move with the value 2 ( I think 2 is the threshold where the arrow hints are not shown anymore) the algorithm will always pick the left tree.

So maybe what is needed is more statistics on picked lines and then deviate from the "optimal" lowest value if some line was repeated multiple lines or if at some decision point one a single move is ever picked. This would be up to discussion.

Happy for any input.

[olleeriksson]

Hi and thanks for the awesome response! I tried your PGN and you're right, it does work with your example. It's great to hear it is supposed to work this way. I would love to use LiStudy for training my repertoire. But maybe I've come across a bug then. Because I've managed to set up several examples that illustrate the opposite behavior.

The simplest example I could come up with: 1.e4 e5 ( 1...Nf6 2.e5 ) 2.Nf3 ( 2.Nc3 ) *

Here it will pick e4 and Nf6 as the first response by black the same number of times. First time e4, second time Nf6, third time e4, fourth time Nf6 etc.

A slightly more advanced example is below, because I thought maybe there was some special behavior on the first move, but the same behavior exist here on move 2. After e4 e5 and then Nf3 black will respond with Nc6 and Nf6 one after the other forever. First time Nc6, second time Nf6, then back to Nc6 and then Nf6 and on on on.

1.e4 e5 2.Nf3 Nf6 ( 2...Nc6 3.Bc4 ( 3.Bb5 ) ( 3.d4 ) ) 3.Nxe5 *

I haven't set up the server on my own computer, but unminified the code in the browser and tried to debug. It appears that the values are never actually updated, at least not until move 3 (where I see the values being increased from 0 to 1) but they also appear not to be saved after starting over from the starting position between lines. By the way I'm running with Key move off, though it makes no difference.

Also, as the values are always 0 the Math.min(5.. kicks in on line 77 in the function update_node_value(node, value) so the actual value being compared with is always 5. And since both branches end up with 5 I suppose it picks the one you didn't get to play last time.

I would love if you want to give me your take on it. Is it a special circumstance I've uncovered or am I misunderstanding something. If not I'll see if I can set it up and run a local copy some time next week.

I like the quality of the code by the way. :) Super easy to read.

[olleeriksson]

Just realized after debugging it more thoroughly that what I was seeing with your example was an example of that "weird" behaviour that you described. It kept going into the e5 lines because there was one move in that subtree that I never played. I'm going to think a little more about this and then get back to you. I think I have a few ideas.

[olleeriksson]

Alright, I have looked at the algorithm now and think I understand a bit more about what it's doing. I've been debugging it for a good couple of hours.

The algorithm does indeed in effect pick the larger subtrees more often, but because of the "weird" behavior it often goes to the other extreme where it only plays one side because you have a neglected sideline somewhere. And as you say, after 2 moves it stops showing the arrows.

Instead of showing the arrows only for moves that have a value less than 2, it could also show them for moves that have been played less than say 40% of the most popular move at the current position. Once a move has been played less than say 40% compared to the most popular move, arrows to indicate a "forgotten" subtree could be shown, maybe even with a different color to indicate "reminder".That way the arrows could come and go (instead of disappearing permanently after the move has been played 2 times), steering you into lines you haven't played in a while.

However, I also have a suggestion for a different algorithm, which I believe would alleviate the "weird" behavior altogether, and rely less on the user playing all lines evenly. It think it should be very simple to implement, but work a bit differently. I'd be willing to give it a shot and demo it to you, if you think it's a good idea. If we call the current algorithm a "play whole tree eventually" algorithm, my suggestion would be more of a "random tree weighted" algorithm.

My suggestion is to count the total number of nodes (or possibly node leaves) in each sub tree and play the next ai move randomly but weighted towards the subtree with the most nodes. Ie if one subtree has 100 nodes, and the other 50, then there's a 2/3 chance that the next ai move will come from the first subtree, and 1/3 chance from the second. I find the problem with the current approach is that it relies on the user too much to never neglect a sideline (even if you can fix the missing arrows). It still relies on the user to play every single line, or the parent moves up until this sideline gets picked every time. With a more random approach the computer will act more like a real player, and there would be less focus on getting you to play every single line. This will hand over the control of where the ai plays the most moves to the author of the repertoire. Where the author puts in most moves is where the ai will focus its effort. If you play long enough all moves will be covered. Also, if the user avoids playing certain lines in the repertoire intentionally then the algorithm doesn't get in the way. It's a different way to train perhaps but one I find more "game like". You could still show arrows to "remind" the user of forgotten lines, but perhaps in a color that lets him know it's just a reminder not to forget certain lines.

This new algorithm speaks to one of the main reasons I was drawn to your site. I really liked the feeling of playing against a computer, where you are free to choose your own lines, while the ai is forced to follow your repertoire. If you've added something to your repertoire but after a while you start to realize you never really face those lines in real games and you want to stop training them but keep them in the repertoire, then it would be nice to not be forced into those lines on a regular basis. The current algorithm actually doesn't force you into any lines per se, but the effect is still there since you're forced into the subtree that contains those lines, you're just not being forced to play the lines themselves. If there is a gambit line deep within the e4 tree that you never play and don't want to play, it will still keep forcing you into e4.

So..

1) What do you say I (or you) try to fix the weird behavior above with a "need_hint limit in %" in addition to the hard coded 2 of today? I'd create a new issue just to isolate this code code.

2) Would you also be open to having a more random-based algorithm weighted towards the largest subtree, maybe in addition to the current algorithm even? There could even be a dropdown allowing the user to select the algorithm himself? I'd be happy to try to implement that, and let you evaluate what you think about it.

BTW. It took me a while to understand why sometimes not all arrows appear, but now I realize these are not to show all possible moves, but more like "remind" arrows of specific moves you haven't played in a while. This in itself I find a little troublesome. I think that if I always saw the same arrows in a specific position I think I would learn faster which options I have there, but at the same time I see the need for "remind" arrows too. Anyway, just something I've been thinking about. The only solution I've got to this is to always show all possible moves when there is an arrow to show, but highlighting the ones which are pure reminders. This way the user doesn't get fooled into thinking this is the only line to play in this position. I'd be happy to give this a go as well if you think that's a good idea, or are willing to let me demo a solution for you.

[ArneVogel]

I like the idea. I thought it would be an upgrade to the current algorithm.

So unless in actually trying it something obviously is wrong which we don't see right now I would be happy to add this.

If you think 1. is a quick fix then I think its worth pursuing, otherwise the old algorithm could just get replaced with the with the weighted random algorithm.

I don't think it would be necessary to keep both algorithms around. So a dropdown wouldn't be needed.

As to the arrow appearing: chessground (the board framework I use) added overlays. Maybe some text could be shown there for more context instead of relying on colors. I would need to look into the library at some point.

[olleeriksson]

Awesome! Great to here that you like the idea. I'll get to work as soon as I can. And then we can see how it feels.

Cool about the chessground overlays. I guess I've been using some of them on Lichess. Maybe a shaded background arrow like this to indicate "forgotten" moves..

I will focus on the algorithm and then we can perhaps take it from there.

[olleeriksson]

Alright, I've published a pull request now at https://github.com/ArneVogel/listudy/pull/131. I might open another issue on the arrows, we'll see. More info in the PR.

[olleeriksson]

Implemented!