Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Chess invariants

muratbuffalo.blogspot.com

Post reply on HN
Print view View original

51–60 of 67 posts

Re: Chess invariants

#51

Post by CSMastermind »

sobellian wrote: post #42

The historical rules also left ambiguous promotion to the opposite color: https://chess.stackexchange.com/questions/8291/pawn-promotio... . This rule was clarified later to restrict to the same color.

> The player’s choice is not restricted to pieces that have been captured previously

I grew up playing chess but my grandfather always insisted that pawns could only be promoted to captured pieces so when I played him we had to play a that variant.

I suspect this came from players not having extra pieces with their chess sets.

Re: Chess invariants

#52

Post by necklesspen »

teiferer wrote: post #47
arvyy wrote: post #43

Earlier quoted context omitted.

doubtful, or at least not useful ones. Like, you could describe some invariant along the lines of "the position is winning for the side-to-move, iff there exists move, such that position' := ApplyMove(position, move) is losing for the (now other) side-to-move". But that's just restating minimax algorithm that people have known for 50 years. As someone dabbling abit around chess engine development, I'm very often impr…

I agree it's hard and non-obvious. If it wasn't then chess would have long been solved by now. Let's start from the other end. Just a pawn and two kings. It's possible to describe some quite succinct rules for when that's a draw versus a win for the side with the pawn. Agreed? Club players know these by heart. You could write that doen as invariants. As long as the side with the pawn stays inside the "green zone" of…

You may want to take a look at the Shannon number, we would need quite a large neural net to solve chess in this way.

Re: Chess invariants

#53

Post by stymaar »

> apparently it wasn't until 19th century that people made clear that you couldn't promote a pawn to a King, surprising an attempted checkmate by responding Le roi est mort, vive le roi!

That's the coolest thing ever though, why would you ban such a move, where's the rule of cool when you need it most?

Re: Chess invariants

#54

Post by anthk »

pramodbiligiri wrote: post #31
fnord77 wrote: post #16

side question, which CS class(es) teach about invariants?

Usually goes under Formal Methods: https://github.com/luigiapetre/Formal-Methods-Courses There’s a book called Logic for Programmers: https://leanpub.com/logic#table-of-contents

A bit expensive. Just get Swi Prolog.

https://www.swi-prolog.org/

The Simply Logical book as a start:

https://book.simply-logical.space/src/simply-logical.html you can get a PDF just fine.

Also, for hardcore mode, get paper and pen, I'm not kidding: (again, just use SWI Prolog): https://www.ida.liu.se/~ulfni53/lpp/bok/

Another approach. Scheme and Logic:

S9 Scheme, get the bleeding edge version and compile it. Enough to do the book:

https://www.t3x.org/s9fes/

Sketchy Lisp, intro to Scheme:

https://archive.org/details/sketchy-lisp

Logic Progamming in Scheme: https://www.t3x.org/amk/index.html

Re: Chess invariants

#55

Post by TacticalCoder »

> It is a concurrent system, but with a very specific kind of concurrency: interleaved execution. More specifically, taking turns: white, then black, then white.

"Chess is a game of imperfect information, but with a very specific kind of imperfectness: fully available information. More specifically, ever single information is visible: you see all your opponents' pieces and he sees all yours, you see how much time he's got left, and he sees how much time you have left".

Who knew it? Chess is actually a concurrent game of imperfect information: with that definition, it's not unlike a real-time strategy game like Warcraft 3.

Who would have guessed it?

Re: Chess invariants

#56

Post by TZubiri »

0.01% chance you are a genius stumbling unto a whole new paradigm

99.9% chance you could have solved this in a couple of hours with some ifs and loops

Re: Chess invariants

#57

Post by somat »

TacticalCoder wrote: post #55

> It is a concurrent system, but with a very specific kind of concurrency: interleaved execution. More specifically, taking turns: white, then black, then white. "Chess is a game of imperfect information, but with a very specific kind of imperfectness: fully available information. More specifically, ever single information is visible: you see all your opponents' pieces and he sees all yours, you see how much time he'…

I sometimes dream of actual concurrent wego chess. It ends up a bit involved without a computer, each side has to commit to a move in secret(write it down on a pad) then comes the tricky part, a solid set of rules for situations that don't resolve cleanly under normal chess. stuff like collisions(do we bounce, halt, mutual annihilation?), pass throughs, escapes. I don't play much chess but it sounds like it could be a lot of fun.

Re: Chess invariants

#58

Post by gryn »

TacticalCoder wrote: post #55

> It is a concurrent system, but with a very specific kind of concurrency: interleaved execution. More specifically, taking turns: white, then black, then white. "Chess is a game of imperfect information, but with a very specific kind of imperfectness: fully available information. More specifically, ever single information is visible: you see all your opponents' pieces and he sees all yours, you see how much time he'…

huh ? where did you see the second quote, I can't find it the post. Was it there before ?

the game is very much a game of perfect information.

Re: Chess invariants

#59

Post by halfcat »

teiferer wrote: post #47
arvyy wrote: post #43

Earlier quoted context omitted.

doubtful, or at least not useful ones. Like, you could describe some invariant along the lines of "the position is winning for the side-to-move, iff there exists move, such that position' := ApplyMove(position, move) is losing for the (now other) side-to-move". But that's just restating minimax algorithm that people have known for 50 years. As someone dabbling abit around chess engine development, I'm very often impr…

I agree it's hard and non-obvious. If it wasn't then chess would have long been solved by now. Let's start from the other end. Just a pawn and two kings. It's possible to describe some quite succinct rules for when that's a draw versus a win for the side with the pawn. Agreed? Club players know these by heart. You could write that doen as invariants. As long as the side with the pawn stays inside the "green zone" of…

People have done this. They call it tablebases [1]. They’ve computed 7-piece tablebases, but not 8 pieces.

”After the completion of the 7-man, some people were curious about the feasibility of building the 8-man. Ronald de Man estimated that without modifying much the generator, the task requires computers with 64 TB RAM and 2000 TB hard disks[10] (cost about $640K and $40K respectively in 2020). The generator can be modified to work on much cheaper computers with 64 GB RAM but that may need a few thousand years of computing”

And to solve chess you’d need to calculate the 32-piece tablebases.

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

Re: Chess invariants

#60

Post by teiferer »

necklesspen wrote: post #52
teiferer wrote: post #47

Earlier quoted context omitted.

I agree it's hard and non-obvious. If it wasn't then chess would have long been solved by now. Let's start from the other end. Just a pawn and two kings. It's possible to describe some quite succinct rules for when that's a draw versus a win for the side with the pawn. Agreed? Club players know these by heart. You could write that doen as invariants. As long as the side with the pawn stays inside the "green zone" of…

You may want to take a look at the Shannon number, we would need quite a large neural net to solve chess in this way.

The Shannon number is about the size of the state space. What I am dreaming up here is to avoid explicit enumeration by succinct descriptions in the form of logical formulas which have the potential of cutting down the representation size dramatically.
Post reply on HN