When I play chess, being the amateur that I am, I sometimes find myself trying to discover what my opponent’s plan is, based on the moves she’s been making in the game so far. I rely on knowledge of past moves in trying to decide what the best move is in the present position.
However, I understand that a good player does not need to think about past moves in order to come up with the best move. Knowledge of the board position is all the information that is strictly needed in order to determine the best move.
I think this is true of all games with perfect information.
But what about games of imperfect information? I suspect that in at least some cases, knowledge of past moves is vital–past moves must be taken into account when determining the best next move. This makes a kind of sense; The opponent knows something the player does not, and it is entirely possible that the sequence of moves made by the opponent so far may serve to give clues–maybe even in some cases fully reveal–whatever it is that that opponent knows.
But is my suspicion correct? Does game theory have something to say about this?
I don’t know anything about formal game theory, so I’m just talking out loud here… but I think that there are a lot of games with perfect information in which you’ll commonly find situations where there isn’t an obvious best move, just a best move for your style or plan.
I don’t play chess, but I know that Go (the Japanese board game) is a perfect example of this. There are common sequences of moves which professional players memorize called ‘joseki’, which are often used because they’re viewed as giving neither player the edge. (Amusing anecdote: I once saw a fictional TV show about a 6th grader who was a genius at Go. The show was known for using published games that’d been played between real-life professionals to create their fictional matches, giving the show an authentic feel… but occasionally they would accidentally have their characters do something extremely strange. On one of these occasions the genius kid played out of joseki when he was ahead… I think everyone watching the show at that precise moment wanted to smack the writers. >_<)
Anyway, back to the point: Go takes an extremely long time to play when you’re good, and there are annual top-level competitions (so-called ‘title matches’) in which two players will often spend one to three full days playing each game. Because it’s so open, especially at first, even though you have perfect information it’s quite hard to predict what your opponent will do until you have an extremely good grasp of that person’s playing style.
Of course I didn’t mean to imply that any human being, by herself, could calculate the best move just from the current board position, for Chess, much less for Go.
But in theory (i.e., using a computer with some large but finite amount of processing power) the best move can be calculated from a chess board position without any reference at all to the past moves leading up to the present position, and this is true for Go as well–again, “in theory.” You can see that this must be true, if you notice that there are only a finite number of possible go games. A computer with a very large memory could have them all stored in a database. Then, whatever the current board position is, the computer just has to compare it to the database, finding all the possible games in which that position occurs. Some of these possible games may end in a win, some may end in a loss. The computer selects a move corresponding to the next move in that possible game which includes the present board position in it, and which maximizes the number of possible games that end in a win.
Well yes, and I know this isn’t the point of your question so I encourage you to stop reading if you’re not interested, but Go is notoriously difficult for computers to play. First off, the idea of giving it a database of games isn’t feasible for a truly dynamic AI; the number of recorded games played come nowhere close to covering the possible outcomes in an average game played between two novices. As such, most software tends to behave in a manner which is quite similiar to chess simulators: every ply (player turn) the computer will consider every possible immediate legal move against some predefined metric, then move on to speculating about the next possible move. The problem is that compared to chess Go has a staggeringly large number of possible moves, so the standard strategy of reconsidering every move on every ply is extremely slow. Wikipedia has a really great article at Computer Go - Wikipedia if you’re interested, and they give a nice list of challenges for software solutions:
Long time lurker, first time subscriber. Hello world.
The concepts you are talking about are discussed in the poker world. The two methods are exploitive play versus optimal play.
Exploitive play is focusing on the opponent’s mistakes and eh, exploit them.
Optimal play is the game theory best way of playing which does not consider the opponents mistake.
The authors of Mathematics of poker (Amazon link) favor the optimal play citing that you may give up some value by not exploiting but it makes you unexploitable, even if your opponent knows how you play it’s nothing he/she can do about it.
Exploitive play also have the drawbacks that it can’t counter when the opponent adapts and fixes the mistakes. Also you need a large sample of how the opponent plays until you can find out what flaws in their play they have.
It’s definitely true in contract bridge. The exact bidding sequence usually gives a lot of clues to what cards a person has. So it’s common, when deciding which cards to play, to think back to the auction.
I don’t know what game theory has to say about this, but interestingly in bridge, poker style “bluffing” is often frowned upon if the bid is wildly inconsistent with one’s bid card. For example, if your bid card says that you will open 1nt with 15-17 high card points and a balanced hand; and you open 1nt with a yarborough, it’s usually considered bad form.
Yes, since bridge is not a ‘full information’ game like chess, you do need to use deduction on what the opponents have bid and played.
So if one opponent opens 1NT (showing 15-17) and you and your partner outbid them, you would use the information from the bidding in the play. Given there are 40 points in all, if you and your partner held 24 points, then the silent opponent must have 1-3 points.
Or if one opponent opens with a pre-emptive bid, then they usually have 7 cards in their suit, which may well be useful to know in the play.
Bluffing in bridge is called psyching, and is controlled. If the partner of the psycher benefits because the psycher usually makes the same bid (and the partner expects that), then those of players can be punished with a bad score.
I confirm that a strong chess player can analyse a position, without knowing the history, and come up with two or three likely best moves (plus plans for each of them).
However it is also true that you can try to predict which of (say) two reasonable alternatives your opponents will play, based on their previous play.
I used to play a variation of the French Defence as Black , where the same position was reached at move 4:
A
e2-e4 e7-e6
d2-d4 d7-d5
Nb1-c3 d7xe4
Nc3xe4
B
e2-e4 e7-e6
d2-d4 d7-d5
Nb1-d2 d7xe4
Nd2xe4
Later on in this variation, White got the chance to castle on either side. Players of variation A usually prepared for, then went Q-side (OOO), whilst B players went K-side (OO).
I’m plenty interested in the subject you’re discussing. And if others reading this thread are discovering the game because of what you’re writing, that’s great. I’ve been playing for ten years, myself.
By the way, in the last Scientific American there’s an article about Go playing computer programs. There’s apparently a new one that can beat some pretty strong players. I forget the details, but I’ll try to look it up for you.
Go is a much more interesting game for research into AI precisely because it’s so incredibly complex. You just can’t do brute force searches, even of just a few moves, with our current technology, or with any foreseeable technology. So you have to figure out how to write a program which can recognize the kinds of patterns people recognize when looking at a Go board. You have to teach it “shape.” (A term used by Go players for a set of smallscale configurations of Go pieces, each of which is known as a rule of thumb to be good or bad for particular purposes." You have to give them a feel for “pressure,” (Go players often talk as though go pieces were pushing against each other, which is strange since the pieces don’t move once placed on the board. But there’s something right about the term, and its a concept important to good game play.) And so on.
Of course, chess playing programs have some analogous higher-level concepts in their arsenal as well, but with Go you have to do this even more, and the nature of the concepts is more difficult to spell out to a computer.
Go is a great subject for exploring human and AI cognition. Of course, to be clear, as you noted, that’s not what I’m asking about. But that doesn’t bother me. I just want to be sure the topic of my own OP doesn’t get drowned out.
It’s possible to imagine a game of perfect information where the set of legal moves depends on both the current state of the game and the history of states since the beginning. In that case, you certainly do need to know at least some of the past moves to determine the optimal strategy. In fact, if you play chess with the rule that repeating the same board position three times leads to a stalemate, then it is such a game.
I’m not familiar enough with bridge to know if it qualifies under the OP, but euchre definitely does. Knowing which cards have already been played makes a huge difference for what you should do with a given hand.
In a sense, though, it seems like we should consider information like whether the king has moved in the past to be part of “the current board state”, as if there were a flag on the board to indicate such things. But then, once you get to defining things this way, where all the information available to both players is considered part of the current board state, then I suppose the problem becomes trivial (since any past moves I know of my opponent’s must be part of the shared information).
I can’t find anything online, but you may be looking for the difference between static and dynamic games. Fudenberg and Tirole is a good place to look.
As I understand it, static games are things like rock-paper-scissors where both players pick moves separately, which are then revealed simultaneously, from which the outcome is determined, while dynamic games are things like chess, where players take turns making moves, responding to whatever knowledge they acquire of their opponent’s moves, the outcome eventually being determined from the total sequence of moves. Is this correct? [I suppose we could treat any dynamic game as a static game, by thinking of it as “Player 1 chooses a strategy, Player 2 chooses a strategy, then the two strategies are pitted against each other to determine the outcome”]
To answer the OP’s question, though, it still seems like we need a clear definition of what the board state means, in general, for arbitrary (dynamic) games, or, more specifically, what information at a player’s disposal can be considered available to him even once deprived of any knowledge of his opponent’s past moves. It seems to me that a given game (as specified by its game tree or something like that) could be analyzed from various different perspectives; for example, consider the two extremes: we could consider chess played on a board on which was always written down all information about past moves, in which case one would of course not need to rely on any memory of them, or we could consider chess played without any pieces placed on the board at all, players merely shouting out their moves in turn and relying fully on memory of past moves in order to play competently. These would both be identical games, in terms of having isomorphic game trees, but, presumably, they would have different notions of board state, and thus would be different in terms of the context of the OP’s concerns. If we allow things like this latter “boardless chess” with its trivial notion of board state, then, clearly, the answer to the OP’s question is that “Yes, you may be required to rely on knowledge of past moves.” But perhaps the OP (or others) feel there are certain reasonable restrictions on just what we can consider to be the board state for a given game.
I think one of the big problems with teaching a computer to play Go is that a lot of the important minutiae are extremely abstract, and often require conversation between the players to resolve.
Actually, there’s a really wonderful game of Go I’m trying to remember… I seem to recall that it was an official game in 1997 played between two high-ranking professionals, one from Korean and one from Japan. As is usually the case in high-level games, it ended with one player only 0.5 points ahead of the other. (For anyone just learning about the game, to offset the huge advantage of moving first the player who moves second always receives extra points called Komi, to offset this advantage. Komi differs from country to country but it always contains a half point, to prevent ties from occuring.)
Now something extremely strange happened at the end of the game: as usual, both players decided that nothing more could be gained from continued play and mutually agreed to end the game and count up their points. Go has a concept called “Life and Death” wherein, if the game reaches such a point where one player can’t possibly prevent the loss of some of his pieces, it’s traditional to continue play elsewhere without his opponent actually capturing said pieces. However, they are considered “dead” and when the final score is counted up, the player who was in a position to capture said pieces earlier will count all of his opponent’s dead pieces in his final score. Sometimes it can be hard to agree on what’s dead and what’s alive, so it isn’t uncommon for players to discuss the score as they tally it, coming to agreements on what is dead and what isn’t. (Official games also have officials who can make formal judgements, should there be a disagreement or ambiguous case.)
As expected when the points from this game were counted up, the winner was leading by a scant 0.5 points… but a really big problem arose as they were discussing things: at this point in time, Korean and Japanese rules utilized different Ko rules, and both players had been under the assumption that a single open square was their point. Each player’s rules did correctly assign the point to that player… and there was absolutely no precedent for this, so the officials were unsure what the correct manner of deciding a winner would be.
I think something the OP didn’t necessarily consider is that given a full set of all possible games, there might be several moves that are all equally “best” for a given board. There is no guarantee that there would only be one best move per board position. Choosing among these equally good moves within context of how you would expect your opponent to react to them is advantageous over picking one randomly. To do so effectively you need to have information on how your opponent reacts to what - i.e. past moves in this game and records from past games.
I not very good at chess, and know nothing about Go or Bridge, but I know a little bit about game theory.
Keep in mind, that if you could actually learn something from an opponents previous plays, said opponent could play to trick you into thinking you have learned his strategy, when in fact you haven’t
In game theory, convincing your opponent that you’re irrational, when in fact you are not, is a very valuable tactic.
My cursor surreptitiously passed over this as I idly checked my subscribed threads, and, in the way that Firefox sometimes does, the popup for this thread actually came up even as I was in another window. It read “When I play chess, being the amateur that I am, I sometimes find myself trying to disco…”. I couldn’t at first realize where that could have come from, and the confusion and resolution were so beautiful that I simply had to share.
