Game of the General AI Implementation

Are you familiar with Chess AI, and standard minimax approaches? It is more complex when you have hidden information, as in this game, but an AI can often do well by using estimated information (e.g. based on a heuristic) instead of the known values.

(Also, this is the wrong forum for technical questions, so I'll move it to a more relevant place.)

I haven't written AI for this game, but the last time I thought about it I could see a way to implement decent AI using MCTS. The hidden information part makes it trickier, but I think the difficulties are surmountable. I'll be happy to discuss some details, but I would like to know what you have thought of so far.

Now that we have DeepMind's AlphaZero approach, it can probably be applied here as well, but I have to think about it a bit, and it might take too many resources for a thesis.

I am trying to apply this one in my implementation https://medium.freecodecamp.org/simple-chess-ai-step-by-step-1d55a9266977. But im stuck in evaluation function i dont know how to evaluate the bestMove due to hidden pieces in the board. Forgive i am lack of knowledge in AI.

You can't use the traditional methods for chess AI because they only apply to full-information games. That's why I suggested Monte Carlo methods. Have you looked into that at all?

Here's my very brief recipe. The main ingredient is a "policy function". That is a [quick] function that, given a game situation, returns a probability distribution over the moves. If you had full information, you would try each of the moves available to you, run 1,000 "playouts" --where both players use the policy function to pick the next move for the rest of the game-- and pick the move with the best results. A few modifications of this very basic method would get you to Monte Carlo Tree Search (MCTS).

Since you don't have full information, you have to first "read" what the opponent may have. You can do that by generating random configurations, assigning them weights and then running the playouts from a variety of configurations. The configurations should be weighted by their probability, which can be computed as the product of the probabilities of all the moves by the opponent until this point in the game, using the policy function (this can be justified using Bayes' theorem). You also have to zero out the weight of any configuration that is incompatible with information that has been revealed already (like the identity of some pieces after they have been captured, if I remember the game correctly (sorry, I've never played)).

The tricky part is that once the game has gone on for a while and you have learned the identity of some of the opponent's pieces, the vast majority of random configurations will be incompatible with the game history. So you should generate only plausible configurations, and in doing so you should be careful not to bias the probability distribution in any way.

The fact that you will be running playouts on different configurations means that you can't reasonably accumulate statistics for future positions the way you do in MCTS, so you will probably have to use a basic scheme without tree search.

One more thing: It's possible to use a neural network to play the role of the policy function, and this might be feasible these days. If I were you, I would start with a hand-crafted policy function. Something that returns the uniform distribution over all legal moves would be a good place to start. You can then up the probability of obvious good moves. Eventually you can train a neural network to maximize the likelihood of the moves in some database of games (which could be generated with your own program playing itself) and use it as policy network.

7 hours ago, alvaro said:

Here's my very brief recipe. The main ingredient is a "policy function". That is a [quick] function that, given a game situation, returns a probability distribution over the moves. If you had full information, you would try each of the moves available to you, run 1,000 "playouts" --where both players use the policy function to pick the next move for the rest of the game-- and pick the move with the best results. A few modifications of this very basic method would get you to Monte Carlo Tree Search (MCTS).

How can i implement the probability distribution in each pieces?. How to redistribute the probability if my enemy piece has been eliminated?. Sorry i cant figure it out.

I don't understand your question.

Sorry for unclear question sir. These are all the pieces in this game. How can i get the probability of of each pieces?

You don't assign probabilities to pieces, but to moves. As I said before, you can start with a policy function that simply generates all the legal moves and assigns them equal probabilities. Later on you can refine this with some heuristics so good moves have higher probability, or you can train a neural network to produce the probability distribution for you.

The game is somewhat similar to Stratego, which is quite well studied, but quite complex. (e.g. the thread below).

If the focus of your thesis is not the AI, I'd be tempted just to stick to a simple tree search. Each AI player needs a function which can answer the question "What's the chance that Piece A defeats Piece B". This is where those probabilities come in - if you have a General, the result is 1.0 (it always wins, if I understand the rules correctly), if you have a Major, the result is 0.619 (because it can beat 61.9% of the pieces on the board), etc. That's based on the quantities of pieces at the start - you would improve the system by adjusting the probabilities as pieces are removed, and you can further improve the system by remembering things about specific pieces (so you can return 1.0 or 0.0 instead of an estimate) and weighting different attacks based on how useful they are (e.g. defeating a general is more useful than defeating a private).

Sir can you check my assumption on chance of winning of the piece
Rank private (6 pieces in total) can eliminate 2 spies and ofcourse the flag so my assumption is 9/21 chance of winning is it correct sir ?

Rank 5 star general can eliminate all pieces including for draw 5 star general except for 2 spies so my assumption is 18/21 chance of winning

sorry im not good in statistics

On 3/19/2018 at 10:38 AM, Henry Fernandez said:

Rank private (6 pieces in total) can eliminate 2 spies and ofcourse the flag so my assumption is 9/21 chance of winning is it correct sir ?

No. If there are 21 possible pieces, and 3 of them can be beaten, then the chance of winning is 3/21.

If you include the chance of a draw, then it maybe doesn't make sense to think in terms of the chance of winning - instead you might have a 'score' for each challenge, and count a draw as the average of a win and a lose. That would make the following:

Private vs 3 pieces it always wins against: 3 * 1 = 3
Private vs 12 pieces it always loses against: 12 * 0 = 0
Private vs 6 pieces it always draws against: 6 * 0.5 = 3
Total 'score' for attacking an unknown piece: 3 + 0 + 3 = 6 (out of a maximum 21, for a hypothetical piece that always win against any of the 21 opposing pieces)

Same equation for general:

General vs 19 pieces it always wins against: 19 * 1 = 19
General vs 2 pieces it always loses against: 2 * 0 = 0
General vs 1 piece it always draws against: 1 * 0.5 = 0.5
Total 'score' for attacking an unknown piece: 19 + 0 + 0.5 = 19.5 (out of a maximum 21)

The higher the score, the more beneficial it is, ignoring the value of the defeated piece or the implications for future turns.

It's easy for your AI to keep track of some information it has learned about pieces that have won a challenge, because the fact that they won restricts what piece it could be. I would keep a 15-bit integer per enemy piece, where each bit represents the possibility of being a particular rank. You can then compute the probability estimates more precisely.

3 hours ago, Kylotan said:

No. If there are 21 possible pieces, and 3 of them can be beaten, then the chance of winning is 3/21.

If you include the chance of a draw, then it maybe doesn't make sense to think in terms of the chance of winning - instead you might have a 'score' for each challenge, and count a draw as the average of a win and a lose. That would make the following:

Private vs 3 pieces it always wins against: 3 * 1 = 3
Private vs 12 pieces it always loses against: 12 * 0 = 0
Private vs 6 pieces it always draws against: 6 * 0.5 = 3
Total 'score' for attacking an unknown piece: 3 + 0 + 3 = 6 (out of a maximum 21, for a hypothetical piece that always win against any of the 21 opposing pieces)

Same equation for general:

General vs 19 pieces it always wins against: 19 * 1 = 19
General vs 2 pieces it always loses against: 2 * 0 = 0
General vs 1 piece it always draws against: 1 * 0.5 = 0.5
Total 'score' for attacking an unknown piece: 19 + 0 + 0.5 = 19.5 (out of a maximum 21)

The higher the score, the more beneficial it is, ignoring the value of the defeated piece or the implications for future turns.

Thank for clarifying my thoughts about probabilities of each pieces sir.

2 hours ago, alvaro said:

It's easy for your AI to keep track of some information it has learned about pieces that have won a challenge, because the fact that they won restricts what piece it could be. I would keep a 15-bit integer per enemy piece, where each bit represents the possibility of being a particular rank. You can then compute the probability estimates more precisely.

Thank you ill try that one

Can i apply this simple implemetation as my MCTS in my codes http://mcts.ai/code/java.html?

Please check if my steps of implementation if it is the proper way. I have problem with the speed of my playout.

e.g I have 15 possible moves

Iterate every moves
Function 1000 Playout()

if root node had already state finish the playout and update win/lose of root node

while root node is leaf iterate until it reached the leaf
select using UCT

expand the leaf node and select from expanded noded using UCT

simulate the selected node *My problem starts here its slowing down my playout

update the win/lose of the visited nodes

Select the bestNode

I implemented this using http://mcts.ai/code/java.html?

How are you using UCT for a game with hidden information? I'm not even sure this can be done, and it's certainly not straight forward.

im not sure about this id just use the snippet code from here http://mcts.ai/code/java.html?