Puzzle: mathematical puzzle

Post any puzzles you have or post your analysis of any games played on Net-Chess or anywhere else. Posts which do not contain game puzzles or analysis will be removed, such posts belong in the general forum. Commentary and discussion on openings is also welcome here.
Post Reply
nerob
Posts: 4
Joined: Sun Mar 17, 2002 6:00 am

Puzzle: mathematical puzzle

Post by nerob » Mon Sep 22, 2003 4:14 am

Given that each player at start of a game has 20 possible opening moves, the number of possible board positions after 1 move each is 400.
What is the MAXIMUM number of legal board positions after 2 moves each ? :shock:

gmiller
Site Admin
Posts: 1388
Joined: Sun Mar 14, 1999 11:13 am
Location: Jeffersonville, IN
Contact:

Post by gmiller » Mon Sep 22, 2003 8:48 am

It's probably somewhere around 160,000. But there's no mathematical way to determine the exact number of moves, the only way would be to count them all. 8)

keithstuart
Uranium
Posts: 266
Joined: Mon Apr 12, 1999 3:52 am
Location: NW England
Contact:

Post by keithstuart » Mon Sep 22, 2003 10:50 am

is it not possible to have a chess program tell you??

gmiller
Site Admin
Posts: 1388
Joined: Sun Mar 14, 1999 11:13 am
Location: Jeffersonville, IN
Contact:

Post by gmiller » Mon Sep 22, 2003 11:13 am

You could, but it's not a puzzle then.

tcc
Posts: 1
Joined: Mon May 07, 2001 2:07 pm

Chess positions

Post by tcc » Wed Oct 01, 2003 7:53 am

Hi,
I just did a Google search for ("Chess positions" 400).
Howstuffworks has a site of "How Chess Works" and it says probably about 160,000 after 2 moves (20x20x~20x~20).
Another site at MathWorld or Works listed the positions as: 20, 400, 5362, 71852, ...
I'm fiddling with some of it at work. Unfortunately some of white's second moves are obviously dependent on Black's first move but the rest isn't too difficult to write out (for instance, if white plays a3 1st move then regardless of what black does, white will only have 19 possibilities for a 2nd move - playing a4 adds the Ra3 move, Na3 move and a possible axb5 move for a total of 22 possibilities).
Here's what I've got so far....
a3->19
a4->22
b3->21
b4->23
c3->21
c4->24
d3->27
d4->30
e3->31
e4->33
f3->18
f4->19
Gotta get back to work now.

nerob
Posts: 4
Joined: Sun Mar 17, 2002 6:00 am

Maybe you miss the point

Post by nerob » Sun Oct 05, 2003 9:33 am

The question was not "how many combinations of moves" but how many differennt positions there could be - imagine taking a photograph after move 2. How many different photos could you have. I think the answer is less than 900

keithstuart
Uranium
Posts: 266
Joined: Mon Apr 12, 1999 3:52 am
Location: NW England
Contact:

Re: Maybe you miss the point

Post by keithstuart » Sun Oct 05, 2003 10:30 am

nerob wrote:The question was not "how many combinations of moves" but how many differennt positions there could be - imagine taking a photograph after move 2. How many different photos could you have. I think the answer is less than 900
must be more than 900 postitions white can make 16 different pawn movs for hsis first move and black can make 16 reposnses back for his first move which is 256 unique positions after one move each already not counting the several knight moves that can be made

sirthursday
Posts: 26
Joined: Sat Oct 11, 2003 3:31 am

Post by sirthursday » Fri Dec 05, 2003 12:35 pm

I don't know about 2 moves each but for three moves each the total number of legal positions is something like 9 million. (Read it in a book somewhere)

swraichu
Posts: 14
Joined: Wed Dec 31, 2003 9:07 am

Post by swraichu » Wed Dec 31, 2003 10:28 am

Because most of the pieces are cramped in at the start, both players could create a lot of variations by releasing these pieces... I'd say at least 500,000.

gmiller
Site Admin
Posts: 1388
Joined: Sun Mar 14, 1999 11:13 am
Location: Jeffersonville, IN
Contact:

Post by gmiller » Wed Dec 31, 2003 2:32 pm

We're counting the number of possible possitions, not the 'likley' possitions. Only moves of the center pawns actually increase the number of moves significantly. (e.g. after playing f3 the number of valid moves is only 19). Also checks significantly reduce the number of valid moves.

steve
Posts: 9
Joined: Wed Oct 20, 1999 10:05 am
Location: Jeffersonville, In

Post by steve » Sat Jan 03, 2004 8:59 pm

I did something similar to what was done earlier - for each first move, how many possible 2nd moves. Then I added them up and got 440. There would be 440 possible moves, if the opponents move did not give additional moves or restrict any moves.

The next step was to remove the moves where the position is identical. If my thinking is right, that is done by determining the number of original moves that are still possible after the first move.

If a knight is moved first there are 16 possible original moves still available - the original 20 minus the two knight moves, plus the two moves of the pawn the knight is now blocking.

For most pawn moves there are 18 possible original moves. (20 minus the pawns two original moves). For four of the pawn moves it is blocking a knight move, leaving 17 moves.

Doing the math... 4 (knight moves) * 16 + 4 (pawn moves that block a knight) * 17 + 12 (other pawn moves) * 18 = 348. This is the number of moves where there is another combination that ends up in the same position. Divide that by 2 to get 174. Subtract that from the 440 and you get 266. That is the number of possible positions (assuming all of my math is right) that is possible after 2 moves, if the opponent does not give additional moves or restrict any moves. Square that and it is 70,756 possible possitions for both sides.

The number 71,852 has been mentioned as the correct number of positions. My calculations did not take into account the effects of opponents moves. If both numbers are correct then there is a little over 1,000 additional positions possible because of opponents moves.

Post Reply