Chess, unlike war, is a game of perfect information | Hacker News Reader

Chess, unlike war, is a game of perfect information

daily.jstor.org

73 pointsitem76 comments

Chess belongs to a class of games that are particularly interesting to study: it is a finite extensive form game which basically means the game can be modeled as a tree and requires only shared knowledge among participants, all the participants have complete shared knowledge, it’s sequential, has perfect recall (nothing prevents looking backwards at the game state), and a simple payoff function (you win if you checkmate the opponent, in which case the opponent also loses) that is zero-sum.

This makes it so chess has a one-shot sub game perfect equilibrium: https://en.m.wikipedia.org/wiki/Subgame_perfect_equilibrium. But, the dimensionality of the possible end states is very high, because there are many different configurations leading to a checkmate, so you can’t easily perform backward induction. But you can perform minimax (which is how Stockfish works): https://en.m.wikipedia.org/wiki/Minimax

From a game theory perspective chess is really not at all like an actual war, because the properties of the game are different in almost every conceivable way - not just because of perfect information. But, you can model more complex “games” like war in a way that makes them more similar to chess if you wish. Just be careful because ignoring very fundamental differences like the payoff model could greatly affect decision making - for war, you’d probably rather surrender or make minor concessions in most cases than win at the cost of 99% of your people and infrastructure getting destroyed.

>But you can perform minimax (which is how AlphaZero works)

AlphaZero uses Neural Networks, old engines used to use Alpha-Beta pruning if I am not mistaken but after 2017 (the year AlphaZero papers were released) they started using a combination of the two or just NN.

Chess Programming Wiki [1] is an awesome website if you want to learn how Chess engines work in detail (or write one).

[1]: https://www.chessprogramming.org

The neural networks are for the evaluation at each node, traversing the game tree is done by using the NN to evaluate how good the position is on the tree’s nodes; how it traverses the tree is minimax with a-b pruning.

In my original comment I didn’t mention pruning or other heuristics like estimating the value of intermediate states because it’s more of an optimization (a very important one!) that doesn’t affect the theory very much.

Ah, ok, so Minmax/Alpha-Beta to traverse the game tree and NN to evaluate, my mistake (apparently I am the one who should visit the link I provided :)

No, it was I that was too lazy to visit the link, or we both were. I got alphazero and stockfish’s implementations mixed up

AlphaZero uses Monte Carlo Tree Search not MinMax. So it does use a neural network for the search. Modern Stockfish is the one that moved to having a neural network for position evaluation while keeping MinMax with AlphaBeta and heuristics for the search.

Oops! You are right, I got alphazero and stockfish mixed up.

Nitpick: MCTS is a heuristic search algorithm as well (just like minimax) that doesn't necessarily need a neural network to operate and the MCTS algorithm existed way before AlphaZero, coming from Reinforcement Learning literature. Deepmind's innovation was to replace two of the 4 classic steps of MCTS (selection step and simulation step) with neural network-based policy and evaluation network.

That's a good nitpick. In recent computer chess discussions MCTS is usually shorthand for the search that was novel with AlphaZero and then copied by LeelaChessZero. But you're absolutely right, MCTS doesn't even need to imply a neural network.

The article doesn't touch on this, but Sun Tzu famously wrote about the importance of spycraft in his The Art of War. It actually completely changed my outlook on what it's like to truly go at war (from a macro standpoint). The salient advantage often lies not by knowing what's on the battlefield, but rather what's behind enemy lines. Being able to sow dissent, for example, can be way more of a force multiplier than outnumbering the opponent on the field. And, in this regard, Chess (where number of pieces is vitally relevant) is absolutely nothing like war.

> Being able to sow dissent, for example, can be way more of a force multiplier than outnumbering the opponent on the field.

Not even just dissent, eg despair used to generate an advantage in morale can be incredibly powerful.

Alternatively misinformation can push you towards bad tactical decisions.

In the same vein: in chess, all your forces are present, and have all they need. So it's more like a skirmish than a war. In particular, wars can be won or lost not only by intellectual disruptions behind the lines, like drops in morale due to propaganda, but also because of supply line issues. Brett Devereaux's ACOUP blog has a great write up on this re the Romans and the "tyranny of the wagon equation"

I find it fascinating how Chess is, in a way, stateless. Other than whether some rules like castling are still valid, you don’t need to have played the previous moves to be able to play the next moves effectively.

This got me thinking: is that common in games? If I take someone’s place at a Risk board, can I play well?

But in both cases, there is perhaps still some state… At least if you’re playing a human. You might be able to get a feel for what’s on their mind. Where they’re going with the game. What overall strategy they’re working on. And that can inform what comes next.

But is that just a form of gambler’s fallacy? Would an AI have a natural advantage if it made optimal moves given current state rather than being attached to a “plan”? Is the “plan” just an abstraction so you don’t have to re-analyze the board every time? Or is the “plan” some sort of advantage?

If you take into account player behavior dynamics, then I think path to a state becomes more important. I.e. "what my opponent thinks I'm trying to do" becomes important information to keep track of. Maybe not the case with chess, but definitely in other games.

This is called recall and it’s an important factor in “strategy profiles” for games with unshared information

I don't believe stockfish cares about past moves at all besides castling/en passant. It's able to evaluate a board so effectivly that it doesn't need it.

And repetitions. You may need to store 3x or 10x or in degenerate cases 100x the game state in order to check if the game may end by threefold repetition.

A standard optimization in chess engines is to treat a single repetition as a draw, while in competitive rules the position must be repeated twice in order for either player to claim a draw.

This works fine for playing against an infinitely good opponent, or against a clone of itself, which is how engines are usually tuned, because the repetition will be made if and only if the best evaluation under minimax is a draw, in which case a second repetition will also be optimal.

But it's not maximally exploitative against a weaker opponent. It's possible in some positions to give the opponent the choice between repeating moves and making a mistake: you can do this "for free" by giving the opponent this choice and then playing a different continuation if the opponent correctly chooses to repeat. And when annotating a human game, this bug will cause the engine to scream that the human blundered if he allows a single repetition in a winning position, whether for this reason or to gain time on the clock.

>At least if you’re playing a human. You might be able to get a feel for what’s on their mind. Where they’re going with the game. What overall strategy they’re working on. And that can inform what comes next.

Every decent chess player is able to take over any position, there is no need to communicate the plan being worked on, you look at the board, you evaluate your and your opponent's strengths and weaknesses, and a plan (or even plans) should show up, assuming the game is not a dead draw, the evaluation of course differs from one player to another, and consequently, the continuation.

Time constraints are a bit of state that can influence how both humans and engines how search for moves. There was some contention over how to understand the training time of AlphaZero in relation to more conventional engines - even as just a physical process this seemed pretty interesting.

I'm not sure about the plan (that takes time of course), but playing styles are quite different.

I as a beginner try not to give my bishops for horses, but more advanced players adjust it to the strategy they want to persue.

Some people have more experience in open, others closed games.

There are lots of other simplifications beginners have to make to be able to not get totally lost.

I don't remember the exact mechanics, but Risk has cards that each player holds. If nothing else you'd probably want to see how many of them each player holds to plan the next move.

Yes this is common, it happens in all finite extensive games with perfect knowledge

> take someone’s place at a risk board

Not the case because Risk has unshared knowledge (the contents of your cards) and taking someone’s place makes it so the game doesn’t have perfect recall. You need shared knowledge and perfect recall, or complete knowledge (in which case recall doesn’t really matter) for a game to have a sub game perfect equilibirium - in simplified terms, for there to be an optimal strategy that applies equally well regardless of the game’s prior events.

