Minimax issues

[edre]

Hello, and thanks for trying out my minimax library! You're the third one including me so please let me know how it can be improved :)

I see a couple of issues with how your game is implementing the interface:

• The out of bounds error when enabling countermoves is because you are generating moves with a table_index greater than max_table_index. I could probably have a clearer error message here.
• You're mutating the game state in apply, but you haven't implemented undo. This will make all of the algorithms fundamentally broken.

[thomasmarsh]

Hello! It is wonderful to hear from you: I was thinking of reaching out but didn't want to bother you before I had dug in a little deeper. Thanks so much for your hard work on minimax-rs!

I have actually found a number of small issues with minimax-rs, some bugs (e.g., setting max_depth to 255 results in an infinite loop), some just questions or my misunderstandings and misuse. I'd be happy to contribute PRs for documentation or code fixes, but I haven't focused on fixing the minimax stuff yet. (I also thought I might need to confer with you to understand things better.)

Regarding the bounds errors, I wonder if this might be a bug in minimax-rs. At first I was returning Some(state.clone()) from the Game::apply() and I noticed it was not leveraging the tables at all. That changed when I saw how Nokamute was using mutation in place. So I switch to that approach (but failed to implement undo), and I saw much different behavior. I expected the behavior would be the same based on the comment that the implementation supports either approach. I didn't look deeper, but had the impression that the minimax was definitely doing odd stuff.

I just tried switching it back to returning a value, but still get an index out of range error, with countermoves on. So, at least that is consistent. I'm happy to play around with it some more, but must confess I'm just doing a little bit of guesswork at the moment on picking the right options. I'll try adding history+undo and see if that helps search, but it's not the approach I wanted due to game state size. Thanks again!

[edre]

Your game state seems very small so I agree you should be returning a new state instead of mutate and undo. Then you can omit the move history. The index out of bounds should be fixable by using a larger max_table_size. If you're not entirely sure, setting it to u16::max is perfectly reasonable.

Your game has a huge branching factor so I suspect you may need to use MCTS. No one has really tried to make a good engine with minimax-rs's MCTS, so I'm open to improvements. It does have multithreading and MCTS-Solver built in, so the basics are there.

[thomasmarsh]

I agree, the branch factor is too high. I actually started with MCTS, but know that it is very poor without some domain knowledge.

For MCTS, I think some improvements are possible. I was just reading Monte Carlo Tree Search: a review of recent modifications and applications. I didn't see much relevant new stuff from last I looked at MCTS, but I was reminded of older techniques.

I don't think you implement AMAF/RAVE. I also heard of "LastGoodReply", "DecisiveMove" which I think were popular in older go engines. They are mentioned in this article along with poolRAVE.

I think MCTS-Solve might be an alternative to RAVE - I don't know them except for vague impressions. I did once chat with Cameron Browne in 2013 and he mentioned RAVE as being unusually effective in most games where it works (and, looking back, notably didn't mention TDS-Solver..). Maybe you have some insight here? Or maybe I need to finally sit down and figure out RAVE. I think it might benefit from transposition tables.

It would be nice to have some more dropout options and pruning techniques for MCTS. I could perhaps use my game to drive some of those requirements.

I saw an issue in minimax: I saw an illegal move being played. There is only one of a certain piece, but it was played twice. This is was something I expected when mutating the state but not providing undo. Now I saw it happen when I first cloned the state and then returned the mutated copy. So, not sure what that was about.

Otherwise, I observed that minimax is choosing the first move every time. I believe this is a common artifact (which moves are not otherwise shuffled) when all moves seem to be of equal value. More work on an evaluation function would help in that case. This game in particular has a cold start until mid-game when captures start occurring, so unless you can reach deep into the game tree, all moves should look roughly equivalent.

[edre]

My parallel minimax implementation has an intentionally racy table for performance reasons (something like a 50-80% gain vs a per-entry mutex). I saw that Stockfish's implementation was way more racy than mine so figured it was fine in practice. You seem to be using an especially small translation table, so the races may be more likely there. Minimax should probably trust the moves in the table less to prevent returning invalid moves (instead making invalid calculations sometimes).

I did a lot more research for minimax than MCTS, and I had to look up what RAVE was. Something about storing information in transition tables across branches. Either it would need a completely different thread sharing model of state, or just separate tables per thread. Feel free to experiment.

Your game could probably get multiple benefits just from implementing biasing in the rollouts. For one, you could check for better moves first, and maybe bigger pieces first with a higher probability, and in most cases skip generating a majority of moves.