...

# Complex Formula

mattover-matter
04-14-2003, 10:09 PM
I just know I am in WAY over my head. I have been attempting to calculate the number of possible positions in chess. I started by taking the number of squares in a chess board.

8 x 8 = 64 tiles on a chess board.

Each players has a total of 16 peices, so we would do 32x64 = 2048 possible positions. But that is exlcuding mutual positioning and invalid moves. We know that pawns cannot move backward, so we can take the total, without pawns, x 16 away from the total. Bishops, also can only move to 32 squares each on the board. The mutual positioning is the hardest to kink out. Every time I think I have it, I find a flaw in my math. Does anyone know of a good resource that will aid me here today?

PS: If someone has already calculated this, please do not post the link. I want to figure this out (mostly) on my own.

PSS: I am still in the process of working this out, I may figure something out later. In other words, I have not been crushed by such a problem yet.

krycek
04-14-2003, 10:34 PM
:confused:

::] krycek [::

krycek
04-14-2003, 10:45 PM
Well, I'm not quite sure that I understood the question, but I'll have a bash at the answer...

King 64 x1 x2 = 128
Queen 64 x1 x2 = 128
Bishop 32 x2 x2 = 128
Knight 64 x2 x2 = 256
Castle 64 x2 x2 = 256
Pawn 7? x8 x2 = 112
1008

I'm not sure if I understand the question, so I've given pawns 7 spaces to move. Although one individual pawn could cover a triangular area, however only taking one path through it... so I stuck with 7.

Tell me, what was so hard about that? Took me 2 mins with a pen and paper, and 5 mins to type up...

::] krycek [::

PS - If it's right, do I get a prize? :D

Roy Sinclair
04-14-2003, 11:18 PM
This could be extremely complex. You can't just take all the possible positions for a single piece and multiply them times all the possible positions for every other piece because some combinations wouldn't be possible to create in a game, the possible positions of the king for example would be limited depending on the positions of the other pieces. Also every single pawn has the possibility of reaching the opposite rank and therefor being promoted so you also have to deal with the possibilties of multiple queens.

In fact the pawns add tremendous complexity to the problem since they can't pass each other but through taking other peices it is possible for them to end up many ranks left or right of their initial position but only when they aren't close or next to a board edge.

mattover-matter
04-14-2003, 11:25 PM
I said that. I need help witht he mutual positioning. Two peices cannot be on the same square. PLus pawns and bishops can not reach every square on board. What about if u kill a peice. I would never ask something that was not way over my head. :D

krycek
04-14-2003, 11:34 PM
well, that was kinda what I was scared of.

See, I hoped you were just trying to work out the 'potential'. If you are trying to work out according to moves etc. then give up! It's too hard. Plus I don't know if what you are trying to do is valid... I mean, what limits are you setting?

If you are talking about an open-ended game, then my answer is correct as the potential number. However I think the question is a bit odd in the first place.

Why are you trying to do this? What restrictions are you imposing? The way you are headed is into fiendishly complex maths :p

::] krycek [::

missing-score
04-14-2003, 11:55 PM
Just another note, when a pawn reaches the end of the board, it can then be exchanged for another piece. So that makes it a whole lot more complex.

Personally, I wouldn't bother. You would have to work it out by hand, no real times this by this and get this sorta thing.

mattover-matter
04-15-2003, 01:05 AM
fiendishly? Sounds scary...

But, if math if power...should I be scared of it?

re: why?

I just thought it would be interesting to know, and fun to do.

missing-score
04-15-2003, 01:08 AM
It would be interesting to know, but probably not fun to do.

krycek
04-15-2003, 01:31 AM
mattover-matter, I think you really need to figure out what you are trying to do, because so far you are either a) trying to do something inherently impossible, or b) something else that I haven't quite understood yet :p

Can you describe the task more fully?

::] krycek [::

jkd
04-15-2003, 03:05 AM
You can easily get an upper bound on board positions, but legal board positions should be a little smaller (perhaps insignificantly less so).

Don't ask me to calculate it (I would't want to sit down for an hour thinking about it), but finding the upper bound is really just simple combinatorics.

