I decided that I want to write the game Stratego, and iv got the basic system working and two (human) players can play it, but I want to add an AI player. Since I figure that (conceptually) stratego is similar to chess in that it requires carefull planing to win, Im wondering what types of AI algorithms are commonly used for chess or any other type of complex game. Iv had some experience with neural nets, but I highly dought that they would be usefull in this senario. Im looking for something that I can use to make a smart player, but I dont want to have to explicitly tell it a thousand ways how to win, rather I want to it continuously play itself and learn how to win. I assume this is the general strategy used by chess programs... Any thoughts?

I doubt any learning has been used for commercial chess AI, unsupervised learning even less! Most of the time, it seems to be a variation on minimax/alpha-beta, with an oppening playbook.

"What AI algo's are commonly used for chess?"

Uh... that would be the 'chess tree search'. You will find a multitude of links both on here and the web in general. It is probably one of the more documented algorithms. It can also apply to any turn-based, zero sum, perfect knowledge game - whether that be tic-tac-toe or stratego. Optimum? Maybe not... but it's a start.

The Minimax algorithm is the fundament of most Chess playing programs. Since the algorithm itself doesn't vary much, you can pretty much copy it verbatim into your programming language. After that, you "only" need to find out how to evaluate positions (in a comparable way). If you want, I can provide you a C++ framework which implements a generic Minimax algorithm.

I dont know about Stratego, but in chest, having an oppening playbook is very important. That is because there is only a few "good" ways of begining a chest match, and that its at the start that evaluating the board is most difficult.

Most commercial chess games have certain chess masters that you can pick from, so I would assume the AI is a simple playbook developed from their playing style. I would recommend getting a number of these "playbooks" and randomly selecting them to mix up the player.

Stratego, unlike chess, does not give each player full knowledge of the state space. Therefore, the algorithms which are useful for chess are generally not useful for Stratego.

Thanks for all the input

>> Stratego, unlike chess, does not give each player full knowledge of the state space. Therefore, the algorithms which are useful for chess are generally not useful for Stratego.

I think I see what you are saying...since the player positions his pieces where he wants, theres really no reasonable way to predetermine any "plays"

I looked up the minmax algorithm and it seems like it might be usefull, but wikipedia only tells me so much...Ill have to do more research on it.

I looked up "chess tree search" but wasnt able to find much on it. At the moment the minmax looks a bit more promising since I can see now that stratego doesnt give the player full knoledge of all the pieces, it involves alot of guessing and intuition

At any rate, minimax is one of those basic algorithms that anyone in CS should study.

Quote: Original post by Sneftel
Stratego, unlike chess, does not give each player full knowledge of the state space. Therefore, the algorithms which are useful for chess are generally not useful for Stratego.

Oh yeah. Oops. So much for minimax.