I realized that my previous post did not fully clarify the scale in question; let me assure everyone that the scale is intended to measure only the impact of random chance upon gameplay, it is not a value judgment.

Someone might look at that scale and immediately infer game snobbery (“Oh, so Pat thinks Chess is the end-all of games, huh?”) That’s not accurate. In fact, precisely the opposite.

When I was somewhere between 10 and 12 years old, I remember deciding that Chess was an uninteresting game to play. This was, admittedly, naivete on my part, since my reasoning was based upon a set of false assumptions. Those assumptions went something like this: “Each piece has established rules for movement. There’s only 64 squares on the board. Therefore, there’s a limited number of possible outcomes for moves and countermoves. Once you know them all, there’s only a limited number of moves you can make before the winner of the game is decided. So the winner is the person who can memorize more moves and countermoves. Bo-ring!” One of the problems with being a smartass kid is that you often times reach conclusions before you have all of the evidence intact for buttressing up your assumptions (pop quiz: where was my logic broken, there?)

Turns out, the mathematics behind Chess are a bit more complex. From the standpoint of training your mind, Chess is a worthy endeavor, since the total number of possible scenarios outweighs that which one can keep in one’s head. Even chess Grandmasters are limited in the number of possible scenarios they can reasonably compute as outcomes to their possible moves on any turn. Heck, even the brute force method used by Deep Blue and other Chess-playing computers has limitations.

That said, while I was wrong as to why Chess was “boring”, I was right in one aspect… you can program a computer to beat a human. Deep Blue beat Kasparov in 1989 (which reinforced my smart-assitude to no end), and it’s only gotten worse. Given the set of fixed options, today’s computers are going to beat the snot out of a human player, even someone who spends a lifetime studying Chess. The reason for this is that brute force approach: the computer can plot out possible combinatorics faster than a person can, more accurately, and retain the outcome for comparison. Over and over again. Chess is too complicated to program out the endgame from the first move, but there’s a limit to how many comparisons a human can calculate internally, and the graphs intersected twenty years ago. The computers will continue to win.

In the meta sense, then, I was even right about Chess being boring at least as far as the way my brain works… brute force approaches lack style and poetry. If the brute force approach is the optimal approach, then the game is, at heart, lacking in style and poetry. Sure, in an individual match between players you might see style having an impact, but that’s because humans can’t optimally use the optimal approach! In the main what works best for Chess is straight computation. Ugh, if I liked that, I would have been an applied mathematician or (horrors!) an engineer.

See what I did there, Hammer?

I like games with an element of chance. Not too much (unless you’re playing with a four-year-old, “War” is about as boring as a game can possibly be), but enough to force style and poetry back into being an element of the game. Having a great strategy in Acquire or Risk is important; being able to recover your position at least somewhat after a run of bad luck is equally important, if not more so. Winning while beating your opponent is an important aspect of gameplay for any game… but winning while beating your opponent *and* Murphy is better, and oh so much more delicious.

By that argument, virtually ALL games lack style and poetry. What game with clearly-defined rules can’t be the subject of a well-designed brute force analysis of decision trees? About the only exceptions might be RPGs, where such trees can’t be easily constrained. Given that your computer opponent might have a run of bad luck in dice rolls or card draws you might still win, but that’s akin to having a coin-tossing contest- there’s still no skill in it from the computer’s perspective.

Moral: ban computers from gaming. Computers bad!

> What game with clearly-defined rules can’t be the

> subject of a well-designed brute force analysis of

> decision trees?

A good many of them. Well, to be precise, in practice a good many of them can’t be attacked with brute force in a

computationally feasiblemanner, as the decision tree is far too complicated. While admittedly Chess can’t be attackedfullyin a computationally feasible manner, the current brute force methodology is good enough to bust a human.Put another way, all zero-sum games with closed boundaries have brute force computational attacks… but the order of operations required to net a winning strategy falls outside the near-term (or in many cases longer-term) capabilities of binary computers. It’s like cryptanalysis… MD4 is breakable, but AES-256 isn’t (at least, as far as we know right now) 🙂

Take, for example, the game “Risk”. You’re right… in a game between two agents, you can account for probability in your decision tree analysis. If you have two completely rational agents, both using a “well-designed” brute force decision tree analysis, you’re right… you wind up with a coin-tossing contest.

In practice, though…

(1) games aren’t between two agents

(2) generally speaking very few (if any) agents in the game are completely rational agents

(3) your well-designed brute force decision tree probably can’t meet the same criteria for success as a similar attack on Chess

Usually, player strategies are only very loosely coupled to optimal strategies.

It is the interaction of the skill, random chance, and the estimation of the other players’ strategic short term and long term goals, is what makes the game interesting.

The only limiting factor is the processing power of the machines that conduct the decision tree analysis. As such, any game where choices are constrained (especially when those choices occur in a very limited number of ‘turns’, as in something like Axis & Allies) can be ‘cracked’ with brute force. Sure, we may not have the computational power to break a more complex game open now, but that’s just semantics. I maintain that what makes games interesting is the interplay between people. But don’t judge a game’s potential for style and poetry by their vulnerability to that sort of analysis.

> Any game where choices are constrained (especially when those

> choices occur in a very limited number of ‘turns’, as in something

> like Axis & Allies) can be ‘cracked’ with brute force.

No, this is not correct. At least, not in practice. You need to read Scott Aaronson’s blog (linked on my home page) and learn a bit about computational complexity.

If the number of operations required to brute force attack a decision tree is sufficiently large, the limiting factor is not the processing power of the machines, but physics. There’s only 10^80 atoms in the universe (roughly), so computations that require (well, within a freaking large delta of that number *on the underside*) number of operations are not computationally feasible, regardless of the binary computer processing capability. Quantum computing aside, being able to calculate the number of operations required to brute force attack a decision tree != being able to calculate all of those operations.

Given what I understand to be the current state of quantum computing, this is likely to be an operating principle for quite some time 🙂

Now, of course, Chess has a game tree complexity of about 10^123, which is why I say we can’t fully break Chess (which is why Kasparov didn’t lose them all). But in practice, Chess is a lot less complicated than Axis and Allies, even if you removed the dice rolling as the decision making methodology for individual combat resolution and ran straight off of some sort of numeric unit value computation.

I don’t know offhand what the game tree complexity limit is for binary computers, but someone has probably computed it for several different types of games, and I’d wager dollars to donuts that it is well outside of both the current capabilities of computational machines and their theoretical limits 🙂

A few points:

1) What is the reliability of the current estimate of the total amount of atoms in the universe? What are the odds that number is wrong? Look at the work of Alan Guth, who estimates that the ‘finite universe’ could be quite a bit bigger than the observable universe, on the order of 10^25 times larger. Seeing as how we haven’t figured out a way to leave *this* planet I am reluctant to believe that we can definitively say anything about the entire universe. 🙂

2) How in the heck do you know that we’ll hit some unbreakable computing limit? It’s just another problem to be solved. I *did* stipulate that we haven’t the computing power available to us *now*, but it’s very likely to be just a matter of time. The fact remains, however, that any game that disallows infinite choices must, by definition, be ‘crackable’ given sufficient computing resources. Your argument is that we’ll never have them. That’s a very difficult point to defend.

3) Your father was a hamster and your mother smelt of elderberries. Or something. 🙂

At the beginning levels, it’s amazing how many games of chess you can win with just a very little memorization. There are probably scholastic players who went their entire academic careers not really knowing how to play the game in any meaningful way, but they memorized a few trap openings and were able to win two or three games out of five with just that. And it gets even worse the better the competition gets. Against many opponents, the goal first and foremost is to get them “off of book” such that it’s just your skill against theirs rather than against theirs and their days and weeks of canned analysis.

Which is to say that I completely agree about chess being uninteresting in that regard. Human v. computer games are pretty pointless these days; I at least was a pretty good chess player, and I can’t even dream of beating an iPhone, let alone a computer with a meaningful amount of CPU or memory. Clearly human v. human five minute games are the only pure form of chess remaining 😉

“I never played him. All them patzers sittin’ around the park… waitin’ for him to go back there like Jesus. Me, I don’t give a !&1^. Put the clock on that mother@#*!… I’ll chew his ass up, just like the rest of’em.”

— Sam, re: Bobby Fischer.

re:

(1) : I will accept another number, provided you come up with it 🙂 In any event, it’s a very high upper bound, well outside the realm of the actual upper bound… given that as far as we know there is no current way to utilize all of the matter in the Universe in a computing device.

(2) : No, it’s not a difficult point to defend, it’s justifiably true given what we currently know about binary computing and the laws of physics. Of course, it can come about that someone could invent a subspace quantum computer that could surpass the limits of our current technology, absolutely… but betting against that huge of a paradigm shift isn’t “difficult to defend”, the converse is.

(3) : I know you are, but what am I?

Oh yeah?

Thanks for the link. You know there are worse things to be than an engineer. No?

The complexity of the atoms in the universe is quite an interesting comparison. A computer wouldn’t necessarily need all the atoms in the universe to analyze all the atoms in the universe. Its all about our favorite topic, your modeling fidelity! I do know the implied assumption that it was to parallel analyze every atom, but this is an interesting parallel. Some portions of the gameplay, like some portions of the universe could be analyzed separately. We could work from one side of the universe creating building blocks and work out at least one turn :D. But wait, where to start! Plus infiinty or minus infinity? Hooo boy! Anyway, that’s how my take was different. Of course, the analog to binary of trying to represent the positions and empty space blows orders of magnitude into the model beyond just the number of molecules. How much of space is homogenous and could be lumped….. Ouch. Head hurts. I started to defend Andy, but wow!

Oh, and Andy we can leave this planet, fuzzy Elderberry eating parents or no!