mattover-matter
04-15-2003, 04:43 AM
ok, im going to restate:

My question:
I wish to figure out how many valid positions in a chess game are possible (at one time)

My troubles:
1) two peices cannot be on the same square at one time
2) bishops cannot reach every square on the board
3) pawns cannot reach every square on the board (cannot move backwards)
4) Whenever a pawn reaches the end, It can choose a peice that is already dead (from his side) and revive it inplace of the pawn. You cannot have 2 queens, or 3 rooks.
5) Units cannot travel through (you must think back). A pawn cannot appear behind an enemy pawn for some reason (well, it is possible but not if the pawns have not killed anyone)

FYI:
1) There are 64 squares on a chessboard.
2) There are 8 pawns, 2 rooks, 2 knights, 2 bishops, 1 queen, 1 king per side(32 in total)
3) The dimensions for a chessboard are 8x8.
4) A knight CAN reach every position on the board.

Also, I asked at DR.math forum to see if anyone there knows a solution.

re: It would be interesting to know, but probably not fun to do

You are missing the point of this. Do you think I randomly pick things that have 0 relevency in anything I will ever do (don't take me literally)? I am doing this to learn, not to know. knowing is just a bonus. (note : what I just said applies to this problem, and this problem only [again, don't take me literally])

jkd
04-15-2003, 05:51 AM
Like I said, it really isn't that hard to find a usable solution. The upper limit of all board positions will be insignificantly greater than the number of all possible board positions, and with that in mind it is a long-winded combinatorics problem. I don't think you'll find anybody wiling to sit down and grind out the numbers though... I remember reading that the number of possible games of chess is greater than the number of all the grains of sand in the world.

That's a lot, and those numbers aren't easy to calculate, even with 3ghz P4 beasts.

mattover-matter
04-15-2003, 06:03 AM
I do not mean number of games possible. I mean at one state.
The starting position is one(1)(uno) position. You once heard wrong, that is impossible because exclding all the problems that would degrade it it still is only 2000 something, multiply that be 500, and it still does not reach the number of grains of sand.

krycek
04-15-2003, 12:47 PM
Originally posted by mattover-matter
I do not mean number of games possible. I mean at one state.
The starting position is one(1)(uno) position. You once heard wrong, that is impossible because exclding all the problems that would degrade it it still is only 2000 something, multiply that be 500, and it still does not reach the number of grains of sand.

...don't tell jkd he's wrong until you have actually learnt about probabilities in math class :p

He's spot on as usual - the number of possible games is an exceedingly large number! :eek:

So, go back to school, learn about these things, get as far as people like myself have, THEN TRY to get as far as jkd :eek: and THEN tell him he's wrong! :rolleyes:

::] krycek [::

PS - It is a constant mission to me to find jkd wrong at something. So far, I have succeeded only twice - and one of those was debateable... :(

missing-score
04-15-2003, 12:52 PM
Lol.

Next time I go onto a site where it asks for a mission, I can put: "To prove jkd wrong"

krycek
04-15-2003, 12:53 PM
Originally posted by mattover-matter
ok, im going to restate:

My question:
I wish to figure out how many valid positions in a chess game are possible (at one time)

My troubles:
1) two peices cannot be on the same square at one time
2) bishops cannot reach every square on the board
3) pawns cannot reach every square on the board (cannot move backwards)
4) Whenever a pawn reaches the end, It can choose a peice that is already dead (from his side) and revive it inplace of the pawn. You cannot have 2 queens, or 3 rooks.
5) Units cannot travel through (you must think back). A pawn cannot appear behind an enemy pawn for some reason (well, it is possible but not if the pawns have not killed anyone)

FYI:
1) There are 64 squares on a chessboard.
2) There are 8 pawns, 2 rooks, 2 knights, 2 bishops, 1 queen, 1 king per side(32 in total)
3) The dimensions for a chessboard are 8x8.
4) A knight CAN reach every position on the board.

Also, I asked at DR.math forum to see if anyone there knows a solution.

