Jump to content


Photo

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


  • Please log in to reply
43 replies to this topic

#1 General Rascal

General Rascal

    Miner

  • Members
  • PipPipPipPipPip
  • 180 posts
  • Coat of arms
  • Gold Colonel

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?


  • TemplateRex likes this

#2 The Prof

The Prof

    Colonel

  • NASF Committee
  • 1,515 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


  • TemplateRex likes this

#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 and TemplateRex like 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

    Sergeant

  • Members
  • PipPipPipPipPipPip
  • 267 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/


My Youtube Stratego Channel: https://www.youtube....cGDvlZZkGbgq0LA


#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.

  • TemplateRex likes this

#7 Napoleon 1er

Napoleon 1er

    General

  • Honorary members
  • PipPipPipPipPipPipPipPipPipPipPip
  • 2,533 posts
  • Coat of arms
  • Platinum General

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.


#9 Dobby125

Dobby125

    Sergeant

  • Members
  • PipPipPipPipPipPip
  • 267 posts
  • Coat of arms
  • Silver Major

Posted 11 December 2017 - 03:05 PM

A pretty interesting development in the chess world.

 

https://www.technolo...thout-any-help/

 

https://www.chess.co...-100-game-match

 

https://gizmodo.com/...just-1821081928

 

Maybe we should challenge AlphaZero to try learning Stratego.


  • TemplateRex likes this

My Youtube Stratego Channel: https://www.youtube....cGDvlZZkGbgq0LA


#10 TemplateRex

TemplateRex

    Sergeant

  • Members
  • PipPipPipPipPipPip
  • 386 posts
  • Coat of arms
  • Silver Lieutenant

Posted 11 December 2017 - 04:02 PM

A pretty interesting development in the chess world.

 

https://www.technolo...thout-any-help/

 

https://www.chess.co...-100-game-match

 

https://gizmodo.com/...just-1821081928

 

Maybe we should challenge AlphaZero to try learning Stratego.

 

Earlier this year, a student named Johannes Heinrich obtained his PhD under the supervision of David Silver, the lead researcher on AlphaGo and AlphaZero. See http://discovery.ucl...h_phd_FINAL.pdf Together, they developed reinforcement learning methods for imperfect information games such as poker. In principle, these methods should be applicable to Stratego. Combined with the massive resources that were used to create super-human Go, chess and Shogi programs, they might be able to create a super-human Stratego program. The question is whether these methods scale as well as they do for perfect information games (possibly), and whether Google / Deepmind want to invest in the game of Stratego (unlikely). It seems that games such as Starcraft and Dota2 are games that attract far more attention from deep learning companies.


Edited by TemplateRex, 11 December 2017 - 04:03 PM.


#11 Morx

Morx

    Lieutenant

  • WC Online Team
  • 681 posts
  • Coat of arms
  • Platinum General

Posted 11 December 2017 - 04:03 PM

Im working on a new bot. The first version has codename LakeBot. It actually moves pieces in a very simple pattern, but I made the software such that all the other infrastructure supports more advanced bots.

 

So a new version of a bot or a new bot can seamlessly replace the more simple one.


  • TemplateRex likes this

#12 TemplateRex

TemplateRex

    Sergeant

  • Members
  • PipPipPipPipPipPip
  • 386 posts
  • Coat of arms
  • Silver Lieutenant

Posted 11 December 2017 - 04:17 PM

Im working on a new bot. The first version has codename LakeBot. It actually moves pieces in a very simple pattern, but I made the software such that all the other infrastructure supports more advanced bots.

 

So a new version of a bot or a new bot can seamlessly replace the more simple one.

 

Very interesting! Do you have some code to play with on GitHub? 



#13 OuweSok

OuweSok

    Sergeant

  • Members
  • PipPipPipPipPipPip
  • 495 posts
  • Coat of arms
  • Platinum Spy

Posted 11 December 2017 - 04:24 PM

Can an AI be developed that can beat Hielco and Nortrom consistently?
Absolutely. The AI can bluff profitably vs the top poker players in the world, it can surely bluff in Stratego. Also its memory and tactics will be flawless. The lack of perfect info will be countered by analyzing the 100k most likely positions and calculating the best move.
  • TemplateRex likes this

