Hacker News Reader

Comment by Waterluvian | Hacker News Reader

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?

View on HN

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.

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.

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

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.

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.

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.

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

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.

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

Reply on news.ycombinator.com