Two years ago I made an MCTS connect-4 program that plays almost perfectly, just with random rollouts. Then I applied the algorithm to draughts, adding a 6-piece database. To my surprise, I lost more games to this program than I could win (5 sec/move; I used more time). I am a former club player but not strong at tactics. Maximus, however, thrashed the MCTS program, often quickly winning material (all wins but about one draw in 50 games).
The problem is that random rollouts are terrible for tactics. They favour forcing moves where the opponent has only one answer, but pure randomness will play it only with probability 1/n. Any kind of bias dramatically improves the situation, although it's an art (and a very secretive one) to make it work best. In Go, for instance, they used tricks for strings in atari very early on. Something like P = 1/2 for the capture/save instead of 1/n. Don't get me wrong: I love the idea of pure randomness giving us information; it's very elegant. But it's also terribly inefficient.
Of course this is without value and policy networks. I don't have experience with CNNs and it would be very interesting to see what they are capable of in draughts. They should, indeed, be much more powerful than the tactical patterns of Keetman. On the other hand, the Keetman patterns guide the tactical search and it is not clear to me how an A0 clone would manage this. But then again, Keetman patterns are only applied in leaf nodes and not in interior nodes, IIRC. So it is difficult to compare the techniques.
The policy network does guide the search ("progressive bias"). In AB jargon, it would play multiple roles:
- move ordering (order of exploration in MCTS)
- extension/reduction for each move
- root "bias" added to the search score (rarely used in AB programs)
- maybe others I'm not thinking of?
This could be extremely powerful. And it has to be, because it replaces all the search heuristics AG had, including RAVE (or AMAF) which is very efficient in Go.
Fabien, are you using CNNs for chess now?
No, my experience comes from working With Rémi Coulom on Crazy Stone two years ago.
Even if I wanted to use them in chess, it wouldn't be realistic because of the huge computing-power requirement. Leela-Chess Zero (LC0) needs hundreds of people donating computer time for months before becoming competitive.
That's why I made this post on G0: it gives hope that, at least in simpler games, you don't need to find a sponsor before even starting your project.