Hi, I'm planning to create a generic board game engine for my scripting class. Basically, the engine will be coded in c++, and the rules will be in a high level scripting language such as python or lua. I've just started planning the project out, I think I know how I would go about it for the most part as long as they are all grid based games such as chess/checkers etc, but I'm unsure on how I would make it completely generic so that more complex games could be added (this is not a requirement, but I would like to pursue it) If anyone has any experience with a project like this or some ideas, let me know. I hope to get started on this by the end of the week. Thanks.

I have never coded something like this, but I have thought about it, so perhaps some of my ideas will prove useful. The class of games that I was trying to cover is probably much larger than what you are thinking about: full-information games (including games with randomness and games with more than two players).

A game is described by:
* The number of players taking place.
* A method to generate a list of available moves for each player (for many games this will only present real choices for one player at a time, but some games require making decisions simultaneously).
* A method to know if the game is over, and in that case how happy each player will be with the result (i.e., the utility of the result for each player, which is just one number per player).
* A method to save and restore the current state of the game.

Although this interface fully describes the game in principle, in practice you'll need your engine to have access to more information. Exactly what information depends on the algorithm you'll use to play.

My personal choice of algorithm would be some sort of Monte Carlo Tree Search (MCTS). You can get something working using exactly the interface to the game described above, but your program may not play very well. My thoughts were that you can extend the interface by providing a signature for each available move, which would simply be a sequence of 64-bit numbers (hash keys) that will allow you to compare two moves and get an idea of how similar they are.

For instance, in go, you could form a signature for a move by computing a hash value for the 3x3 pattern around the point, a hash key for a 7x7 pattern and a hash key for the entire board together with the move. This way the MCTS algorithm can accumulate statistics of how often a move gave good results. If the exact position hasn't happened before, you can still use data from previous moves that had the same 7x7 pattern, and if that hasn't happened yet either, you can use data from previous moves that had the same 3x3 pattern. Exactly how to combine stats on the different classifications of moves is a tricky thing.

If you just want to limit yourself to deterministic full-information two-player zero-sum games (still a large class: chess, checkers, connect 4, go, arimaa...), you should probably add an evaluation function as part of the game description (so you can use some version of MiniMax search), and perhaps a move generator that only generates moves that have the potential to change the score a lot (so you can implement Quiescence Search).

Well, that was several months of thoughts condensed into a few paragraphs, so it might be too much to process. I assure you that it all makes some sense, even if my explanation isn't great. If this sounds like the kind of approach you are interested in pursuing, do your homework (i.e., get informed about alpha-beta and MCTS) and feel free to ask for details.

Quote:Original post by alvaro
I have never coded something like this, but I have thought about it, so perhaps some of my ideas will prove useful. The class of games that I was trying to cover is probably much larger than what you are thinking about: full-information games (including games with randomness and games with more than two players).

A game is described by:
* The number of players taking place.
* A method to generate a list of available moves for each player (for many games this will only present real choices for one player at a time, but some games require making decisions simultaneously).
* A method to know if the game is over, and in that case how happy each player will be with the result (i.e., the utility of the result for each player, which is just one number per player).
* A method to save and restore the current state of the game.

Although this interface fully describes the game in principle, in practice you'll need your engine to have access to more information. Exactly what information depends on the algorithm you'll use to play.

My personal choice of algorithm would be some sort of Monte Carlo Tree Search (MCTS). You can get something working using exactly the interface to the game described above, but your program may not play very well. My thoughts were that you can extend the interface by providing a signature for each available move, which would simply be a sequence of 64-bit numbers (hash keys) that will allow you to compare two moves and get an idea of how similar they are.

For instance, in go, you could form a signature for a move by computing a hash value for the 3x3 pattern around the point, a hash key for a 7x7 pattern and a hash key for the entire board together with the move. This way the MCTS algorithm can accumulate statistics of how often a move gave good results. If the exact position hasn't happened before, you can still use data from previous moves that had the same 7x7 pattern, and if that hasn't happened yet either, you can use data from previous moves that had the same 3x3 pattern. Exactly how to combine stats on the different classifications of moves is a tricky thing.

If you just want to limit yourself to deterministic full-information two-player zero-sum games (still a large class: chess, checkers, connect 4, go, arimaa...), you should probably add an evaluation function as part of the game description (so you can use some version of MiniMax search), and perhaps a move generator that only generates moves that have the potential to change the score a lot (so you can implement Quiescence Search).

Well, that was several months of thoughts condensed into a few paragraphs, so it might be too much to process. I assure you that it all makes some sense, even if my explanation isn't great. If this sounds like the kind of approach you are interested in pursuing, do your homework (i.e., get informed about alpha-beta and MCTS) and feel free to ask for details.

Firstly, thank you for the great information. I wasn't expecting nearly as much.
I've been researching the various methods you described, most of them seem specifically designed for what I'm trying to achieve.

I would definitely want to go the MCTS way since it sounds interesting and is a relatively new algorithm. My original idea was limited to deterministic two player games such as chess, checkers etc. I was planning to use a minimax game tree like you suggested, but I believe that other board game types aren't that far off.

I'm still debating which version to pursue. Thanks for the great information, I'll keep you informed once I decide.