That might be hard to reason about with Risk, but consider how information “leaks” by when players choose to use their cards or not and when they received the cards. Having a card for a long time but not using it suggests something else than having just received the card, which is why perfect recall is important. For a game to be “stateless” (ie have a one shot sub game perfect equilibrium), when cards were received would also have to not be important, but it is in Risk.

I think technically you don’t even need to tell others how many cards you have (of course you have to comply with the hand limit). But it is weird because normally everyone sees when you get a card, so it is just a bit of bookkeeping to notice when someone gets behind a card.

More interesting I think is knowing when a player has been holding their cards for a while.

There's a lot of games where the "State" is important the most obvious of which being poker.

In a game of poker you can devise a game theory optimal strategy for any given position which is objectively the best, but that's not what most players do. They try to mix in exploitative strategies which abuse the tendencies of their opponents. These tendencies are revealed after extensive experience with the players.

There is an aspect to this in chess as well, you can treat the best move as the one which is objectively best (Game theory optimal, as evaluated by chess engines usually), or you can treat the best move as the one people in general have a hard time responding well do or that your opponent doesn't play well against (Exploitative, as evaluated by opening database statistics or a players history). Yet once a tricky opening becomes popular, people wise up, and it starts becoming a bad opening again. Whereas old traps become forgotten and effective again. Whereas objectively good moves are always objectively good.

Another huge aspect to winning the game is just playing against bad players. In chess players your performance is rated based on the rating the other player, so you shouldn't fear playing games against a stronger player. In Poker your performance is measured in dollars, and you should absolutely fear playing games against a stronger player. So to be most effective in poker, you want to know the history of the people you're playing, which is why poker tools like sharkscope exist which tell people which tables are filled with historical winners.

You can play games in a stateless way and do pretty well, and the benefit to doing so is you learn skills that work against anything from the weakest to strongest opponents and allow you to play objectively good moves. But adopting a few stateful strategies can absolutely give you an edge against squishy humans. You can play the board, or you can play the player, at the end of the day all that matters is who won and who lost.

> They try to mix in exploitative strategies which abuse the tendencies of their opponents.

without knowledge of other players, how do pros wins consistently at casinos?

The longer you're at a table with somebody, the more information you learn about them. If they're a weak player, if they're a strong player, if they're too aggressive, if they're too passive, if they play with crappy cards, if they only play with good cards, if they have a tell.

When you don't know much about the other players at a table, you tend to not use exploitative strategies as much and reply more on game theory optimal strategies and just play the cards you're dealt while you quietly gather information on your opponents tendencies so you can play the players. This might be enough to win on its own, or at least be good enough to just break even, presuming the other players are making enough mistakes.

Disregarding rake or table costs, the Game Theory Optimal strategy for a poker variant will always (on average over time) take money from all players who aren't also playing a GTO strategy.

It would only break even (again, disregarding rake or similar table costs) against another GTO strategy, and there's no way casual players, which is where the money enters this system, would play a GTO strategy. You're lucky if they remember all the rules of the game without prompting from the dealer.

For real poker variants, humans can't play an actual GTO strategy because it's too complicated. http://poker.srv.ualberta.ca/ provides an essentially perfect derived GTO strategy for Heads Up, Limit Texas Hold'em. It's... a lot, trying to "simplify" it will make it leak money (where Cepheus takes option A 62% of the time, B 38% of the time, simplifying to fifty-fifty will lose a little money) and trying to "improve" it (e.g. let's take on more of these potentially weak opposing hands) is likely to open gaping holes in your play that can be exploited by others.

Yeah this is all true, I’m talking pragmatically to a huge extent here since humans don’t and can’t play perfectly and they do play at raked tables. You can’t exploit perfect play, you just end up being the one getting exploited.

Your intuition is actually proved mathematically for two-player games of perfect information (even for infinite games), in which chess is included, by Wolfgang Schmidt (Theorem 7 in https://www.jstor.org/stable/1994619). Roughly speaking, if a two-player games of perfect information has a winning strategy (which might need all previous moves of a play to make decisions), then it has a positional winning strategy, which only need the current state/position to make decisions. The `only` requirement needed for that theorem is the Axiom of Choice / Well-ordering Principle.

It's not 100% stateless though: Did the king already castle? Did the pawn just pass me for an en-passant?

Which is why those balance patches were ill-advised and should be reverted for the next point release.

Bridge is the ultimate game of war, where you need to analyse every single risk, work out combinations, strategise and come up with a reasonably aggressive plan of attack.

Some of the contests, you just cannot win, and all you can do is to try to minimise the damage. Some, you are almost sure to win, and is no fun playing. Close contests are thrilling, and upsets are exhilarating...

In interviews, (US) General Stanley McChrystal has said he prefers backgammon to chess because it involves both strategy and chance.

Poker would've been a better choice because of the imperfect information and bluffing.

I wonder what chess would be like if it incorporated a fog of war mechanic where you could only see some tiles around each piece, and perhaps rooks could see a straight line all the way down the board.

You can try this on chess.com: https://www.chess.com/terms/fog-of-war-chess

You mean like Strategos?

I experimented with building in something like that into RPG mechanic. It's not so simple as modelling "fog of war" as uncovering terrain like in real-time strategy games, but rather, perception roll checks and modeling morale, discipline, and simulating things like tunnel-vision.

Is that the UK name of the US game "Stratego" ? Yes, a deceptively(?) simple board game that incorporates imperfect knowledge.

Not the UK spelling — a typo.

You might like Reconnaissance Blind Chess [0]. It incorporates imperfect information into Chess and was developed for AI research at the Applied Physics Lab.

[0] https://rbc.jhuapl.edu/

Interesting, one who makes an account to post about reconnaissance blind chess. Are you involved in it a lot? I know some who are post here.

Ha — I was thinking the same. I am not involved, unfortunately. I studied political science at Johns Hopkins during the time RBC came out though and always thought it would make a great canvas for a deeper exploration of, broadly defined, strategy; deeper than you’re conventional polsci game theory allows. But it stayed a hunch, or an intuition…

My thought here is that perhaps the hidden information on a chess board is in the mind of the player.

Time is also a factor - in speed chess you only uncover as much as there is time to.

And don't forget sacrifice. Not sure if AI or Stockfish or ... can emulate sacrifice for material advantage.

I learned to play chess almost 40 years ago. Just started playing last month and it is amazing at the amount of information, studies, theory and gameplay that is out there.

I jokingly understand this quote now:

"The ability to play chess is the sign of a gentleman. The ability to play chess well is the sign of a wasted life." - Paul Morphy

There's one match in which it was not a game of perfect information, as Garry Kasparov says in "Deep Thinking: Where Machine Intelligence Ends and Human Creativity Begins":

If you consider "perfect information" to include "knowledge of your opponent's previous games" (that's a big IF) then he did not have it against Deep Blue. IBM refused to give him any insight into what he was up against.

I don't think that's a very convincing argument, in game theory you are not supposed to be helping your opponent out, except in some very specific scenarios that usually involve zero and/or one probabilities or infinities, so they don't apply to real life. Using minimax in a non-infinite iterated game like chess, with the standard goal function, I don't think it ever happens. Winning is the optimal strategy every single time. You don't owe correct and useful information to your opponent, in fact it is against the goal function. All iterated games in the real world have a first game as well.

> All iterated games in the real world have a first game as well

not really. Any opponent you face in a serious tournament has played before. If he's played in major matches, you have his games to study, so he's not "helping" you.

Experiment: A plays B, in two different scenarios, one where A knows all of B's prior games, and the other where he doesn't even know it's B. in which scenario would A do better?

Right, but if not playing before or playing differently before increases the chance of victory, that's a good thing in the utility function. For example, even in a non-infinitely iterated true prisoner's dilemma, defecting is the right move. In an infinitely iterated one it's probably not, but that requires pretty sophisticated decision theory, including acausal or backwards looking analysis. In a standard forward looking minimax, when applied to chess, you can use an arbitrarily sophisticated evaluation function, and that function can model the psychological state of the opponent, potentially causing the opponent to have no prior knowledge of your games, or changing your play style or using surprising moves. In addition, I don't think any external force would prevent this action, as top players in the real world have used similar strategies and were able to continue playing more games. If Kasparov thinks you are required to waste your first game on a weak player, he is mistaken.

You know, this reminds me of one of the few Economist Jokes I know, where the economist hears of a previously-unknown real world phenomenon:

"That's interesting. It works in practice, but will it work in theory?"

the other one, since you wondered, is:

Two economists are walking on the sidewalk and spot a $100 bill. One bends down to pick it up, but the other stops him and says, "That can't be a $100 bill. If it were, someone would have picked it up already."

I'm a $100 bill picker-upper. The efficient market hypothesis is false.

Actually, to be a bit more clear, let's say you are well compensated and a $100 bill is worth 99 USD to pick up excluding outside factors. You would calculate in USD 99 - (expected loss from ambush|picked up + expected loss from arrest|picked up + expected loss from police harassment|picked up + expected loss from mob|picked up + expected loss from lawsuit|picked up + expected loss from stress|picked up + ...). I guess at that point the stress from doing the situational analysis and calculation is sunk, so you should pick up the bill if the previous calculation gives a dollar value above 0. I personally would just quickly put on gloves and check for possible ambush scenarios, and then just pick it up. If you do the full calculation at the time, someone else might get it before you. If you do most of it ahead of time, you can commit to the likely optimal decision. You need to calculate the value of your time and the value of your life in US dollars, taking into account that inflation may not work how you intuitively think it does.

way to ruin a joke.

> All iterated games in the real world have a first game as well

They effectively don't, because the way things work in the real world is that you become known to the competitive scene long before you reach a top level tournament and people will have definitely played against you in some capacity.

If you could somehow become a top pro without interacting with the rest of the scene, then you would most definitely have a massive advantage against other top pros for a little while before they figure out your tendencies.

This is based on my experience and knowledge of real-time games like SC2 and Dota, so it may not be as applicable to Chess since the action space is considerably smaller and I don't know if knowledge of opponent tendencies is as important (I assume it is though).

I wouldn't necessarily agree all of this means it wasn't a game of perfect information, but the first match of an iterated game in the real world is almost always either inconsequential or you have access to information from a secondary source.

Thanks, my joke about "will it work in theory?" is kinda on point here:

I don't think it's any slam at game theory to say that it doesn't represent the real world perfectly. It's an approximation.

It's also a game of instant information, unlike war where generals hear about events with some delay. Or at least used to.

Even with modern technologies and the surfeit of information, it's still not a perfect-information situation. If the cosmos is a computational engine, only the cosmos has the possibility of perfect-information. Everything else is a representational model.

Messing with that information is one of the ways one side can gain an unfair advantage, and why such concepts like OODA was developed.

The article is not related to the title in the mathematical sense that the HN context and JSTOR URL would suggest. It's a literary history of chess (or a chess history of literature), and article not a research paper.

You don’t play chess against an opponent, you play it against your self - can you find the best strategy for the other side and counter it

Bughouse chess, unlike chess, is real-time, and symmetric.

i'm not so sure it gives you perfect information - it doesn't allow you information about what your opponent is trying to do.

In practice, Chess is not a game of perfect information, since you generally don't know which lines your opponent has prepared beforehand.

that doesn't matter, you have every bit of information from the board to in theory know every possible outcome. It's not like the opponent can't sneak an extra piece in behind your line. Or randomly turn your rook into their queen...

>in theory know every possible outcome

Does your theory model the maximum possible compute of a player and the amount of time they have to spend computing these outcomes on a turn? People have a finite amount of time to make moves or they lose. Even computers can't explore the full search space.

Trivializing the combinatorial explosion of each move is not useful for a chess strategy.

"Perfect information" is a term of art for games, it doesn't literally mean you are omnipotent.

Is it a particularly useful term here? It seems to mean you could theoretically play perfectly but in almost every real situation you can't, which is true of every human activity (including war). Information is hidden by complexity, but it's still utterly inaccessible.

You know the entire state of the chess board. You don’t know the entire state of your enemy forces. I’m both cases information could be said to be hidden by complexity, but in the case of war information is also just plain hidden.

Edit: it would be similar to your example of war if you e.g. couldn’t see their pieces or something that would cause information asymmetry. This would make the game very different so clearly the term of art _is_ useful and important.

I suppose my problem is that the term 'perfect information' doesn't really communicate anything really interesting about chess. Whereas the equally valid term of art 'incomplete information' actually does, because it captures the fact that you lack knowledge of your opponent's strategy, but nobody ever uses that term. Chess is like navigating a maze or a minefield, it's like stumbling into an ambush. It's much more like war than tic-tac-toe.

> I suppose my problem is that the term 'perfect information' doesn't really communicate anything really interesting about chess.

Yes it _does_ communicate something interesting. It is a basic fact about the rules of play. If there were imperfect information, it would be a different game. Poker with perfect information means everyone plays with their cards up. It is a fundamentally different game.

The fact that chess has perfect information for all parties is fundamental to the game.

And while I understand that you’re coming at this from a technical standpoint and I can’t argue with the definition, I still think on a human level chess is more like poker than tic-tac-toe (because you’re spending a lot of time imperfectly filling in gaps in information about what your opponent could be up to), and so the category defined by this technical term isn’t so useful in a human conversation such as we’re having, with no prizes from technical correctness. I’m not really interested in repeatedly restating the definition, I’m saying it’s not a good signifier for the differences between chess and war. Maybe that’s not interesting to you, but it is to me as a player and designer of games! And on a deeper level I suppose I’m guilty of exactly the same thing because this is a thread about poetry anyway. :P

Eh, no longer really enamoured by these thoughts, because that's really what's interesting about almost any game, but somehow I still bristle whenever people bring this up about chess.

Exactly. In particular, "perfect information" means you know all the strategies available to your opponent. You also know that your opponent knows this. And you know that your opponent knows that you know that your opponent knows that you know all the strategies to your opponent ad infinitum symmetrically.

In this context, a strategy is a function that maps every history of moves by you and your opponent to an action. So, while chess is theoretically a game of perfect information, in practice it is less so.

Real war is not a game of perfect information, because you do not know all the strategies available to your opponent. In addition, you and your opponent's priors may have an intersection of zero measure which makes things very interesting.

War is what happens when a certain kind of people try to play the game of chicken which is usually not taught in the kind of fun programs like master's of international studies for members of the preferred party because it is too sophisticated due to the fact that it admits an infinite number of Nash equilibria ... instead, such programs prefer to focus on prisoners' dilemma which, having a dominant strategy equilibrium, is more suitable to ensure such students can go back to the bureaucracy after having passed their classes with perfect As and get us in to war.

> In practice, Chess is not a game of perfect information, since you generally don't know which lines your opponent has prepared beforehand

What do you mean when you say "game of perfect information"? What would be an example of one?

https://en.wikipedia.org/wiki/Perfect_information

Yes, but according to that definition, Chess is a game of perfect information. So I’m wondering what definition the person I replied to is using, since their claim was that Chess is not a game of perfect information.

There is some truth to this.

In theory, chess is a game of perfect information.

But in practice, this is only true for ~6-piece endgames: every outcome has been / can be computed. But for any middle- or early-game position, the amount of finite information greatly exceeds any person's or computer's capacity, practically speaking.

In concrete terms, the tablebase for 6-piece endgames is ~150 GiB. For 7-piece, it's 16 TiB.

[1] https://syzygy-tables.info/

Reply on news.ycombinator.com