Jump to content


Photo

Will artificial intelligence develop to the point where it can beat a human in stratego?


  • Please log in to reply
7 replies to this topic

#1 General Rascal

General Rascal

    Scout

  • Members
  • PipPipPipPip
  • 130 posts
  • Coat of arms
  • Platinum Spy

Posted 29 May 2017 - 05:07 PM

I was reading about an interview with the chess grand master, Gary Kasoarov (link).  The evolution of AI and how a computer can beat the very best chess player was discussed. It got me thinking about AI and Stratego. Of course the biggest difference between chess and stratego is role of bluffing. Does this make Stratego AI-proof?



#2 The Prof

The Prof

    Major

  • NASF Committee
  • 1,445 posts
  • Coat of arms
  • Platinum Scout

Posted 29 May 2017 - 06:02 PM

It's a very interesting topic.  It is much harder to create an effective AI for Stratego than a game where all the pieces are known, but it is not AI-proof.  Bluffing can be programmed using game theory.  If Stratego were as popular as Chess, then I believe a strong AI would have been invented by now.   As far as I know, the best work on this subject that I know of is a thesis by Vincent de Boer (link below)

 

https://www.dropbox....ncible.pdf?dl=0



#3 despy

despy

    Miner

  • Members
  • PipPipPipPipPip
  • 205 posts
  • Coat of arms
  • Platinum Marshal

Posted 29 May 2017 - 08:18 PM

Agreed - AI is very likely already at a point where it could compete with top Stratego players - there just hasn't been the interest in the community. The most relevant parallel is probably poker - AI has been superior to humans in limit hold'em for a few years now, and this year a bot successfully beat professionals at heads up no-limit as well. I suspect if a rich Stratego fan put out a $1 million prize for someone to program a bot that won a best of 7 competition against Hielco, we'd have such a bot by year-end. Anyone care to test the theory?

 

(Of course, Hielco could just write a simple program to scout the front row on the first move, and then place his flag there to win the money, but I trust that he loves the game too much to manipulate the system!)

 

 


  • Major Nelson likes this

#4 Sir_Richard

Sir_Richard

    Spy

  • Members
  • PipPip
  • 18 posts
  • Coat of arms
  • Silver Captain

Posted 29 May 2017 - 10:01 PM

There's Probe, three time Stratego computer world champion.  A strong player's comment on the program was,

"you know it never bluffs, and isn't going to come throttling down the column with a high piece."  Actually, it

should.  It should also lotto, shuffle, place its flag in he front row (but rarely) and do all those things that keep

opponents honest. It's very hard to characterize with certainty, what an advanced player does, because he may

do anything he's not supposed to do.  You never know what he's got.  Any good AI would have to be like that also.

As an inferential game, Stratego is very subtle.  Play often involves human psychological ploys, not just bluffing,

but our predictability, biases, habits, etc.  Like attacking on the dominant (usually right) side.  How would an AI

know that?  A frequent psychological play is to maintain tension in a locked position long enough that the opponent

gets frustrated, acts rashly, and blunders.  How would a machine measure frustration?  In Stratego, one often has to

dawdle, not to waste time, but to think, or to irk the opponent.    A machine should also willfully do nothing at

times.  Deterministic programming (and programmers) don't intentionally do nothing.    Sir Richard



#5 Dobby125

Dobby125

    Miner

  • Members
  • PipPipPipPipPip
  • 161 posts
  • Coat of arms
  • Silver Major

Posted 29 May 2017 - 10:41 PM

Here's some research papers on the topic I posted last year.  

 

http://forum.strateg...ng/?hl=research

 

I agree with Nortrom.  I don't see a Stratego program beating the top players on a consistent basis anytime soon.  

 

Maybe I'll email the programmers that wrote the Go program(that beat a world champ) to challenge them to write a Stratego program.

 

https://www.scientif...-the-go-master/



#6 despy

despy

    Miner

  • Members
  • PipPipPipPipPip
  • 205 posts
  • Coat of arms
  • Platinum Marshal

Posted 30 May 2017 - 12:53 AM

Stratego is very subtle.  Play often involves human psychological ploys, not just bluffing,

but our predictability, biases, habits, etc.  Like attacking on the dominant (usually right) side.  How would an AI

know that?  A frequent psychological play is to maintain tension in a locked position long enough that the opponent

gets frustrated, acts rashly, and blunders.  How would a machine measure frustration?  In Stratego, one often has to

dawdle, not to waste time, but to think, or to irk the opponent. A machine should also willfully do nothing at

times.  Deterministic programming (and programmers) don't intentionally do nothing.    Sir Richard

 

I have only a loose understanding of how the relevant algorithms work, but I think this is sort of beside the point. The algorithm doesn't need to know about dominant sides / frustration / timing / etc... And the programmer doesn't need to factor in these subtleties either - I suppose this is where machine learning is very different from traditional computer science / programming. All it needs to do is play completely randomly, and continually make adjustments until it comes up with an equilibrium strategy that cannot be beat in expectation. If an opponent usually attacks on a dominant side, that will be learned and accounted for; if chasing a piece 8 times instead of 4 (time wasting) makes a bluff more believable, that will be learned and accounted for; if waiting 7 seconds when someone moves beside a bomb makes the opponent more likely to lotto it, that will be... you know -

 

A traditional perspective of figuring out what logic you would yourself apply to create a bot will naturally result in a conclusion that this cannot be done / is extremely difficult - and it's probably true that this type of approach will never result in a bot that beats top human players in imperfect information games. But this approach isn't really in the spirit of AI - it would really just be programming human intuition - all the algorithm should need is the rules of the game, and it should be able to itself discover an 'optimal' strategy from there.

 

Anyways, I'll reiterate that I'm far from being an expert in this area, so don't ask me to prove the feasibility of this by doing it myself, but I recommend anyone interested in this look into counterfactual regret minimization -


Edited by despy, 30 May 2017 - 12:53 AM.


#7 Napoleon 1er

Napoleon 1er

    Colonel

  • Moderators
  • 1,924 posts
  • Coat of arms
  • Platinum Captain

Posted 31 May 2017 - 12:23 PM

A big difference between programming for chess or for stratego is that in chess you can program based on the effective position of the pieces on the board independently from "who" is the opponent, only based on predicting all possible sequence of moves to come. In stratego "who" is the opponent has an impact on what is the best sequence of moves to do. For example if you know your opponent is a big bluffer you can take some more risks. If your opponent is a defensive player you can allow youself some moves that you wouldn't have done against a reckless attacker. This makes programming much more difficult.

If you don't know where you go ... you have a lot of chance to arrive elsewhere ...


#8 despy

despy

    Miner

  • Members
  • PipPipPipPipPip
  • 205 posts
  • Coat of arms
  • Platinum Marshal

Posted 01 June 2017 - 06:00 PM

A big difference between programming for chess or for stratego is that in chess you can program based on the effective position of the pieces on the board independently from "who" is the opponent, only based on predicting all possible sequence of moves to come. In stratego "who" is the opponent has an impact on what is the best sequence of moves to do. For example if you know your opponent is a big bluffer you can take some more risks. If your opponent is a defensive player you can allow youself some moves that you wouldn't have done against a reckless attacker. This makes programming much more difficult.

 

Yes, opponent modelling could certainly improve the algorithm's chances against a specific player, but in any case there wouldn't be enough data in a few games to make much of a difference in a best of 7 or similar. The point of CFR though is to play the Nash strategy, so in expectation, no strategy would be able to do better than tie the bot. In this sense who you are playing doesn't really matter.


Edited by despy, 01 June 2017 - 06:00 PM.





0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users