Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Page 1 of 3 123 LastLast
Results 1 to 15 of 43

Thread: Complex Formula

  1. #1
    Banned
    Join Date
    Mar 2003
    Posts
    224
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Complex Formula

    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.

  • #2
    Regular Coder
    Join Date
    Nov 2002
    Location
    Bristol, UK
    Posts
    932
    Thanks
    0
    Thanked 0 Times in 0 Posts


    do you want the answer, or are you just telling us about this?

    ::] krycek [::
    ithium | SOAPI | SDP | PTPScript manual
    "ithium is a non-profit webhost, which is pretty much unique. The mission of ithium is to provide free hosting resources for worthwhile and needy non-profit projects, which otherwise may not be able to obtain such facilities. The money from commercial customers goes to maintain ithium's servers and further development."

  • #3
    Regular Coder
    Join Date
    Nov 2002
    Location
    Bristol, UK
    Posts
    932
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Well, I'm not quite sure that I understood the question, but I'll have a bash at the answer...
    Code:
    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?
    ithium | SOAPI | SDP | PTPScript manual
    "ithium is a non-profit webhost, which is pretty much unique. The mission of ithium is to provide free hosting resources for worthwhile and needy non-profit projects, which otherwise may not be able to obtain such facilities. The money from commercial customers goes to maintain ithium's servers and further development."

  • #4
    Senior Coder
    Join Date
    Jun 2002
    Location
    Wichita
    Posts
    3,880
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  • #5
    Banned
    Join Date
    Mar 2003
    Posts
    224
    Thanks
    0
    Thanked 0 Times in 0 Posts

    yes,

    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.

  • #6
    Regular Coder
    Join Date
    Nov 2002
    Location
    Bristol, UK
    Posts
    932
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

    ::] krycek [::
    ithium | SOAPI | SDP | PTPScript manual
    "ithium is a non-profit webhost, which is pretty much unique. The mission of ithium is to provide free hosting resources for worthwhile and needy non-profit projects, which otherwise may not be able to obtain such facilities. The money from commercial customers goes to maintain ithium's servers and further development."

  • #7
    Senior Coder missing-score's Avatar
    Join Date
    Jan 2003
    Location
    UK
    Posts
    2,194
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  • #8
    Banned
    Join Date
    Mar 2003
    Posts
    224
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  • #9
    Senior Coder missing-score's Avatar
    Join Date
    Jan 2003
    Location
    UK
    Posts
    2,194
    Thanks
    0
    Thanked 0 Times in 0 Posts
    It would be interesting to know, but probably not fun to do.

  • #10
    Regular Coder
    Join Date
    Nov 2002
    Location
    Bristol, UK
    Posts
    932
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

    Can you describe the task more fully?

    ::] krycek [::
    ithium | SOAPI | SDP | PTPScript manual
    "ithium is a non-profit webhost, which is pretty much unique. The mission of ithium is to provide free hosting resources for worthwhile and needy non-profit projects, which otherwise may not be able to obtain such facilities. The money from commercial customers goes to maintain ithium's servers and further development."

  • #11
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts
    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.

  • #12
    Banned
    Join Date
    Mar 2003
    Posts
    224
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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])

  • #13
    jkd
    jkd is offline
    Senior Coder jkd's Avatar
    Join Date
    May 2002
    Location
    metro DC
    Posts
    3,163
    Thanks
    1
    Thanked 18 Times in 18 Posts
    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.

  • #14
    Banned
    Join Date
    Mar 2003
    Posts
    224
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  • #15
    Regular Coder
    Join Date
    Nov 2002
    Location
    Bristol, UK
    Posts
    932
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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

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

    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 and THEN tell him he's wrong!

    ::] 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...
    ithium | SOAPI | SDP | PTPScript manual
    "ithium is a non-profit webhost, which is pretty much unique. The mission of ithium is to provide free hosting resources for worthwhile and needy non-profit projects, which otherwise may not be able to obtain such facilities. The money from commercial customers goes to maintain ithium's servers and further development."


  •  
    Page 1 of 3 123 LastLast

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •