One billion random games

[Daniel Shawul]

Interesting. What I had in mind was to make the probabilities proportional to (1+f*victimValue)/pieceValue. This does seem to avoid the problem you mention; QxP captures could be discouraged, while PxQ captures would be strongly enhanced.

Mind you, I am not claiming that you could ever play good Chess with such an algorithm. I am just curious if one could create such a simple strategy that was at least able to exploit a material advantage (making the game unstable, diverging away from equality rather than converging towards it).

Intuitively I would think that paranoia is good, because pieces could be defended and empty squares could be attacked. OTOH, QxQ should probably be strongly encouraged, because the Queen could have been unprotected. So f=2 seems a reasonable value, which would prefer QxQ by a factor 19/9=2.11 over a Pawn push, while PxQ would have relative probability 19, and QxP 3/9=0.33.

I think I used MVV/LVA for ordering captures. We can also use other good heuristic to sort captures within themselves.
What was problematic was captures weights relative to non-captures! If the capture is forced, that move should get all the weight
despite 40 other non-capture moves possible. If it gets equal simulations (1/40 of them), it will fail.
In checkers this is naturally taken care of by the rules of the game, and playing only among the captures converges fast on the best one.
The "standing pat" is a big problem since it requires a SEE or qsearch. There are also other good tactical moves even in non-captures.
Pins , forks and checks are some of them. The best result I got with MC was in endgames but still had problems with those tactical moves...
I think the best strategy is to select among a reduced pool of good moves instead of pinning down the best move statically, as that is less error prone.

IIRC I also tried using hand-written tactic detection for upto 5-piece endgames to predict results of the game and help compression..
It worked to some extent so then I tried SEE and shallow searches but it was too slow and I couldn't finish compressing some of the big files.

I think that running very fast games with regular search is a much better alternative with less hassle (as Rybka does). We will not be able to produce games as fast as a MC engine does, but then we will have a much better quality of games.

[Daniel Shawul]

Some time ago I have tried to reformulate Monte Carlo for chess as "take an average of multiple searches with large random factor in eval function", which is probably about the slowest and the most knowledge-heavy simulation strategy one can design. The result was a very funny failure: engine estimated mobility over material, needed a special incentive at the root to castle at all, and reached at most 1200 Elo

Did you do a regular search with random eval ? If that is the case , yes it will start to prefer moves leading to better mobility. But you have to make sure all leafs are at the same ply though. But here we are talking about a MC engine where you select exactly one move, and for chess it is very difficult because of too many tactical moves which MC is badly suited.

I also have a very basic and bad engine playing the game of go with shallow, selective global alpha-beta. 10-12 moves are selected by Monte Carlo simulations and leaves are evaluated in the same manner. From time to time I add some rule preventing certain kind of a bad move, but even on a 9x9 board chances to pick something horrible are unfanthomable. Alpha-beta helps pure Monte Carlo / AMAF a lot, but the resulting program is still a sore loser. I came to admire go programmers a lot after trying that.

Still, it would be a great and instructive achievement to build a 1800-ish Monte Carlo chess program, but I have no clue how it can be done.

I think getting 1800elo chess is very difficult with MC only. Advantage of MC is that it brings distant information, but we are having serious problems looking short distances. Tactical issues should be solved by some kind of heuristic first. I tried a MC which only extends up to ply 30 but it still failed miserably due to this short tactical weaknesses.

[PK]

For chess search I used plain alpha-beta with iterative deepening of simulated games (but no transposition table, no null move), for eval - material, some stuff I forgot to disable (not much of that, as I used the codebase of Sungorus, because of its speed and simplicity) and random factor of 200-300 centipawns. At its best, "Monty" plays like that (as white, at blitz time control).

