Games/second Engines

[hgm]

If we are talking about non-searching engines... I also experimented with those some time ago. I don't remember exactly how fast the games were, but I played many hundred-thousand, so it cannot have been very long. In particularly I wanted to figure out what the optimal relative probabilities were depending on the piece on the from- and the to-square. All I recall was that the results were a bit disappointing; the optimized engine did not completely crush a pure random mover. Much more important than what you capture is whether what you capture is protected.

My non-searching engine N.E.G. keeps track of that, by counting the number of attackers and protectors of each square, as well as the lowest-valued attacker and protector. It then assumes the recapture would gain the attacker when the piece was sufficiently protected, and only the value difference it was not, in retaliation to a capture. It then just chooses the move that gains the most, also taking a PST-like centralization bonus into account. This totally crushes a random mover, but then stalemates the latter in half the cases. With some bias for checking moves, and stalenate protection by refraining from capturing the oponent's last minor, you can boost the score to nearly 100%.

This algorithm would be at least 2x slower than a pure random mover, because it has to generate moves for both sides. I never tried how many games per second I could pump out with that. But it seems a good algorithm for playing the rollouts.

[jhaglund2]

This algorithm would be at least 2x slower than a pure random mover, because it has to generate moves for both sides. I never tried how many games per second I could pump out with that. But it seems a good algorithm for playing the rollouts.

I would be exicted to see this in action. The more variations of games/sec people come up with, the better.

[jhaglund2]

Here, after 1 day, it played 437,544,860 games. I'm looking forward to testing this type of move selection on positions. If only your page had a set FEN option.

86400 s | 437544.86 kr | 5.06 kr/s | h4

1. h4

h4 408 51277 / 21878672 (0.0023436980087274037) ****
h3 409 7018 / 21880248 (0.00032074590745040913)
g4 407 2007 / 21880618 (0.00009172501434831502)
g3 410 12719 / 21880876 (0.0005812838571910923)
f4 407 -23594 / 21880000 (-0.0010783363802559416)
f3 409 -34697 / 21872471 (-0.0015863319695337578)
e4 409 -17187 / 21874305 (-0.0007857163919036513)
e3 411 -43708 / 21873615 (-0.001998206515018208)
d4 409 -30144 / 21870383 (-0.0013783023370006827)
d3 411 -26680 / 21884033 (-0.0012191537090078415)
c4 410 -18557 / 21872935 (-0.0008484000889683986)
c3 411 -35570 / 21866865 (-0.0016266620752448968)
b4 408 29101 / 21882516 (0.001329874498892175)
b3 409 21095 / 21880055 (0.0009641200627694948)
a4 408 39442 / 21875583 (0.0018030148042225893)
a3 409 15908 / 21880372 (0.0007270443116780647)
Nh3 410 10234 / 21884321 (0.000467640736945871)
Nf3 409 36084 / 21878691 (0.0016492760010185252)
Nc3 409 32357 / 21878408 (0.0014789467314075138)
Na3 410 -5594 / 21869896 (-0.00025578539559584554)

[op12no2]

Here, after 1 day, it played 437,544,860 games. I'm looking forward to testing this type of move selection on positions. If only your page had a set FEN option.

Well I actually feel quite bad about my last reply, so given you have taken such an interest in Roller, I'll do some tweaks along the lines you need. I want to stress though that Roller is very very slow, a 'proper' implementation would get at least 2 orders of magnitude speed up in my estimation. And fix the 50 move rule bug. Also I don't want to add a search strategy and turn it into MCTS. I like it's 'Pure MCTS' form - that is Roller's USP kinda thing. That and the 'no knowledge' restriction, so no piece values etc.

[hgm]

I think we discussed this before, but a 'no-knowledge' restriction does not exclude making some parameters that affect the move choice during the entire game part of the game state, and subjecting those to the search algorithm too. I guess the usual MCTS algorithm would then discover it is a very good 'move' to bias the move choice towards capturing a Queen very early on in the game.

[op12no2]

I think we discussed this before, but a 'no-knowledge' restriction does not exclude making some parameters that affect the move choice during the entire game part of the game state, and subjecting those to the search algorithm too. I guess the usual MCTS algorithm would then discover it is a very good 'move' to bias the move choice towards capturing a Queen very early on in the game.

I totally agree with that and in that way MCTS is (can be) game-independent. @jhaglund2 mentioned piece values which would go against the Roller philosophy and that's what I was getting at. I probably confused the situation saying "Pure MCTS" by which I meant no search strategy at all (other than simple root rules) rather than classic MCTS with game-independent search heuristics like you mention. NB: As I recall Roller always beats a random mover with the exception of 3-fold repetition draws because it does not know that rule.

[hgm]

I guess it would be better to just call it MC, because you don't really construct or search a tree.

[op12no2]

I guess it would be better to just call it MC, because you don't really construct or search a tree.

lol, fair point On reflection I misinterpreted what the Wikipedia article called "Pure MCTS".

[jhaglund2]

Here, after 1 day, it played 437,544,860 games. I'm looking forward to testing this type of move selection on positions. If only your page had a set FEN option.

Well I actually feel quite bad about my last reply, so given you have taken such an interest in Roller, I'll do some tweaks along the lines you need. I want to stress though that Roller is very very slow, a 'proper' implementation would get at least 2 orders of magnitude speed up in my estimation. And fix the 50 move rule bug. Also I don't want to add a search strategy and turn it into MCTS. I like it's 'Pure MCTS' form - that is Roller's USP kinda thing. That and the 'no knowledge' restriction, so no piece values etc.

That is great to hear!

The w/l/d breakdown for the moves would be nice.
Keeping counters for each additional ply would also create a PV line upto however many you'd like to display.

Not adding any knowledge, but an option for the computer to select the move based on the most wins, most draws, or wins+draws, least losses, besides the current total overall win-loss score

Option to only play games on a selected move.

Thoughts about writing the games to a file for database generation?

Thanks!

[dangi12012]

Not adding any knowledge, but an option for the computer to select the move based on the most wins, most draws, or wins+draws, least losses, besides the current total overall win-loss score

You can totally store the MCTS search on a memory mapped file. When it fits in ram its fast - when not it will get cached with a smart - hardware backed - policy and you dont need to implement anything.
Bonus: Memory mapped files can be accessed from the GPU too. (but I dont want to spoil this point by explaining further)

The "most wins" can be a red herring. https://en.wikipedia.org/wiki/Survivorship_bias
Since the pure search implementation cannot see a forced line - could be that 999/1000 moves are winning but that does not matter when the only other move is forcing and your oppenent finds it.

You still need a smart agent at the leafes of your search like hgm correctly asserted here: http://www.talkchess.com/forum3/viewtop ... =7&t=80300

Also a policy like ucb1 does optimally solve the problem of "This move looks very promising, when it is the best time to search other unpromising moves too?"

MCTS still needs a smart agent at the leaves. A NN alone wont cut it. What is needed for a new type of engine is MCTS + computationally optimal lightweight engine that can run in parallel at the rollout phase. Ideally an engine that is good enough to keep a winning position winning against the strongest current gen engine with not too much material.
Maybe an engine that is a pure NN like giraffe with an eval network + policy network that still walks the alphabeta tree.
This is the predecessor of Alphazero - an assortment of new ideas that sidestepped all common ideas at that time (2015) https://github.com/ianfab/Giraffe

I am fond of NNs because they can be evaluated very quickly if implemented in harware (fast GEMM)
Different networks looking for long_term, short_term moves may also help.