re: It would be interesting to know, but probably not fun to do

You are missing the point of this. Do you think I randomly pick things that have 0 relevency in anything I will ever do (don't take me literally)? I am doing this to learn, not to know. knowing is just a bonus. (note : what I just said applies to this problem, and this problem only [again, don't take me literally])

good luck.

start from the 'potential' figure I gave you (1008) and then take away whatever you want... but your question still lacks what I would call a 'point'... which means I'm probably still missing it! :rolleyes:

Oh yeah and your rules 4 and 5 are technically incorrect. It's possible to have 8 queens, for example, and number 5 is to be laughed at :p What if someone simply decided NOT to take...? Perfectly legal.

::] krycek [::

mattover-matter
04-15-2003, 04:08 PM
I think you mean number of possible games. I mean number of posible positionings

jkd
04-15-2003, 08:11 PM
Possible positions is still enormous. With *just* two kings on the board, you have something like this:

A king on interior: 36*55 (9 squares opponent can't be in)
A king on side: 24*59 (5 squares opponent can't be in)
A king on a corner: 4*61 (3 squares opponent can't be in).

Which sums to 3640. As soon as you throw any more pieces onto the board, it becomes ridiculously enormous.

Notice 64*63 is 4032, which could be considered an upper limit for the calculation. A difference of 392 may seem significant right now, but as we get into billions of combinations, the only feasible way to calculate the number is to look at upper limits.

krycek
04-15-2003, 08:55 PM
ahhhhhh :) now I get what he is trying to do!

the question is, why? :confused:

oh well!

::] krycek [::

krycek
04-15-2003, 08:59 PM
By the way, I worked it out, mattover-matter.

4.5e+53 (I cannot write superscript on here can I? Ah well, I will leave it like that)

Any more accuracy, and that's up to you to work out... :p

::] krycek [::

mattover-matter
04-15-2003, 09:11 PM
re: why?
I am trying to learn :mad: :D
Hey, Can you kinda put that in stupider terms, I thought e was for calculating the growth in percentages...but I learned that on my own (not at school, don't give them the credit for my intelligence :D). Kryckeck, can you please attempt to explain how you figured that out? I'm 13 so you guys are a wee bit ahead of me :D My math class is still on ratios and proportions (for 9 weeks now :rolleyes: ) WOW, jkd I guess....my next mission will be to prove you wrong. I was getting 64*32 = 2??? I guess you proved me wrong.

52*Y

like that kryckeck?

[ s u b ] [ / s u b ] [ s u p ] [ / s u p ]

nope, i guess these avatarless forums are jes' weird :)

scroots
04-15-2003, 10:08 PM
you say calculating the possible positions to move too at any one time in a game.
do you mean you want to calaculate the possible positions to move too at one ponit and later recalculate at another time. or just calculate them once?

would it be an idea that some produces a chessboard overview so that when calculating all the possible moves everyone is working on the same game board.

Depending on positions depends on the possible moves.

scroots

jkd
04-15-2003, 10:08 PM
Originally posted by mattover-matter
I thought e was for calculating the growth in percentages...but I learned that on my own (not at school, don't give them the credit for my intelligence :D).

That's not e as in lim n-> infinity (1+1/n)^n, it is e as in the scientific notation shortcut.

4.5e+53 = 4.5 * 10^53

Which isn't actually the right answer either... it should be significantly larger than that.

mattover-matter
04-15-2003, 10:44 PM
but..number of grains of sand on earth??? That is like....
for (i=0;i++;200;){document.write(",999")}

krycek
04-15-2003, 11:03 PM
Originally posted by jkd
That's not e as in lim n-> infinity (1+1/n)^n, it is e as in the scientific notation shortcut.

4.5e+53 = 4.5 * 10^53

Which isn't actually the right answer either... it should be significantly larger than that.

I'll take your word for it... as you know, it was just a quick estimate :)

I still think that 450,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 is big enough! :D

::] krycek [::

bcarl314
04-18-2003, 03:08 AM
Originally posted by mattover-matter
ok, im going to restate:

My question:
I wish to figure out how many valid positions in a chess game are possible (at one time)

My troubles:
1) two peices cannot be on the same square at one time
2) bishops cannot reach every square on the board
3) pawns cannot reach every square on the board (cannot move backwards)
4) Whenever a pawn reaches the end, It can choose a peice that is already dead (from his side) and revive it inplace of the pawn. You cannot have 2 queens, or 3 rooks.
5) Units cannot travel through (you must think back). A pawn cannot appear behind an enemy pawn for some reason (well, it is possible but not if the pawns have not killed anyone)

