How many distinct chess games are possible, and which is the longest?

Sort:
kiloNewton

ok. how many 8 queen solution do you have? (place 8 queens in such a way that one cannot attack another)

Benzodiazepine

"8 queen solution" - doesn't say much, if anythign, to me

Who has 8 queens? Black, white or both?

SeanEnglish

Kilo, are you asking on a labelled or unlabelled board? what I mean by that is would you count these two positions as the same:

even though one is just half-turn rotation of the other?(if you count them both as one, you're counting unlabelled boards, if you count them as two, you're counting labelled boards)

Iluvsmetuna

Chess is such a pointless game that it spawns such questions.

SeanEnglish
Benzodiazepine wrote:

"8 queen solution" - doesn't say much, if anythign, to me

Who has 8 queens? Black, white or both?

Benzodiaepine, There is a famous(albiet rather easy) chess problem called the "8 queens problem". Starting from a blank board, can you put 8 queens on the board without any of the queens attacking eachother?(look at post 151 for an example) So the answer is definitely yes, but there is more than one configuration that acomplishes the task, so now Kilo is asking how many configurations(or how many "8 queen solutions") are there?

kiloNewton

>"are you asking on a labelled or unlabelled board?"


its better to count mirrors as unique. otherwise it'll take a lot time in finding mirrors. so count 4, for position like this:

if you count seperately like this, there are 92, 8-queen positions!

SeanEnglish

ah yes, 92 for a labelled board, and google suggests that there are 12 on an unlabelled board. I wonder though if that 12 is on an unlabelled and uncolored board, or just an unlabelled one(an uncolored board says a quarter-turn is the same, where as a colored board, a quarter-turn would give you two positions). I'm assuming unlabelled and uncolored. If it is unlabelled and uncolored, for each "pure solution" there are 7 symmetries(corresponding to the dihedral group of order 8[also known as the dihedral group on four vertices, depending on which context you are considering it{usually algebraic vs. geometric contexts}])

kiloNewton

ok then, lets play a vote game. Vote A or B

Ques: Which is more attractive of the following two?

A) Iluvsmetuna's pic 

B) these "pointless" puzzles

SmileSurprisedTongue OutYellCoolEmbarassedFoot in MouthMoney MouthFrown

SeanEnglish

Here's a nice spin on the 8-queens problem...

How many independant queens can be placed on a 64-square cylinder board? what about a 64-square torus board?(if you've never seen how to think of a chessboard as a cylinder or torus, here is a nice link http://webserv.jcu.edu/math//vignettes/Mobius.htm )

SeanEnglish

ahh, I thnk I just realized that as far as queens are concerned(due to their indifference to distance), a torodial board and a cylindrical board are the same(in the sense that for all squares, the set of all neighbors of that square[places a queen can move in 1 move] are the same regardless of if it is a cylinder or a torus), so my two questions are actually only one.

kiloNewton

What about a 3D 8x8x8 board? it will consist of cubes. pieces will move in 3D. i.e. a Rook can move in x,y and z axis.

for a king, its like outer cubes of a rubics cube, while the king is in the centre?

 

This kind of board is difficult to build in real. but computer simulation can make it easy. i think it will be more popular than current 2D chess !

SeanEnglish

Kilo, why stop at three dimensions? if chess can be brought into three dimensions, it ends up it could be brought into any number of dimensions. two dimensional chess is hard enough, but could you imagine the complexities of 6-dimensional chess?

kiloNewton

if we can play 3 dimensional video games, why we cannot apply in chess?

SeanEnglish

Kilo, I'm agreeing with you(not trolling even though it might seem like I am). We can play 3-dimensional chess and even n-dimensional chess. There's no reason to stop at 3(other than going above 3 can be very confusing for people who haven't worked in higher dimensional spaces). Granted, the level of complexity involved in 6-dimensional chess(or even 3-dimensional chess) would be high enough to dissuade all but the most adventurous of thinkers from playing, but it is still quite feasible. 

kiloNewton

moreover, at some point we can play multiverse chess? i can't think what the rules should be.

SeanEnglish

Kilo, you can visualize n-dimensional chess(n>3) in two ways... either algebraically in which all "squares"(actually hypercubes) are considered ordered n-tuples with entries taking on 8 values(as a set it would look like (Z_8)^n or the direct product of n copies of the cyclic group of order 8) and movement can be defined by vectors a.k.a. a king on "square" a can move to square b if there exists some vector c=(0,...,1,0,...,0) or c=(0,...,1,0,...,1,0,...,0) or c=(0,...,1,0,...,-1,0,...,0) such that b=a(+or-)c
All other pieces movements can be defined simiarly.
[editactually if a king's movements can be modeled by the exerior of a rubik's cube in 3d chess, then in n-dimensional chess, a king can move from a to if there exists any vector c with entries that are all zeros, and (+or-)1s not just vectors that have one or two ones in them.] 

Or you can visualize n-dimensional chess(n>3) using the following trick: to get from 3d to 4d chess, put 8 3d boards in a row. each piece can either move inside the board they're currently in, or can move in between boards as if that was another direction of travel.

Once 4d chess is visualizable(the only tricky part is figuring out what "diagonal" means in such a context), then going to further dimensions can be achieved by just repeating the process of going from 3 to 4. 

SeanEnglish

Greensleeves(good melody btw),

 that depends a lot of how you define "moves". If you consider the number of legal algebraic formulas(aka Nf6 is a legal algebraic formula but axc5 is not since a pawn on the a file cannot take something on the c file), then I believe this is less than 10^50. If you consider the number of possible moves by any piece on any square(to be more precise the number of ordered pairs where the entries come from chess boards with only one piece, placed anywhere it could be in a legal game with pawns given the freedom to also move how they capture to make sure their potential captures get counted, and in which the second position can be gotten from the first position from a single move of the piece), I think this is still a lot less than 10^50, but if you consider a move to be any transition from one legal position to another from a legal move(aka the number of ordered pairs with entries from all possible legal chess positions in which the second position can be obtained from the first with a single legal move), then I think I agree with you, that number I believe is bigger than 10^50.

Hawksteinman

I think my 4 player chess might be. Check out the thread: 4 player chess to find out more about it. Frankly brilliant idea.

watcha

The longest possible game under the 50 move rule is 11797 halfmoves:

http://de.wikipedia.org/wiki/50-Z%C3%BCge-Regel#Schachmathematik

In an average position there are 35 legal moves.

After all this, it is mistery for me how one can arrive at a number 10^50.

To me a distinct game is a unique sequence of moves, where order matters. 1. e4 e5 2. d4 d5 is not the same game as 1. e4 d5 2. d4 e5.

So the number of distinct games should be somewhere on the order of 35^11797.

SeanEnglish

watcha, your estimate of 35^11797 suggests that every game has 11797 half-moves in it. While I think that could be used as a decent upper bound, to do an estimate like you did, you would have to find the average number of moves in a game(not in a game played by people though, so you can't use a large game database to get an estimate, but in an arbitrary game.)