1. d4 Nf6 2. e3 g6 3. Nc3 Bg7 4. Nf3 c5 5. dxc5 Qa5 6. Nd2 Qxc5 7. Nb3 Qc7 8.Nb5 Qd8 9. Bd3 a6 10. Nc3 O-O 11. O-O b5 12. a4 b4 13. Ne2 Bb7 14. Bd2 a5 15. Ng3 Qb6 16. e4 d6 17. Be3 Qc6 18. Qd2 Nbd7 19. Bb5 Qc7 20. Bxd7 Qxd7 21. Bb6 Nxe4 22. Nxe4 Bxe4 23. Nxa5 Rfb8 24. Qxb4 d5 25. c4 Bxb2 26. Qxb2 Rxa5 27. Bxa5 Rxb2 28. cxd5 Qxd5 29. Bc3 Rc2 30. Rfd1 Rxc3 31. Rxd5 Bxd5 32. a5 Rc7 and no need to continue, 0-1

At its worst, it plays something like Rh1-f1-g1 instead of castling and never recovers or sacks a piece for a pawn and a couple of checks.

[S.Taylor]

One billion random games generated with a single thread on a 3.2 GHz Intel Core i3:

Code: Select all

[] rgstat 1000000000
Summary:
  Checkmate 153,023,351 (0.153023)
  FiftyMoves 199,868,185 (0.199868)
  Insufficient 560,510,846 (0.560511)
  Repetition 25,427,172 (0.0254272)
  Stalemate 61,170,446 (0.0611704)
Count: 1,000,000,000   Elapsed: 159960  (6251.57 Hz / 0.00015996 s)

That must be interesting! I'd like to study each one of them in great depth, i'm sure it would provide me with plenty mental stimulation and chess experience!

[Don]

I do not trust random games for chess because of this "capture problem". For checkers , captures are forced and plain monte carlo works very well, but for chess a player has an option not to capture. I have tried biased move selection for captures (both more/less frequency), still with very bad results. Maybe SEE would help but I never tried as that is too slow for MC. A capture may be good or bad and that takes some plies to discover. So plain biasing without using a complicated heuristic like SEE is doomed to fail. Chess is full of tactics (captures at each ply) and a MC searcher ,even though it goes deep, returns crap results missing 2-ply tactics. First, It moved its queen for the opponent pawn to capture it in the next ply. To solve that I tried giving larger probabilities to captures but then it started capturing defened pawns with its queen. So clearly I needed a good tactical searcher for the monte-carlo part and that is very _expensive_. Without that the statistics derived from it about who is winning is not dependable. To prove this point we can try a position where one side is up by a rook. I will not be surpized if the result is still 50-50.

I spent a small amount of time looking at MCTS for chess and as expected found it extremely unreliable. It's ok if it's far from perfect as the TS in MCTS should figure things out but the MC part should provide an evaluation function that is at least crude but it is not even that good!

Tactics just overwhelm chess, so MC seems doomed from the start. You can try doing 1 ply searches or applying see() but this slows MC to a crawl. Also, MC depends on good randomness and it's hard to produce that without being pretty arbitrary. Too many positions have only 1 or 2 reasonable responses for tactical or positional reasons and that is a killer.

Maybe there is a clever way to do this, but I don't know what it is. It amazes me that it works so well in Go.

[Isaac]

*) How are the wins distributed over white wins and black wins? Does white have an advantage even in the random limit, and if so, how big is it?

I can answer this without the need to check the results.
The most probable games are the shortest ones. That's because the probability to play a particular game is the multiplication of the probabilities to play each move. So, the most probable games are the checkmates in 2 moves (4 half moves). There are 8 such games, where black always wins. Out of these 8 games, 2 are the most probable (and equiprobable). Namely 1.f3 e5 (or e6) 2.g4 Qh4#. Each with probability 1/20 x 1/20 x 1/19 x 1/30 ≈ 4.4e-6. That's one order of magnitude greater than any game lasting 3 moves. And there again, I suspect black still has the edge for 3 moves games, because white can uncover its king while black can develop its queen faster than the other way around. This offers more chances for black to checkmate than the other way around. This advantage gets reduced for longer games.

So we can make a quick and dirty estimate on the bias/advantage black has over white, for totally random games where each move is chosen uniformly randomly. It's about 8*4e-6 ≈ 3e-5.