A tree size weighted random algorithm for selecting ai moves.

[olleeriksson]

Alright, here's my first ever pull request on an open source project. :)

This implements the new algorithm. Instead of picking lines that contain the least played moves, this picks a random move but weighted towards the candidate subtree that is the. largest. This means the parts of the repertoire that conatains most moves are most likely to be played by the ai.

There are some functions in tree_utils.js that are no longer used, but I didn't remove them until I had let you have your say. They are:

• has_grandchildren
• date_sort
• value_sort

I've been testing the algorithm on both your example and my two examples, as well as on a larger repertoire, as both colors. I left some commented out console.log lines that you might want to enable if you want to get a better idea of how the algorithm performs. They are:

study.js: line 204 tree_utils.js: line 209, 224, and possibly line 252

It outputs stuff like this:

Finding moves after starting position
   Candidates: e5 (8),  f5 (18),  Nf6 (120),  d5 (98)  - Rand(1-245): 147, Pick: d5
Finding moves after 2.c4
   Candidates: dxc4 (18),  Nf6 (10),  Nc6 (13),  c6 (18),  e6 (37)  - Rand(1-97): 50, Pick: c6

The number in parenthesis is the size of the subtree from each candidate move. "Rand(1-245): 147" indicates that adding up the tree sizes of all candidate moves gives 245 so it picks a random number between 1 and 245. It happened to be 147, which if you go through the candidate moves' tree sizes gets you to the fourth move, which in this case is d5.

Let me know if you want me to delete the unused methods that I kept around, or the commented out console log lines and I will do that. Also, any suggestions or wishes you have, let me know and I'll adjust the code.

On a different note, I do feel the arrows ought to be looked at so they don't only show moves you haven't played yet, but I'll open up another issue on that and perhaps experiment a little before I suggest any changes. And of course, it's only if you agree a change would be good.

[ArneVogel]

Code looks good.

I tested it out and one thing I think could use improvement is make it not to pick the same move twice in a row. See: repeat.webm

This is from https://lichess.org/study/MBQ3N0F8 on the first chapter for black.

Since this chapter is so short this is especially noticeable but I think it would still be nice to not repeat even in longer lines.

What do you think?

[olleeriksson]

I actually thought about that too... and I kept thinking about it for some time. I started pondering whether there could be an option that controls to what extent the algorithm is forced to vary itself, perhaps in absolute terms on every move, or maybe only within a few minutes of the last move being played. I thought about slightly nudging the AI towards a different move next time, maybe just a slightly higher chance it picks a different move.

But then the more I thought about it the more I realized that I don't think that is the way to go. I think this is just something that feels weird in really really short lines. Even if you just add one more move to the repertoire it become much more natural with a purely random order based on the size of the tree. Let's say you have a big repertoire with both e4 and d4 lines. If we tell the ai to never play the same move twice in a row, we're going to get that old behavior of e4 first, then d4, then e4 etc, even if the majority of your repertoire is in say d4. Another example is if you include Reti openings (1.Nf3) or English (1.c4), but only want a few moves for those "off-beat" openings, then the AI will play those subtrees as much as the main e4 and d4. So while it may be temping to go that way I don't think it's going to be better.

Maybe it might work to add that functionality when you are one move from the end of the line. So that you don't get the exact same line as last time. But then again, how do you find out if you are one move from the end of the line? Unless all your lines are equally deep it's going to get weird. That is obviously what happens when you have a really small repertoire with one or two move lines like in your example.

So I honestly don't think it's a good idea, at least not if you want to cater the algorithm to large repertoires, which admittedly is how I use the opening trainer. I think if you want to use it for really short lines maybe this algorithm is not the way to go, and that is why I was suggesting a dropdown.

[ArneVogel]

Good point. Merged. Thanks for the pr. :+1:

[ArneVogel]

Also added to the changelog: https://listudy.org/en/changelog