Check out my Stratego Youtube channel ! :o


#14 roeczak

roeczak

    Captain

  • Tournament Manager
  • 869 posts
  • Coat of arms
  • Platinum Captain

Posted 11 December 2017 - 05:05 PM

The game is designed in such a way that even if that program is developed , even a gold or silver player will be able to beat in a single game.
I was a denier that there can ever be a good AI program , but I'll have to look into the links TR posted above.
If you enjoy stratego you might want to subscribe to Roeczak. Member of Stratego Captains Club. Actively trying to promote the game and would like to help in any activity towards that goal. Highest Rating : 898 (Platinum Marshal)

#15 ScottLafaro

ScottLafaro

    Scout

  • Members
  • PipPipPipPip
  • 108 posts
  • Coat of arms
  • Gold Spy

Posted 11 December 2017 - 05:05 PM

There is no substitute for intuition (Paul Klee).

 

Unladen told me once he plays on intuition most of the time. 

 

I believe players like US, Napoleon 1e and Hielco will be able to fool AI by switching stances.


thus spoke zarathustra


#16 Morx

Morx

    Lieutenant

  • WC Online Team
  • 681 posts
  • Coat of arms
  • Platinum General

Posted 11 December 2017 - 05:09 PM

Intuition is just the experience of playing many games and analyzing situations and opponents. A master of Stratego can "read" the board.

 

Nobody so far tried with a real budget to make a good AI for Stratego and I think it may need expert knowledge to capture the more advanced techniques used by the pros.

 

The alternative may be to build a self learning one but my programming skills in this field are a bit lacking to do that.



#17 GaryLShelton

GaryLShelton

    Flagbearer

  • Moderators
  • 5,219 posts
  • Coat of arms
  • Gold Major

Posted 12 December 2017 - 07:10 AM

How can the average Joe know that the computer isn't in full knowledge of all pieces simply because you're playing on the computer?

When I'm playing Probe and it lottoes, it sure seems smart about the bombs. :)

The complete GS&F Rules can be found here: http://forum.strateg...rum-rules-2016/

Draw Refusal Rules, specifically, can be read here: http://forum.strateg...604#entry339604

#18 Dobby125

Dobby125

    Sergeant

  • Members
  • PipPipPipPipPipPip
  • 267 posts
  • Coat of arms
  • Silver Major

Posted 12 December 2017 - 04:16 PM

How can the average Joe know that the computer isn't in full knowledge of all pieces simply because you're playing on the computer?

When I'm playing Probe and it lottoes, it sure seems smart about the bombs. :)

 

You could have a game where you don't enter a game setup at all.  Just have 40 placeholders as pieces.  You could easily follow the game on a real physical Stratego board with your game setup.  When pieces are attacked, you then reveal your piece to the program.

 

Probe is a master at lottoing.  It's almost as good as Major Nelson:D


My Youtube Stratego Channel: https://www.youtube....cGDvlZZkGbgq0LA


#19 GaryLShelton

GaryLShelton

    Flagbearer

  • Moderators
  • 5,219 posts
  • Coat of arms
  • Gold Major

Posted 12 December 2017 - 07:18 PM

Like a black speck on a white wall, I sense the definite start of a reputation, Major Nelson. :D
  • Fks likes this

The complete GS&F Rules can be found here: http://forum.strateg...rum-rules-2016/

Draw Refusal Rules, specifically, can be read here: http://forum.strateg...604#entry339604

#20 GaryLShelton

GaryLShelton

    Flagbearer

  • Moderators
  • 5,219 posts
  • Coat of arms
  • Gold Major

Posted 12 December 2017 - 07:21 PM

You could have a game where you don't enter a game setup at all. Just have 40 placeholders as pieces. You could easily follow the game on a real physical Stratego board with your game setup. When pieces are attacked, you then reveal your piece to the program.


So, the answer to my question is that one can only be sure of the computer's ignorance of his pieces if he does things manually? I've actually done this with Score Four with The Prof on Skype. We each have a physical board and then call out the movements to one another which we each match on our respective boards. But it's a bit of a pain, unfortunately.

The complete GS&F Rules can be found here: http://forum.strateg...rum-rules-2016/

Draw Refusal Rules, specifically, can be read here: http://forum.strateg...604#entry339604




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users