FYI:
1) There are 64 squares on a chessboard.
2) There are 8 pawns, 2 rooks, 2 knights, 2 bishops, 1 queen, 1 king per side(32 in total)
3) The dimensions for a chessboard are 8x8.
4) A knight CAN reach every position on the board.

Also, I asked at DR.math forum to see if anyone there knows a solution.

re: It would be interesting to know, but probably not fun to do

You are missing the point of this. Do you think I randomly pick things that have 0 relevency in anything I will ever do (don't take me literally)? I am doing this to learn, not to know. knowing is just a bonus. (note : what I just said applies to this problem, and this problem only [again, don't take me literally])

Heres a possible hint:

try to define the possible move at a given point in the game as an equation. Obviously, the total moves available to a player at any given moment changes based on the position of all the pieces on the board at that moment. For example, when you start the game there are 20 possible moves, each pawn can move 1 or 2 spaces, and 2 knights can move to 2 different spaces each. so we get something like

total moves = total pawns * 2 possible moves + total knights * 2 possible moves or 8 * 2 + 2 * 2 or 16 + 4 = 20.

Now, once you move a pawn, you total possible moves for the next turn increase based on the provious move. So everything is now dependant on the first move. This means you should be able to express the second move as a function of the first move. Hope this helps.

Good luck. I think this could be an SA article if you figure it out. (SA = Scientific American)

mattover-matter
04-18-2003, 06:44 AM
i think you guys were trying to calculate the possible games(entire game) which is infinite.

missing-score
04-18-2003, 10:23 AM
No, Not infinate. A hell of alot, but not infinate.

mattover-matter
04-19-2003, 01:57 AM
Yes, infinite. Moves can be retraced over and over

jkd
04-19-2003, 02:53 AM
Originally posted by mattover-matter
Yes, infinite. Moves can be retraced over and over

Board position can't be repeated three times in a row. Otherwise, it is a draw.

Draws typically also occur when it can be shown that a player can prolong a game indefinitely by repeating a cycle of moves.

Finite.

mattover-matter
04-20-2003, 03:51 AM
oh no, its jkd. I better just step out and agree with him :p

jkd
04-20-2003, 04:09 AM
Originally posted by mattover-matter
oh no, its jkd. I better just step out and agree with him :p

Or you could think about why there are a finite number of games and learn something.

Assuming nonintelligent players who don't mind playing forever, an untimed game could proceed for eternity. What often happens is that there may be an 8 move cycle or something that eventually forces the opponent back to where he started, and in doing so the player ends up where he started as well. Assuming no mistakes, this could continue forever. However, usually a draw is offered and accepted.

Now, also keep in mind that a checkmate is impossible with certain piece combinations. You can't mate with a king and a bishop or a king and a knight. I don't believe you can mate with two knights either. I think you can force mate with two bishops, and you certainly can force mate with a bishop and a knight (though it is lengthy). But games with minimal pieces like this can easily be declared a draw or a victory for someone, even though at first a mate may not seem possible.

This fact significantly reduces the amount of games that seem like they can go on forever.

krycek
04-20-2003, 04:33 AM
Originally posted by mattover-matter
oh no, its jkd. I better just step out and agree with him :p

mattover-matter.

I'm not the only one who is getting COMPLETELY AND UTTERLY FED UP OF YOU :mad:

jkd is a highly respected forum member, as well as being a super-moderator. The reason for both of these is that he knows what he is talking about - whereas YOU DON'T :mad:

