What sources have you provided? BeepKillBeep provided dozens of them, but I must have missed any you gave.
No you don’t. First you have to ask “Can the AI win in this game?”. Only once that question is answered, and only if the answer is no, can you ask why not.
He won’t understand this. He will confuse “Can” with “Does”.
If you understand the game, yes the AI can win. If you understand what I wrote, anyone or an AI with possible training can upset a master level opponent.
However in a tournament style or best of series of games the AI fails to beat the better human level opponents. That is the history. Why is the question?
Oh, why hasn’t the AI beaten the humans. Yeah, we’ve already answered that question: Because there’s been very little effort put into Stratego AIs.
The facts are there were several AI’s that tried and failed. AI did not approach world class level in this game as early as 2011.
How do you know there was little effort put into them? Please explain with details?
Maybe it’s not just a good game for AI’s.
Here’s how I know, because BKB answered this question already:
In case anybody is curious. Here is an estimation on the number of papers about particular games and AI. These estimates are rough, but are probably in the right order, more or less. I wanted to find ones that I knew would be pretty high, like Go and Chess, and the tried to find ones that I thought might be pretty low. So here’s what it looks like to me, and granted this is only an interpretation, if a game has a long classical history it is pretty popular to examine. If a game is a classic Hasbro/Milton Bradley/Etc. game, not so much. I wonder if maybe there’s a fear that looking at games such as this might appear to be lacking seriousness? As in you can go to a conference and say “I’m working on chess” and people will say “Oh chess, yes yes, good classical game” but if you got to a conference and say “I’m working on Battleship” people will say “Really? The kids game?” Again, just a guess, I honestly don’t know but it is hard to not to see that such games are all very low on the list.
Also, clearly the 1/10000th is an error, I meant 1/1000th (or I did the math wrong, which is sadly very possible), not that the factor of 10 makes that much difference to the conclusion.
AI Papers on Go: ~200000
AI Papers on Chess: ~70000
AI Papers on Poker: ~13000
AI Papers on Checkers: ~6000
AI Papers on Chinese Checkers: ~4000
AI Papers on Tic Tac Toe: ~3000 (This is certainly inflated by comparisons to tic tac toe AIs)
AI Papers on Backgammon: ~2000
AI Papers on Scrabble: ~1500
AI Papers on Jungle Checkers: ~1500
AI Papers on Kriegspiel: ~600 (This surprised me, I expected this to be higher)
AI Papers on Wumpus: ~400 (Certainly inflated as it is a classic logic problem for AI)
AI Papers on Stratego: ~150
AI Papers on Settlers of Catan: ~150
AI Papers on Connect Four: ~50
AI Papers on Battleship: ~50
AI Papers on Ticket to Ride: <10
None for Reversi / Othello? It seems like a likely target. Back in college, I wrote a Reversi AI that played a reasonably intelligent (well, not blatantly stupid) game in Lisp.
And I tried and failed to make a Connect 4 game that can beat me. Which certainly doesn’t mean anything, because other people have tried harder than me, and succeeded.
Or to look at it another way: See all those papers on Go? Computer programmers have clearly been trying very, very hard indeed to make Go AIs, and it wasn’t until this year that they succeeded. If we’d had this thread last year, you could very easily have said that it was impossible for a computer to play Go well, because people have tried so hard at it and still failed (in fact, the best Go AIs of 2016 were even worse than the best Stratego AIs are). And if you had said that, you would have been wrong, because the best Go player in the world is now a computer.
Oh Lisp. I had a lot of fun working with Lisp (I’m clearly lying, nobody ever had fun working with Lisp).
And since you asked…
AI papers on Othello/Reversi: ~6000
I’m trying to find some chess software that works well for my needs. I’d like to find one that has intuitive computer-strength settings. I had already started a thread about this here when I noticed this thread and thought I’d ask you guys.
Yes, I guess I’m sort of shamelessly trying to direct people over to my own thread but I could really use the help. Thanks!
Actually, I had fun working with it.
Of course I’ve never had any real world use for it since college but it was completely different from typical procedural languages and I enjoyed the way it made me approach problems in a very different way.
It probably wasn’t the best language to use for the alpha beta minimax algorithm that was the basis for that introductory AI class. It was the first time that class was offered at that school and I think the professor chose Lisp because it was being billed at the time as an AI language.
That was my first game AI, too. I coded mine in Pascal; I actually misunderstood the assignment, which was to code up a Reversi game that allowed two human players to play, but instead I wrote a simple AI. Still good enough to beat me most of the time. Nothing special; it just played against itself several moves into the future and picked the move that gave the highest board score. Still enough to beat me most of the time.
I learnt it as well in an Introduction to AI course. Lisp was cool but I don’t think I have any fond memories of it. I remember the final assignment was this self-modifying code thing that made me weep. 
It is fun though sometimes to think about the journey. With an 20+ years of additional experience, it’d probably be easy now.
Eeeeeeeeeeeeeh, I’m working on Starcraft now (though it’s not to make the best AI, Starcraft is being used as a testbed for other stuff), and… I mean, Starcraft AIs work. They can beat people, and very occasionally beat good players but I wouldn’t say they “beat humans” the way Chess or Go AIs do. Honestly, most of their skill in Starcraft is mechanical – they simply have a higher APM than any human player can reasonably expect to have. Their tactical decisionmaking leaves a lot to be desired.
And, like, that’s a perfectly valid way to win! We can’t expect AIs to operate the same way humans do! If your micro game is stronger than your tactical game, then that’s fine! However, there’s a loooooong way to go as far as making a computer reasonably be able to play a full game. However, it won’t be long until a computer can pretty much win little unit skirmishes with no base management almost 100% of the time, even if the map is only partially observable.
Edit: Also, expect papers and progress on Starcraft 2 to explode soon because Deep Mind is interested and partnered with Blizzard to make an API that makes it easy to use Starcraft 2 for AI research.
Lisp has the interesting property that Lisp code has the same representation as any other Lisp data structure. This makes it easy and natural for a program to do things like examine and modify itself; see for instance www.genetic-programming.com.
It is also true that Lisp has the benefit of longevity going for it, which is why it is associated with AI the same way Fortran is associated with numerical analysis.
Honestly, I think the idea that Lisp is an AI language is a bit outdated. Everything is in Python now, and then everything else is smattered about through C++ (for performance) or Java (more businessy stuff usually). Probably a couple Lua users here and there too because of Torch, but PyTorch exists for a reason. The only academic/researchy people with much interest in Lisp anymore are the Programming Languages folks, and they’ve mostly decided to focus on languages with dependent types like ML or Coque; or Haskell. (Unless they’re working to make static analysis tools for software engineers in which case it pretty naturally follows language popularity).
Of course. That was the thinking when I was in college, but it really wasn’t appropriate for a game playing AI like I wrote, if for no other reason than that it was an interpreted language and therefore too slow on the PCs of the time.
I had to do some questionable trimming of the search tree at every level in order to get beyond 1 or 2 levels in a reasonable amount of time. This negatively impacted its playing ability.
A somewhat recent paper on Stratego AI using convolutional neural networks.
CNNs are the hot thing these days in AI. This guy achieved a moderately successful player, though not a great one. But it’s also just one dude playing around with it and not, say, a research team at Google.
The paper mentions that it handles only first-order inferences, which is to say those things which it knows for sure about the opponent. It apparently cannot deduce facts such as “I know that piece X isn’t an A, because piece Y is already known to be an A” and the like. But of course there’s nothing about computers that prevents this kind of inference; in fact a computer can keep a much more detailed probability inference model than a human.
If Wikipedia is to be believed, one major problem is that there’s very little recording of games. Whereas with chess or Go, there are thousands upon thousands of games available as a training set, that’s not the case with Stratego. Training neural nets requires a huge input database to be effective.
He used a pretty basic CNN and only made moderate improvements to the layers. In fact, his general approach is fairly naive. For instance, his first strategy is to directly predict a move, and his second is to predict the probability of a given move winning.
The former is what the paper he cited did, which is a paper with some influence (77 citations), and is a reasonable approach, but that paper is from December 2014 which is oooooold by now in AI time (granted I don’t know when this student wrote that report). The second strategy isn’t really suited to the network, and directly predicting win probabilities isn’t typically done.
You’d probably do much better with Trust Region Policy Optimization for direct move prediction, or something like DQN for strategy 2 (Q-values and reinforcement learning is better than trying to directly predict what a random policy rollout will accomplish). (For reference, DQN with MCTS is what was used for Go). The new hotness is A3C which pretty much replaces DQN and directly predicts moves AND assigns a value to the moves, but that’s really recent.
The training strategy is also really basic, and honestly the training strategy is probably more important than the network. The Go paper used a huge corpus of expert games, yes, but also a lot of games between itself once it got “bootstrapped”.
You could probably achieve pretty reasonable results just by copying the Go DQN paper with Strategy (and, of course, Google-scale architecture) given how well this student did with a pretty naive approach.
Another strategy that could be interesting is using a CNN to directly predict the fully observable game board from the partially observable information, and then feed that output into a predictor, but that’s kinda open researchy and it’s possible the deep net is already sort of doing that internally (building an autoencoder might help? not sure). Another potential improvement could be using a short history of moves instead of just the current game state since that may give you more information about the hidden variables.
TL;DR version - that paper could be improved upon tons, very quickly, if anyone really cared to do it.