Game theory article from a professional Starcraft player/caster.(teamliquid.net)
teamliquid.net
Game theory article from a professional Starcraft player/caster.
http://www.teamliquid.net/forum/viewmessage.php?topic_id=64514
23 comments
That was awesome, sir. I love the attention to details in the scenario you described and your analysis. I only picked up the hobby of watching Starcraft about 6 months ago (I watch more Broodwar than Starcraft II), but I used to play a lot, albeit at an amateur level. I watched popular casters like diggity, Klazart, Nuke, and moletrap. However, sometimes I don't quite understand why the winner wins even though I have consumed a lot of theories in advance, perhaps for the exact reason you just pointed out. There are good comments on Team Liquid every now and then but the site is hard to browse with 100 pages on average for a popular game.
Do you write game analysis like this somewhere, or do you know where I can read something similar?
Do you write game analysis like this somewhere, or do you know where I can read something similar?
Day[9] (the author of the original essay), is easily the "go to" place for this sort of thing. He has a great amount of analysis scattered throughout his dailies, but here is a link to his most recent daily focusing on "how did I lose" (assuming I remember this daily correctly).
http://blip.tv/file/5460268
Also,
http://wiki.teamliquid.net/starcraft2/Day9_Daily
has a good list of his videos, with their subject, etc.
http://blip.tv/file/5460268
Also,
http://wiki.teamliquid.net/starcraft2/Day9_Daily
has a good list of his videos, with their subject, etc.
My little brother, quoting a noted SC personality: when you're ahead, get more ahead. It is probably the most important strategic lesson in the game: if you have a temporary 5 pct material advantage, you can still easily get outplayed if you force a fight. Better to turn that into a 10 pct material advantage, etc, and force a fight only after you've already won.
The other game I play a lot of is League of Legends, and sadly the community around my skill level has not learned this gospel yet. If it looks like we have 30 seconds of advantage, the team of 5 almost invariably either does nothing or goes for a decapitating stroke whose downside risk is loss. A better tactic is probably "Get more ahead so we win the next skirmish, too, snowballing until we win by concession or overwhelming force."
The other game I play a lot of is League of Legends, and sadly the community around my skill level has not learned this gospel yet. If it looks like we have 30 seconds of advantage, the team of 5 almost invariably either does nothing or goes for a decapitating stroke whose downside risk is loss. A better tactic is probably "Get more ahead so we win the next skirmish, too, snowballing until we win by concession or overwhelming force."
Didn't know you were interested in SC at all, patrick. Would you like to play some time?
I'm a platinum zerg, and don't play super often, but really enjoy the game.
My email is on my HN profile if you are interested.
I'm a platinum zerg, and don't play super often, but really enjoy the game.
My email is on my HN profile if you are interested.
Your brother is quoting the author of this article, in fact.
As someone who's been watching professional Korean SC competition for almost 10 years, the strategy described by your brother can be found from many high class players. Unlike Warcraft3 or other RTS, units in SC have very low health. Even if you have 5% more units, you can easily lose a fight within seconds from bad unit control, bad fighting position or just bad luck. It's never a good idea to attack just because you have 5% more units. Good players will continue play cautiously to make sure the opponent never gets a chance to take those 5% back. In the end, they win by the accumulated bits of advantages from various battles or economy advantages. You don't always need an glorious "final battle" to win the game, as long as your advantage is big enough (say 50%), you opponent will know that he lost and leave the game.
This is probably why SC has become very popular and still remains very popular. There are constant conflicts throughout the game trying to increase or take back the small advantages.
This is probably why SC has become very popular and still remains very popular. There are constant conflicts throughout the game trying to increase or take back the small advantages.
For the Starcraft watcher/spectator's counterpart of the article, there is the University of Washington Starcraft spectators study: http://jeffhuang.com/Final_StarcraftSpectator_CHI11.pdf
They explain the many types of people that watch Starcraft, and that Starcraft games are fun to watch because of "Information Asymmetry"
They explain the many types of people that watch Starcraft, and that Starcraft games are fun to watch because of "Information Asymmetry"
"Sun Tzu said: The good fighters of old first put themselves beyond the possibility of defeat, and then waited for an opportunity of defeating the enemy.
To secure ourselves against defeat lies in our own hands, but the opportunity of defeating the enemy is provided by the enemy himself.
[...]
Hence the skillful fighter puts himself into a position which makes defeat impossible, and does not miss the moment for defeating the enemy."
* * * * *
I think the spirit of what is being said in 'The Art of War', is the same principle that's being discussed in the article: Don't rush into striking before you are sure of victory, and lose everything; instead use the advantage to build yourself into an invincible position, with less risk.
* * * * *
'The Art of War' has been around a long time.
If there's a lesson here, its that strategy gamers might benefit from doing some reading.
I liked the article, and thought it was good; but it comes across that the author has no education in either (economic) game theory, or the study of game playing AI (e.g. minimax, search based AI techniques like you'd see in a chess AI etc). (Two related, but sometimes separate fields).
Which is fine - but there's a lot of good work in those fields, that strategy gamers, that seek to understand games analytically, as well as intuitively, would do well to read.
* * * * *
I think the spirit of what is being said in 'The Art of War', is the same principle that's being discussed in the article: Don't rush into striking before you are sure of victory, and lose everything; instead use the advantage to build yourself into an invincible position, with less risk.
* * * * *
'The Art of War' has been around a long time.
If there's a lesson here, its that strategy gamers might benefit from doing some reading.
I liked the article, and thought it was good; but it comes across that the author has no education in either (economic) game theory, or the study of game playing AI (e.g. minimax, search based AI techniques like you'd see in a chess AI etc). (Two related, but sometimes separate fields).
Which is fine - but there's a lot of good work in those fields, that strategy gamers, that seek to understand games analytically, as well as intuitively, would do well to read.
If there's a lesson here, its that strategy
gamers might benefit from doing some reading.
In short, I think there are very few if any sc2 players that would benefit (in terms of improving their game at least) from reading The Art of War.
>You have to play sc2 or similar games for years before that kind of advice becomes applicable (since there is so much basic skill to pick up before the game becomes that strategic), and by the time you know the game well enough to find the correct analogy to something written in The Art of War you've probably already discovered it yourself.
You seem to be saying that by the time they are playing at a level where general strategic advice becomes applicable, they'll already have learned it. This is a little circular.
Also, I think it probably takes a couple of months, before you get to the strategic level, not years, but that's just an opinion.
You seem to be saying that by the time they are playing at a level where general strategic advice becomes applicable, they'll already have learned it. This is a little circular.
Also, I think it probably takes a couple of months, before you get to the strategic level, not years, but that's just an opinion.
You seem to be saying that by the time they are
playing at a level where general strategic advice
becomes applicable, they'll already have learned
it. This is a little circular.
I said that by the time the advice that can be learned from reading TAOW becomes useful they would have already learned it from their "battle" experience.
What I am saying is that reading it in book form will at most provide an "aha - that's why this strategy I've been contemplating is good!" moment, rather than a new idea about how to play the game.
I've been playing sc2 on and off (mostly off) since it was released and am a diamond league player & most of the time the game is still more about paying attention and tactics rather than high level strategy for me.
And I am pretty sure I would have not have even got to this level were I not already a somewhat competent wc3 player.
Maybe if you play 10+ hours per week of sc2 every week since it came out you would not need years to master the game, but as a busy professional with little free time and many games I doubt you could ever reach that level in a matter of months without having played a lot of sc1/wc3 beforehand.
EDIT: take a look at http://wiki.teamliquid.net/starcraft2/Battle.net_Leagues#Lea... - 80% of players are at platinum league or less, where the game definitively requires more getting over basic tactics than high level strategy. I would bet you can win with a marine/zergling/zealot rush in almost every match in these leagues if you have sufficiently superior micro to your opponent.
> 80% of players are at platinum league or less
By definition, platinum or below is the bottom 80% of the player base. No matter how good the sc2 population gets, around 80% will ALWAYS be platinum or below.
That doesn't necessarily mean that the skill level for platinum or below will always be static though. For example, the korean server is generally regarded as more difficult. A platinum player on the NA server might only reach gold there (or might still be platinum but lose more).
But you are definitely correct that their mechanics are the main thing that separates most top players. I would emphasize macro as being much more important than micro though.
By definition, platinum or below is the bottom 80% of the player base. No matter how good the sc2 population gets, around 80% will ALWAYS be platinum or below.
That doesn't necessarily mean that the skill level for platinum or below will always be static though. For example, the korean server is generally regarded as more difficult. A platinum player on the NA server might only reach gold there (or might still be platinum but lose more).
But you are definitely correct that their mechanics are the main thing that separates most top players. I would emphasize macro as being much more important than micro though.
Sun Tzu was my first thought as well:
"The pinnacle of military excellence is not to win one hundred victories in one hundred battles. It is to subjugate your enemy without fighting."
Eg, to have the foresight and strategy to circumscribe and constrain your adversary's degrees of freedom until the only one left is capitulation.
Pretty cool that there are videogames rich enough for that to be applicable.
"The pinnacle of military excellence is not to win one hundred victories in one hundred battles. It is to subjugate your enemy without fighting."
Eg, to have the foresight and strategy to circumscribe and constrain your adversary's degrees of freedom until the only one left is capitulation.
Pretty cool that there are videogames rich enough for that to be applicable.
Studying pure game theory isn't going to help the SC2 player, at least not in any tangible way, the same with current AI practices.
The point he's trying to make is that truly great (in his view: competitive) games are those that the most advanced AI algorithms won't have any real competitive edge, so that game "theory" would back-up game "reality" of winning with a marginal advantage is more advantageous than winning "big".
The point he's trying to make is that truly great (in his view: competitive) games are those that the most advanced AI algorithms won't have any real competitive edge, so that game "theory" would back-up game "reality" of winning with a marginal advantage is more advantageous than winning "big".
It'd definitely help people wanting to write articles analyzing starcraft. There's definitely things the author doesn't get, that'd seem obvious if he'd read this stuff.
Anyway, I think most people study pure game theory, not because its directly applicable; they study it because there are some surprising results from it, that inform their strategic thinking - not because they apply it to evaluate their specific strategic situation.
>The point he's trying to make is that truly great (in his view: competitive) games are those that the most advanced AI algorithms won't have any real competitive edge, so that game "theory" would back-up game "reality" of winning with a marginal advantage is more advantageous than winning "big".
I'm not sure that's the point he's making. But anyway, I'm not sure its a valid point. For example, Chess is a game where the most advanced AI algorithms have a huge competitive edge, surely its a truely great, competitive, game?
It is desirable property in a game, that there is no obvious strongly dominant pure strategy. http://en.wikipedia.org/wiki/Strategic_dominance http://en.wikipedia.org/wiki/Strategy_(game_theory)#Pure_and...
"winning with a marginal advantage is more advantageous than winning "big"" doesn't at all follow from: "those that the most advanced AI algorithms won't have any real competitive edge".
Anyway, I think most people study pure game theory, not because its directly applicable; they study it because there are some surprising results from it, that inform their strategic thinking - not because they apply it to evaluate their specific strategic situation.
>The point he's trying to make is that truly great (in his view: competitive) games are those that the most advanced AI algorithms won't have any real competitive edge, so that game "theory" would back-up game "reality" of winning with a marginal advantage is more advantageous than winning "big".
I'm not sure that's the point he's making. But anyway, I'm not sure its a valid point. For example, Chess is a game where the most advanced AI algorithms have a huge competitive edge, surely its a truely great, competitive, game?
It is desirable property in a game, that there is no obvious strongly dominant pure strategy. http://en.wikipedia.org/wiki/Strategic_dominance http://en.wikipedia.org/wiki/Strategy_(game_theory)#Pure_and...
"winning with a marginal advantage is more advantageous than winning "big"" doesn't at all follow from: "those that the most advanced AI algorithms won't have any real competitive edge".
> It is desirable property in a game, that there is no obvious strongly dominant pure strategy.
Unless it's a game of skill. E.g. you win a race by running faster than other people. That can still be fun.
Unless it's a game of skill. E.g. you win a race by running faster than other people. That can still be fun.
Yes, sure, fair point.
I was talking about strategy games as such - but you are right that there's large elements of execution skill in many games, even in an RTS like starcraft, which is also fun to compete on.
Yes. Though even games that have dominant pure strategies in theory, like chess or go can be fun to compete in. Because humans don't have access to the optimal strategies, execution skill and gambling creep in.
(Gambling in the sense: You can create more or less complicated situations. There's more or less apparent entropy in the game you are playing then.)
(Gambling in the sense: You can create more or less complicated situations. There's more or less apparent entropy in the game you are playing then.)
What's your Elo?
Suffice it to say that if this whole entrepreneurship thing doesn't work out, my odds of supporting myself through professional gaming are even worse than everyone else's.
Don't feel bad. I'm a cool 900.
The flip side of this is that if you are down by a little bit, you should not allow your opponent to slowly and confidently increase his advantage (unless you think he'll make little mistakes and lose the advantage; that would probably mean you're better than him, and we're probably not talking about that situation). Instead, you should force a big risky fight in which your opponent has a substantial chance of losing, if that's possible.
Along similar lines, chess grandmaster John Nunn wrote, in Secrets of Practical Chess, that when you are down, you have two basic strategies: "grim defense" and "create confusion". If you are, say, a pawn down, it may still be possible to draw if you make no mistakes; your opponent will have to work hard to force a win, and he may even get impatient and try to win quickly with a risky strategy; this is "grim defense". If that strategy is unappealing (if his advantage is simple to consolidate and exploit, or if you don't feel like slow and careful defense), then you may opt to do risky things to create complicated, high-stakes positions and hope your opponent makes a mistake; this is "create confusion".
Along similar lines, chess grandmaster John Nunn wrote, in Secrets of Practical Chess, that when you are down, you have two basic strategies: "grim defense" and "create confusion". If you are, say, a pawn down, it may still be possible to draw if you make no mistakes; your opponent will have to work hard to force a win, and he may even get impatient and try to win quickly with a risky strategy; this is "grim defense". If that strategy is unappealing (if his advantage is simple to consolidate and exploit, or if you don't feel like slow and careful defense), then you may opt to do risky things to create complicated, high-stakes positions and hope your opponent makes a mistake; this is "create confusion".
As many of the sc2 players here might know, the guy who wrote this (day9) is one of the famous person in esports right now. He used to be a professional player of sc, but since sc2 appeared (2010) he dedicated to analyze the game, and has even a daily show about it.
The interesting thing about starcraft is that it's played _so_ much (in s. korea is a profession, kids actually go to live in "pro houses" were they play all day), that the game has/is evolving to a point where every little thing matters. In the highest levels, you can't really fight a straight up battle and hope to win, it's a game of getting little advantages (like removing %1 of his income) and trying to get ahead, and push those advantages much later on. Increasing your economy, building up you army, the execution and management of your units in the fight, everything counts.
The interesting thing about starcraft is that it's played _so_ much (in s. korea is a profession, kids actually go to live in "pro houses" were they play all day), that the game has/is evolving to a point where every little thing matters. In the highest levels, you can't really fight a straight up battle and hope to win, it's a game of getting little advantages (like removing %1 of his income) and trying to get ahead, and push those advantages much later on. Increasing your economy, building up you army, the execution and management of your units in the fight, everything counts.
The game is played at a high level, sure, but I'd call this a slight exaggeration. 1% of a player's income is less than a single worker even in the late game (when most players have around 70 workers), and a single worker kill never really makes a huge difference.
Killing a single mining worker can make a difference very early in the game if they're using a very timing-heavy strategy, but that's really only at the very tip-top levels of play.
Depends when the kill is. A single worker from your initial 6? Big problem.
You can't even get a scout worker to your opponent's base before they're up to 9-10 workers or more on most maps. Anyway, killing one worker of 6 is 17% of someone's economy, not 1%.
Killing a worker early is subject to compound interest, so that 17% (or 10% more realistically) of an early worker kill is going to grow exponentially all game long.
>an early worker kill is going to grow exponentially all game long.
That's a very unrealistic claim, though yes, losing a worker very early can have a measurable effect. But that pretty much never happens, outside of all-in cheeses like 6 pool or proxy 2 rax/gate.
Are you defending the original claim that games are decided over affecting 1% of one's opponents economy?
That's a very unrealistic claim, though yes, losing a worker very early can have a measurable effect. But that pretty much never happens, outside of all-in cheeses like 6 pool or proxy 2 rax/gate.
Are you defending the original claim that games are decided over affecting 1% of one's opponents economy?
> the original claim that games are decided over affecting 1% of one's opponents economy?
The original claim wasn't that the game was decided over 1% of someones economy. Rather, that games were decided over many small advantages gained, things like affecting someones economy by 1%. You do that 5-10 times throughout the game, and that's a good 5-10% of their economy.
The original claim wasn't that the game was decided over 1% of someones economy. Rather, that games were decided over many small advantages gained, things like affecting someones economy by 1%. You do that 5-10 times throughout the game, and that's a good 5-10% of their economy.
Well that's not actually how games are decided these days. It's often something like "did Z have queens blocking his ramp before the blue flame hellions got there?" or "did P get scout the tech lab on the starport and put down a robo in time?", even at the pro level. A lot of other games end with a two-base timing attack (e.g. fast blink stalkers). Good games will have some eco harass, but more along the lines of dropping 8 marines and killing several workers, or totally taking out an expo with infested terrans. I don't think I've ever seen a single worker kill be significant, or even multiple instances of similarly small magnitude. The APM and attention it costs to harass often isn't worth killing a single worker.
There's a lot of depth to SC2, but I think it's a mischaracterization to say that it's a game of such tiny advantages, at least at the level it's played today.
There's a lot of depth to SC2, but I think it's a mischaracterization to say that it's a game of such tiny advantages, at least at the level it's played today.
Sean "Day[9]" Plott (the author of the article) is probably the best analytical Starcraft II caster around. His "Day[9] Dailies" cover everything from the absolute fundamentals ("here's how you set up your hotkeys, here's how you keep your money low") to more advanced topics like build orders, expanding, tactics, and micro. He also throws in "Funday Mondays", where beginner and experienced players alike try to win with unorthodox constraints (usually with funny and/or insightful results).
Bronze league matches often end up being a contest of who can win with the first rush or the earliest "cheese", but most pro-level play does end up being a careful balance between aggression, defense, and expansion. The winner is usually the one who can stay just slightly ahead of their opponent until they can seize a clear advantage.
Bronze league matches often end up being a contest of who can win with the first rush or the earliest "cheese", but most pro-level play does end up being a careful balance between aggression, defense, and expansion. The winner is usually the one who can stay just slightly ahead of their opponent until they can seize a clear advantage.
Slightly unrelated but Day9 also had a really good daily on what it is to dedicate yourself to something for a very long time. Great bits and pieces for any entrepreneur and worth watching if you even know anything about starcraft:
http://www.youtube.com/watch?v=NJztfsXKcPQ
Edit: 0:28:45 - On strategy and execution
http://www.youtube.com/watch?v=NJztfsXKcPQ
Edit: 0:28:45 - On strategy and execution
I really enjoyed watching that, though not really from the standpoint of an entrepreneur. What I really took from that video was how important a support structure is. It sounds like he wouldn't have gone as far as he did without his brother and mother being behind him 100% for years. Every time he had a failure, there were people there to help him get past it and learn from it instead of getting discouraged. He gained this support structure by being so passionate about his game that he made his mother believe in him.
> Every time he had a failure, there were people there to help him get past it and learn from it instead of getting discouraged.
> being so passionate about <x> that he made <y> believe in him
IMHO, this sounds like two pieces of sage advice for entrepreneurs already :)
> being so passionate about <x> that he made <y> believe in him
IMHO, this sounds like two pieces of sage advice for entrepreneurs already :)
There is no _Game theory_ mentioned anywhere in the article, but _Competitive game design theory_.
Title should be changed to reflect that as to not bring confusion about it referring to the broad (and complex) Game theory subject.
Title should be changed to reflect that as to not bring confusion about it referring to the broad (and complex) Game theory subject.
Day9 hosted an event called The After Hours Gaming League in which eight tech companies will compete each other for charity. The event has just finished its first season with team Microsoft crushing everyone else. Zynga is the runner up and Google claimed third place.
Games: http://www.youtube.com/results?search_query=ahgl Homepage: http://afterhoursgaming.tv/
There are a number of interesting game theory articles on competitive Starcraft. This is one: http://www.teamliquid.net/forum/viewmessage.php?topic_id=258... (and my comment to it: https://plus.google.com/116918963723558831013/posts/A8DRTY11...).
Games: http://www.youtube.com/results?search_query=ahgl Homepage: http://afterhoursgaming.tv/
There are a number of interesting game theory articles on competitive Starcraft. This is one: http://www.teamliquid.net/forum/viewmessage.php?topic_id=258... (and my comment to it: https://plus.google.com/116918963723558831013/posts/A8DRTY11...).
I was really impressed how Microsoft steamrolled everyone!
I was less impressed with Microsoft's performance than their team spirit. After all, the mere fact that MSFT has way more employees than the other teams already means that they should be stronger. However, I was surprised that they set up an internal league to select who will get to play, and that there were many MSFT people watching together live on the grand finals day. It just seems like they take fun seriously (to quote Day9 himself), and that's pretty cool IMO.
Anybody want to start a YC or HN league?
=]
=]
The new 4-5dan go-playing bots on kgs (zen19d, crazystone) use this strategy extensively. When they're ahead they play to consolidate their biggest weakness, and when they're behind they play more and more risky moves to try to come back. In the endgame the calculate the score exactly, and will play negative point value moves as long as they are ahead on the board.
It makes for a really tough game, cause if you do get ahead, you have to face a series of attacks which almost but don't quite work, and if you mess up any of them it's over.
It makes for a really tough game, cause if you do get ahead, you have to face a series of attacks which almost but don't quite work, and if you mess up any of them it's over.
Interesting that they use this strategy. Essentially, high variance is good when the expected value of the game is negative. It increases the chances of success in a bad situation.
The maths of this can be found in the article "A Rule of Thumb (not only) for Gamblers." Currently, this article is available free here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.3...
The maths of this can be found in the article "A Rule of Thumb (not only) for Gamblers." Currently, this article is available free here: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.3...
Yeah I read the advice in this article years ago in a beginner's Go tutorial, something about "you just need one more point than the opponent to win".
Lot of little zen-like lessons in learning that game, is why I love it.
Lot of little zen-like lessons in learning that game, is why I love it.
Interesting. I don't really know much about basket ball. But I have noticed something similar. In the last seconds of the game, the loosing team will try riskier moves. (Forcing penalties and throwing from the three point line). It is like playing roulette.
My Go teacher once told me that the truely great players will hold a game in near perfect balance throughout. Concerningy, are the computers really at 4 dan now? I ain't never going to beat the machines.
yeah, they have really gotten good in the last year. They've gone from better than 90% of players who have ever played go, to better than 95%+. They are great to watch, too, merciless and play interesting moves.
Check out crazystone's stats: http://kgs.gosquares.net/index.rhtml.en?id=CrazyStone&y=...
72% win percentage as a 4d.
Check out crazystone's stats: http://kgs.gosquares.net/index.rhtml.en?id=CrazyStone&y=...
72% win percentage as a 4d.
This marginal advantage strategy is also well demonstrated in professional tennis. When you are in control of the rally, going for a shot which maintains your offensive position, with the potential to slightly extend your lead within the rally, is best. Often the defensive player will go for a huge winner if they are getting tired or are so out of position as to be unable to recover by hitting several good marginal defensive shots to get the point back to a neutral position. But if you watch the best players, they all have skills which gain or erase the most marginal advantages.
Tennis, yes! And I would guess also Basketball and other games with small but many incremental scoring.
I read some time an article in which was argued, that this is a fundamental difference in Soccer compared to other team sports. As there is often only 1-2 goals in Soccer a Toss-up between a top team and an underdog is more likely. It is even often the case that a team is playing dominating but they lose anyhow, because the weaker team is getting lucky and stumples the ball in the goal. This keeps the sport fresh and interesting and is seen by fans as a virtue. The randomness is then cancelled out over the season and marginal advantage is important in competition for the league championship.
I read some time an article in which was argued, that this is a fundamental difference in Soccer compared to other team sports. As there is often only 1-2 goals in Soccer a Toss-up between a top team and an underdog is more likely. It is even often the case that a team is playing dominating but they lose anyhow, because the weaker team is getting lucky and stumples the ball in the goal. This keeps the sport fresh and interesting and is seen by fans as a virtue. The randomness is then cancelled out over the season and marginal advantage is important in competition for the league championship.
Am I the only one that thought this post would have been about Economic Game Theory? - http://www.dklevine.com/general/whatis.htm
Very nice read though. Day9 is right. The best players all seem to have a knack for maintaining a marginal advantage or taking a small one and getting a bigger advantage.
Very nice read though. Day9 is right. The best players all seem to have a knack for maintaining a marginal advantage or taking a small one and getting a bigger advantage.
If I remember correctly from my college AI days, thinking about upcoming turns and minimizing your opponent's gains is called minimax: http://en.wikipedia.org/wiki/Minimax
I'm surprised that there was only one AI in the competition that did this. We were all expected to use this strategy in my class. Once everybody's figured this out, it becomes a game of:
- Who can think ahead the most turns? - Who has the best "am I winning?" heuristic function? (For Mancala this function is fairly obvious, but for many games it's not.)
I'm surprised that there was only one AI in the competition that did this. We were all expected to use this strategy in my class. Once everybody's figured this out, it becomes a game of:
- Who can think ahead the most turns? - Who has the best "am I winning?" heuristic function? (For Mancala this function is fairly obvious, but for many games it's not.)
I agree, the Mancala backstory sounds quite strange and unbelievable. To me it looks like it's made up (maybe partly on some vague recollection of the author) to serve as an introduction for the rest of the article.
The behavior of AI programming winning by 1 point does exist in real life for Monte-Carlo based agents calculating winning probabilities. You can see it in computer go games.
The behavior of AI programming winning by 1 point does exist in real life for Monte-Carlo based agents calculating winning probabilities. You can see it in computer go games.
It's almost certainly based on the author's experience in Harvey Mudd's CS 151 (Artificial Intelligence) course, in which developing a Mancala AI is a standard project.
I believe Day 9 did indeed get his masters this year from Harvey Mudd. (original article was written 4 years ago)
Researchers from Berkeley developed a fairly good Starcraft AI engine that combined micro-management, pathing, and overally strategy to win the Starcraft AI competition: http://arstechnica.com/gaming/news/2011/01/skynet-meets-the-...
Yup the strategies described are very primitive and explained quite vaguely. That was the first thing I noticed. You don't make AI to capture the maximum number of pieces and you don't make AI to get only 1 piece advantage. I may be wrong here as I dont know anything about Mancala.
Note that this article isn't on game theory, but on game design theory (i.e., 'game' as in 'computer game').
The author stated, "Third, a good competitive game should test a player’s skills and minimize the element of chance or luck. Ideally, the probability of a weak player defeating a good player should be as close to zero as possible."
Do you think this is always the case? I'm thinking about texas hold 'em, which has short-term variability but the stronger players win over the long run with a better strategy. Does chance have a place in competitive gaming?
Do you think this is always the case? I'm thinking about texas hold 'em, which has short-term variability but the stronger players win over the long run with a better strategy. Does chance have a place in competitive gaming?
The relevant quote here is, "People don't gamble on Chess."
A luck element lets players of uneven skill feel engaged. Even better is a great handicapping system like Go has, but that's notoriously hard to design.
Chess is a great game at certain skill levels and has a lot of beauty to it, but games with enough of a skill difference aren't really interesting for either player unless the better player is teaching/mentoring.
So yeah, luck has some place in letting different people (and even gamble) together.
A luck element lets players of uneven skill feel engaged. Even better is a great handicapping system like Go has, but that's notoriously hard to design.
Chess is a great game at certain skill levels and has a lot of beauty to it, but games with enough of a skill difference aren't really interesting for either player unless the better player is teaching/mentoring.
So yeah, luck has some place in letting different people (and even gamble) together.
I know some people who actually gamble on chess. The thing is, that even with a perfect game (not saying that chess is perfect) you still have the human factors involved. The spirit, the concentration of both players today, the pressure involved when betting money or playing in front of observers. There is still a lot of margin left.
I guess there wouldn't be any incentive for weaker players to bet if they were guaranteed to lose money every game! I find that issue with chess... I'm better than my friends (who have only played a handful of times) but get smoked online or by serious players.
This is a pretty common position amongst competitive gamers, but I disagree with it strongly.
I think that the issue is that people feel cheated if they are in the zone/on a perfect run, and have that pulled from under them by chance. However, I would contest that having some risk makes it more exciting.
Another likely issue is the fear that your tactics and your highly drilled skills might become less relevant if some elements of the game are based on chance/randomized. It essentially negates some of your time investment in the game. For myself, I think that it's more interesting to have to adapt your tactics to new situation. I also find the skills that a game involving chances emphasizes tend away from the repetitive and towards general strategy, for example: map knowledge becomes less important compared to scouting.
I think that the issue is that people feel cheated if they are in the zone/on a perfect run, and have that pulled from under them by chance. However, I would contest that having some risk makes it more exciting.
Another likely issue is the fear that your tactics and your highly drilled skills might become less relevant if some elements of the game are based on chance/randomized. It essentially negates some of your time investment in the game. For myself, I think that it's more interesting to have to adapt your tactics to new situation. I also find the skills that a game involving chances emphasizes tend away from the repetitive and towards general strategy, for example: map knowledge becomes less important compared to scouting.
Yes. In Starcraft, it is not uncommon for players to attempt to force a win by going for an all-in strategy that sacrifices long-term income for lots of first-tier combat units. The chance aspect is that there are more starting locations than there are players. If your opponent does not find you quickly enough and you are relatively close, both of which are purely matters of chance, you can overrun them, almost regardless of skill differences.
In Texas Hold 'Em, competitive matches are rarely decided in a single hand; rather, they are played out over many hands through the course of a day. When you average out over dozens of hands, a substantially worse player actually does have an almost zero chance of besting a superior player.
It is well known that luck plays a major role in all the big competitions in Texas Hold'em. In a field of a thousand players, the best players usually have no more than a .2% or a .3% chance of winning at the very best. (Thus the best players win 2 or 3 times more often than the average players).
For heads-up play (a match between two players), the winrate of a winning player versus a substantially worse player is can be anywhere from 4 big blinds/100 hands to 20 big blinds/100 hands. The standard deviation is more like 140 big blinds/100 hands. This means that you have to play quite a while to have an almost zero chance of winning, even against a substantially worse player. Most professional poker players even have an occasional losing month (let's say one a year an average).
For heads-up play (a match between two players), the winrate of a winning player versus a substantially worse player is can be anywhere from 4 big blinds/100 hands to 20 big blinds/100 hands. The standard deviation is more like 140 big blinds/100 hands. This means that you have to play quite a while to have an almost zero chance of winning, even against a substantially worse player. Most professional poker players even have an occasional losing month (let's say one a year an average).
For those that aren't familiar with it, the teamliquid.net forum typically has very high-quality posts (i.e. heavily moderated) and a great resource for anyone interested in e-sports. I recommend you check out the front page if you haven't before.
This article correctly notes that those in the lead should play to conservatively extend their marginal advantage.
The corollary, for those in behind, is that they should attempt more gambits.
The principles of variance are strange. Sometimes, if you're in behind, you reduce your chance of losing by adopting what looks like a "losing" strategy (according to naive expected value calculations). With a wild all-or-nothing strategy, your chance of winning from behind likely won't exceed 50%, but by acting more like the 'risky amateur,' you might up your chances from 10% to 30%.
The corollary, for those in behind, is that they should attempt more gambits.
The principles of variance are strange. Sometimes, if you're in behind, you reduce your chance of losing by adopting what looks like a "losing" strategy (according to naive expected value calculations). With a wild all-or-nothing strategy, your chance of winning from behind likely won't exceed 50%, but by acting more like the 'risky amateur,' you might up your chances from 10% to 30%.
In my opinion, the most important concept to understand is "Timing windows". Vs a equally skilled player, you can't have all the advantages. Understanding the imbalances of a current situation - and taking advantage of it - is really what differentiate beginners from great players.
Sometime, in a game of 30mins, there's only a few seconds where you have the upper hand.. and this is where you need to attack. Miss that moment (from a couple of seconds!!) and you lose. Go a little bit before, and you lose!
Sometime, in a game of 30mins, there's only a few seconds where you have the upper hand.. and this is where you need to attack. Miss that moment (from a couple of seconds!!) and you lose. Go a little bit before, and you lose!
So much stuff can be learned from sc/sc2 to apply in your life. Things from accepting defeat and understanding your mistakes, to know how to fight strategically. (By fight I mean it in a very vague way; Fight for a girl, Fight for a new job, etc.)
I just read all the comments because the author states that one program collects the maximum amount of stones, and another competitor's program figured out how to collect an additional stone.
Does this not make sense to anyone else? Can someone please explain it to me?
Does this not make sense to anyone else? Can someone please explain it to me?
My understanding was that the competitor's program collected a strategic number of stones N in such a way which forced the other program to be able to collect at most N-1 stones on its next turn. I'm not familiar with the rules of Mancala but I presume they allow for strategies such as this.
There's a difference between collecting the maximum amount of stones and collecting more stones than the opponent. I suspect the winning program also tries to minimize the stones the opponent will be able to collect, thus preserving its marginal advantage.
Edit: Apparently colanderman beat me to it.
Edit: Apparently colanderman beat me to it.
Maybe the "one more stone" strategy leaves more options to the decider algorith and is therefore less likely to get stuck in a local maximum that ultimately leads to a loss.
[deleted]
this is a life lesson, not a game design theory lesson!
I browse hacker news and reddit/r/starcraft each day.. I love when an article appears on both :) A perfect mix between hacker-ness and gamer-ness.
great article, good reminders of how to build a great competitive game, which is applicable to me!
So much time and resources wasted on a game. My heart bleeds.
Not Game Theory really, but Ender Wiggin has some good points...pitty its just a game.
The pitfall for the average viewer/player is to take these mantras and apply them directly to what they see. They see a game where T apparently overcommits after winning an engagement at his 3rd, and wonder why he didn't take a 4th instead. Surely, this is a mistake of not getting more ahead!
An expert player might look at the same scenario and see an entirely different picture. The problem was that he scanned a 15m timing instead of a 17m timing for the Hive, so he was actually behind in that engagement (he should have decisively won with the Z's gas locked up elsewhere!). And that Broodlords would be due out in 2 production cycles, but it takes 3m for him to break-even on the new mine, and he would miss the window to secure enough of an advantage to push the game into a low-econ trade phase.
My point is that real game understanding is extremely specific. It's all about the actual state and timing. To go back to the article, that's where the marginal advantages are gained - by understanding and controlling how these extremely specific scenarios play out. The larger ideas about strategy that everyone loves fall out from the analyses of these interactions. But "getting" the general idea isn't the same as actually _getting_ it when you work out these scenarios and timings yourself from extensive playing/testing. So heuristics are really only part of the picture, the much larger part is a precise understanding of the system at work.