jkd is not only a friend of mine but also someone I respect very highly as a programmer and mathematician. He's very rarely wrong, and it p!sses me off to see someone as ignorant as yourself mocking him. I think he deserves extra credit for being so patient and trying to help you!

He's only 17 himself and I believe he was a mod at 13 - I cannot imagine you doing that because you have (a) an enormous lack of maturity, and (b) a shocking lack of respect. :mad:

Almost every day your name comes up in conversations that people have with me; usually in context with the word "annoying". I think you need to grow up FAST or else decrease even more in popularity here (if such a thing is possible). :rolleyes:

Now, shut up and p!ss off and stop implying that you know more than experienced gurus.

::] krycek [::

mattover-matter
04-20-2003, 08:21 AM
what is with you? I did not flame or put-down jkd. I never said he did not know what he was talking about, and I never said I did. Maybe you should think about what you say before you say it.

(a) an enormous lack of maturity, and (b) a shocking lack of respect

Are you determining my personal attributes from a few typed words? I think you need to logically look at that for a second.

missing-score
04-20-2003, 11:18 AM
trust me matt, it's not just him :mad:

krycek
04-20-2003, 06:08 PM
Originally posted by mattover-matter
what is with you? I did not flame or put-down jkd.

I think you were pretty sarcastic, and it wasn't just a once-off!

I never said he did not know what he was talking about, and I never said I did. Maybe you should think about what you say before you say it.

Believe me, I thought about it! You also had that coming to you for a while... I've held back from it but every time I saw a glib post of yours, it got closer until BOOM!

Are you determining my personal attributes from a few typed words? I think you need to logically look at that for a second.
It's YOU that portrays your personal attributes with 'a few typed words'. I don't know (or care) what you are like in real life. I only interact with you online, and as such, the 'personal attributes' you display leave a lot to be desired.

e.g.

- posting nonsense.
- polluting other people's threads.
- taking the mick out of people/mocking them
- 'know-it-all' tone

And a few more similar things. They all add up to be ANNOYING. :mad:

::] krycek [::

mattover-matter
04-20-2003, 08:45 PM
I'm sorry that you feel that way about me. I guess I will take my leave then.

krycek
04-20-2003, 09:09 PM
Originally posted by mattover-matter
I'm sorry that you feel that way about me. I guess I will take my leave then.

Instant reaction - yippee! :p

Second reaction - you don't have to go, you know.

The only reason you are disliked is because you are annoying. :rolleyes:

If you cease being annoying, then it will no longer be a problem.

I for one will be rather disappointed to see you go, because to me that would say that you cannot change your behaviour. I would vastly prefer that you take the time to consider how you are coming across, and then proceed in a more suitable manner. :)

However if that is impossible then maybe it is best that you go.

::] krycek [::

missing-score
04-20-2003, 09:19 PM
Yup, I agree...

I think you (mattover-matter) could be a respected member if you change your attitude, you do seem to be good at programming, as advice you have given in other threads has been good.

mattover-matter
04-20-2003, 10:23 PM
I have given up on programmimg for a few years. It is too boring for me. I will continue creating campaigns in WCIII as I find the more enjoyable.

WA
04-21-2003, 02:59 AM
Ok, obviously I don't condone any of the last few posts in this thread, which are all out-of-order in one way or the other. The best way to file a complaint is to PM me. However, this situation with Mattover-matter has been a long-standing one, and I've decided to suspend his account until further notice.

Please get back to the original topic now. I might delete the last few posts here sometime this week when everyone's had a chance to see what has transpired.

Thanks.

Alex Vincent
04-22-2003, 03:20 AM
Originally posted by krycek
PS - It is a constant mission to me to find jkd wrong at something. So far, I have succeeded only twice - and one of those was debateable... :(

It can be done, speaking from experience. :) But I do hear Mission: Impossible music playing in the background...

It's worth noting that the development of artificial intelligences for chess games has considered the possible number of moves in a game, and discarded it. It's far easier for the computer to throw away all moves following one move which it knows will not be optimal.

EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum