I am trying to create a 2-player Atlas game bot along the lines of chess bots by using the Minimax algorithm. I am using a database of just countries and capitals to induce strategy in the game. There are 2 ways the game could end :
- The player doesn't know the place name with that starting letter
- There are no places left with that starting letter
The first way could be implemented by placing a timer. The second way is quite interesting, we can create a decision tree where each node represents the available moves for each player.
But a significant problem is unlike chess, where the player and opponent both have their resources, and the evaluation function is calculated using those resources, after which the algorithm tries to maximize the player's route and minimize the opponent's. Here, both players have the same set from which they have to choose, and I don't think minimax can work well here. Will negamax work or is genetic algorithms the only option or maybe I do not need these fancy algorithms?
Assuming that a word can only be used once in the whole game and therefore that every game eventually ends, you can use the minimax algorithm. The fact that the two opponents share the same material does not matter, what is important is the move they can do when it's their turn.
However, creating an evaluation function isn't trivial in this case so you might have to explore every possible continuation until the end. This is because if you get to a point in a game where there is a winner, then doing the evaluation is quite simple (obviously). If you can do that, then you will have solved the game.
Unfortunately, this solution might be too complex (in memory and time). What you could try if thats the case is to implement the most basic form of evaluation and say that if there is no winner in a position, then there is a 0.5 chance for each of the players to win. If your goal is to beat a mere human at this game, I think it would be enough since they wouldn't be able to think more than 3 moves ahead anyway.