[Design Discussion] Minimax

[huiwang]

@tyrcho I tried with a new design which is a bit different from your negamax but I'm not sure it's a good one. My design guide is to separate problem representation from minimax algo as much as possible. As a result, I've taken the following decisions

1. Representation should distinguish active/terminal nodes. An active node should have at least one edge. A terminal node returns an empty edge list.
2. Representation should handle player switch during branching(childOf()) operation. This is hidden from minimax algo.

What do you think of this design?

[huiwang]

@tyrcho I find the discussion really interesting. Please keep it rolling.

The suggested design aims to reduce as much as possible the set of constraints over a game's model. That being said, I think it would be possible to relax the two following contraints

• nextPlayer method in GameState trait
• outcome method in GameRules trait

Relaxing these two contrains means that

• validMoves should return an empty set if the game is in a terminal state.
• heuristic function should take into account game-over situations
• the model is responsible to expand the game tree in a player-switching style

[tyrcho]

@huiwang

I'm not sure how we can relax the nextPlayer constraint ... it seems quite convenient when you manipulate a GameState to know who plays next (as a Judge, to ask the correct AI or human player its move). Especially when we'll want to dive into more than 2p, or to model hidden information as an "environment" player. This would have been useful in Code4Life since the samples order is hidden.

For outcome, it is possible with the heuristic function for sure. But I'm not sure the usability of GameRules would be better. There is no correlation with an empty set of moves, and who won (chess, go ...). It seems to me that declaring the winner is part of the GameRules.

[tyrcho]

@huiwang I think the best way to "test" a new design is from the point of view of the developper writing code using our "framework". Would you share here maybe just this code without any real implementation yet ?

You could showcase :

• implementing GameRules for a trivial game like TicTacToe
• finding best move reusing an algo like MCTS (which does not require anything more than the rules)
• getting a Referee to get the steps and result of a game between 2 variants of the AI (like different time constraints)

Basically this would mean rewriting something similar to GomokuDemo with the new API (without the implentations existing yet, just to discuss the design).

[tyrcho]

@Wei-1 , @trobert if you have the time, I'd like your opinion on this design discussion too ...

[huiwang]

@tyrcho

I see more clearly why you separate game rules from heuristics. A game rule is objective. That's what defines a game. Heuristics are subjective. Different players may have different strategies to evaluate the game.

[huiwang]

Now regarding the nextPlayer constraint.

By saying relax, I'm not saying that we can't use nextPlayer to tell who is to play for the next round. What I want to say is that we can leave the responsability on how to choose next player to the game rules.

Regarding outcome, I do agree that it's important for a judge system to declare the winner when a game ends. However, from the point view of a minimax algorithm, it needs to know how the tree expands and how a tree node is evaluated.

That's why I called that trait MinimaxRepresentation. It covers the minimum information that a game should provide in order to be solved by Minimax.

[huiwang]

I definitely agree that a client has the final word on the design quality. But I don't understand your question

Would you share here maybe just this code without any real implementation yet ?

Do you want me to show the design with real impl or without? :)

[tyrcho]

@huiwang OK, I got it about the nextPlayer. You're right, this can be handled by the rules. On the other we have to encode somewhere in the GameState this information ... so why not expose it in the trait ? I'm not sure it makes a big difference to be honest.

Do you want me to show the design with real impl or without? :)

without any impl ! it's enough to see the position of the client.

[huiwang]

For example, in the tic-tac-toe game, i don't need store a field named nextPlayer to check who is to play for the next round. I just need to compare the number of X and O to know the next player.

This may sound stupid but it shows that it's a implementation detail that can be decided by the game.

[tyrcho]

@huiwang you're right ... But I'm still not 100% convinced. ^^

From the client side, I think I prefer to call state.nextPlayer rather than rules.nextPlayer(state) who will 99% of the time call state.nextPlayer in its impl.

It just feels awkward having a GameState which cannot tell who plays next.

Still "thinking aloud", maybe it means that GameState and GameRules cannot be easily decoupled.

Looking for references over the net ...

• https://stackoverflow.com/questions/361002/any-patterns-for-modelling-board-games
• https://en.wikipedia.org/wiki/Game_Description_Language

the GDL spec is probably a good starting point.

Still thinking (taking about 30 min to write this comment).

A positive point in removing this method from GameState trait is we can remove the trait entirely.

Also the same class can represent the same state for different game rules. Eg a grid can be used to play Tic Tac Toe (play until it's filled) or 3 men morris (play 3 stones then move them). Or a chess board can be used to play a chess variant. So the dependency is really from rules to board.

Hmm another point. When we ask a player (ai) its move, he needs to know which sides he plays (so the player ai can be stateless). It seems to me much easier if this information is encoded in the board state. player.nextMove(gameState).

It might be just a gut feeling, but removing the nextPlayer member from GameState just worries me ...

[huiwang]

@tyrcho

I'd like to make sure that we are well aligned on the design goal.

For me, we are designing a contract between a problem and the minimax algo in order that the problem can be solved by the minimax. How to model a game is out of our design scope. We can model the game in GDL. Others can model the same game in other language.

Do you agree?

[tyrcho]

@huiwang well, my main goal was to design how to find a good move in a turn based game, and to provide generic implementations of MCTS / alphabeta for this purpose. For this I had in mind to specify 2 contracts :

• what is a turn based game
• what is a ai which finds the next best move

Then the client can implement its game, select an ai (maybe he'll need to implement an extra heuristic function) and he gets a robot which can play the game.

It seems our objectives were not the same ...

[huiwang]

@tyrcho Consequently, it's not very astonishing that we can't converge. From the very beginning, my head was already filled with trees, nodes, edges.

But this is not a problem. I'm ready to stick with your current implementation (differences are tiny). Let's collect feedbacks from real-world contests and other developers using these algos. We'll improve the design based on these feedbacks.