Using MATLAB with Chessboard arrangements problem

I'm trying to create codes that can calculate the possibility of chessboard arrangements. The board is 8x8 colored squares. Each player has 8 pawns, 2 knight, 2 rooks, 2 bishops, 1 king and 1 queen. All pieces can be lost.

Please suggest how to write codes to calculate the number of board configurations.

[Walter Roberson]

Which rules, _exactly_ ? Castling? En-passent ? Are pawns allowed to advance 2 positions on their first move? Is moving into Check permitted? If Check is present, is it required to move out of it? Does the number of _possible_ positions include cases where the opponent choses *not* to take the King even though they could (e.g., simulating the possibility that they missed the move) ?

[Sean de Wolski]

I sense a PhD thesis for each those questions Walter.

[Sean de Wolski]

Stalemate after three identical moves or when one side can't legally move without checking thyself?

[Walter Roberson]

The three limit is about having the board positions repeat three times, but having a board position repeat does not create a new position configuration and so the question is not relevant to Fritzy's calculation. No matter what the move path to reaching a given board configuration, each configuration is counted only once.

In tournaments in which the number of moves is limited, the number of moves to reach a configuration is important (as is the thinking time required to reach it), but those are not taken in to consideration for Mr. Cat's question.

[Will Dampier]

Being the Prof. who actually asked this question ... I'd like to clarify. As stated in the problem definition, I don't care about legal or illegal positions. So that simplifies the problem considerably.

The best way to think about it is how can I arrange 32 pieces (or less) on a board of 64 squares.

I'll post an answer after the due date (5PM EST on 5/9/2011)

[Sean de Wolski]

That makes it a much more reasonable question.

[Will Dampier]

If I were asked the "legal positions" I would probably generate a couple hundred thousand random boards (of legal or illegal positions) and estimate the ratio of legal to illegal boards and then go from there. It would be a pretty crappy estimate but it would be about as far as one could figure out in the 7 days allotted for the midterm.

And BTW ... I DID allow people ask the internet for help. If only they'd been better at asking they might have gotten a reasonable answer in time ;)

[Andrew Newell]

Welcome to MATLAB Answers! Having both a Prof. and a student visit the same question may be a first. As student questions go, this one isn't bad.

[Will Dampier]

@Andrew: Yeah, at least it wasn't a copy-paste of my hand-out ... those are always the worst.

[Mr.Fritzy cat]

Thanks, Dr.Will for a crazy problem :D

Answer 1

[Sean de Wolski]

All this nerd can say is: Good luck on your incredibly difficult project!

ps. Look at John's Variable Precision Integers on the FEX. You're going to need it.

[Walter Roberson]

http://mathworld.wolfram.com/Chess.html

10^(10^50)

[Sean de Wolski]

Yeah, even vpi can't handle that:

>> ten = vpi(10);

>> ten^(ten^50)

??? Error using ==> vpi.power at 36

the exponent must not be larger than 2^53

Error in ==> vpi.mpower at 39

b = a.^k;

[Walter Roberson]

It wouldn't be possible to write them all down... not enough elementary particles in the Universe.

Answer 2

[Walter Roberson]

By the way: It has been shown that for sufficiently large problems such as this, as long as "Moore's Law" continues to hold, that you are better off waiting to start the computation.

If you have a particular amount to invest, then roughly 18 months from now, that amount would buy you twice the processing power and thus get the solution twice as quickly. If your computation was going to take 36 months, waiting those 18 months before starting would allow you to finish at the same time, and if your computation was going to take more than 36 months, then waiting those 18 months to start would get the result sooner. But roughly 36 months from now processors will be twice as fast again, so if your computation is going to take more than 72 months, you are better off waiting 36 months before starting... but then you might as well wait 48 months and buy the faster processors available then.

The longer your program would take on today's processors, the longer you should wait to start in order to finish sooner !!

As the computation that is proposed would take more than twice the expected lifetime of the universe, you are best off not starting it within the lifetime of this universe at all, and to instead dedicate your efforts to figuring out how to construct the next universe as purpose-built computer hardware to solve your problem.

Answer 3

[Andrew Newell]

If the positions don't need to be legal, you can use combinatorial calculations. For example, let's first suppose that you can't remove any of the pieces. The number of possible positions for the White king is 64. When this king has chosen his spot, the other king has only 63 positions. Thus, there are 64*63 ways the two kings can be arranged. Now look at the white bishops. If you could tell the difference between them, you could say that there are 62*61 combinations of bishop positions. However, they are identical, so for each position there is another that looks the same because the two bishops have been swapped. Thus, there are (62*61)/2 different positions. This can be calculated using the MATLAB function nchoosek:

nchoosek(62,2)

ans =

        1891

The total number of positions for the two kings and the two white bishops is the product:

64*63*nchoosek(62,2)

ans =

     7624512

In the same way you can keep choosing positions for pieces until all the pieces are accounted for.

EDIT: I got the reasoning below wrong the first time. Here is the corrected version:

Suppose you can remove pieces. The white king has 65 choices: one off the board and 64 on. If White is off the board, the black king still has 65 choices. If White is on the board, there are 64 choices for the black king - 63 on the board and one off. The sum of the possibilities is

1*65 + 64*64

ans =

        4161

If the two pieces are identical, e.g., two White knights, there are 65 cases where one piece is off the board and one is on, while the number of positions must be divided by two when both are on the board:

1*65 + 64*63/2

ans =

        2081

[Walter Roberson]

You cannot have the two kings beside each other: moving your king to be beside the other king would be placing your king into check.

[Andrew Newell]

That's why I said "If the positions don't need to be legal ..."

[Will Dampier]

I like this method, not how I originally solved the problem but certainly valid. When I implemented it got within 1% of my answer which is probably just due to the rounding error involved in doing factorials of 64.

[Andrew Newell]

Glad you like it. I wonder if the student ever saw it?

[Sean de Wolski]

@Professor Dampier: Have you looked at variable precision integers on the FEX to make factorials of 64 feasible?

[Will Dampier]

@Sean Never really cared about that much precision. According to the docs factorial(N) will give the correct order of magnitude and precision out to 15 digits ... this is more then enough for me.

[Mr.Fritzy cat]

Thanks for your feedback....

[Walter Roberson]

You have to be careful with the "65", in that any number of pieces can be in that 65th spot. Makes the combinatorics harder to handle.

[Andrew Newell]

Right - I slipped up with the two knights (another edit).

Answer 4

[Walter Roberson]

11530507514326328290083073687940191225693801

if the empty board is included.

(The solution is at most 3 lines of Maple, and once the second line has been seen, it becomes obvious why it can be reduced to 1 or 2 lines.)

[Will Dampier]

Not the same order of magnitude as I got ... can you post your Maple solution?

[Walter Roberson]

There's still 3/4 of an hour before the deadline, so I'll hold off until then, as it is not difficult to translate the Maple in to MATLAB.

[Will Dampier]

Sure, I can wait

However, you're assuming they understand either Matlab or Maple ;)

[Will Dampier]

Does that take into account missing pieces ... because I get a similar number (within rounding distance) of your number if I remove that consideration.

[Walter Roberson]

Yes, each of the variables is the number of those items remaining on the board. The value of 0 for the variable is the case where none of that kind are remaining (and so are not using up any squares.)

[Will Dampier]

I'm not so sure ... The upper-bound of legal positions is estimated at ~10^47 (http://homepages.cwi.nl/~tromp/chess/chess.html) and one would assume that the number of legal positions is subset of this. Your answer is many orders of magnitude less then this.

[Will Dampier]

And the site mentioned above (http://mathworld.wolfram.com/Chess.html) quotes estimates at 10^40 to 10^43

[Walter Roberson]

It is now after the deadline, soooo...

Maple:

sum(sum(sum(sum(sum(sum(sum(sum(sum(64!/(BKn!*WKn!*BR!*WR!*BB!*WB!*BP!*WP!*(64-KQ-BKn-WKn-BR-WR-BB-WB-BP-WP)!), KQ = 0 .. 4), BKn = 0 .. 2), WKn = 0 .. 2), BR = 0 .. 2), WR = 0 .. 2), BB = 0 .. 2), WB = 0 .. 2), BP = 0 .. 8), WP = 0 .. 8);

B* is Black, W* is White

KQ is Kings and Queens (they are all distinguishable for each other)

*Kn is Knights, *R is Rooks, *B is Bishops, *P is Pawns

The value of each variable is the number on the board, so when the value is 0 there are none of that kind of piece.

The basic expression,

64! /

(BKn!*WKn!*BR!*WR!*BB!*WB!*BP!*WP!*(64-KQ-BKn-WKn-BR-WR-BB-WB-BP-WP)!)

is a mostly obvious multi-item combinatorics expression, differing from a straight N-choose-K only in the KQ component.

[Walter Roberson]

The above formula was derived from the below, where C(N,K) is N-choose-K = N!/(K!(N-K)!)

64!/(64-KQ)!*C(64-KQ, BKn)*C(64-KQ-BKn, WKn)*C(64-KQ-BKn-WKn, BR)*C(64-KQ-BKn-WKn-BR, WR)*C(64-KQ-BKn-WKn-BR-WR, BB)*C(64-KQ-BKn-WKn-BR-WR-BB, WB)*C(64-KQ-BKn-WKn-BR-WR-BB-WB, BP)*C(64-KQ-BKn-WKn-BR-WR-BB-WB-BP, WP)

That is, KQ is a permutation placement (because they completely are distinguishable from each other), and the rest of the items reading left to right are simple Combination calculations of the number of remaining positions on the board and the number of items (which is, by definition, the number of ways that K out of N items may be chosen without regards to the order such as because the items are indistinguishable from each other.)

[Andrew Newell]

I'm surprised that this does seem to handle the off-board cases correctly, but your expression does agree with my analysis for just two knights.

[Bjorn Gustavsson]

Walter, just to throw a spanner in the works: About (==exactly) half the pawns can reach the eight (or first) row...

...and then be promoted.

Answer 5

[Will Dampier]

Now, 15 hours after the deadline I've finally gotten all submissions I'll post my solution based on Andrew's solution. Its much shorter, simpler, faster and easier to understand then my original method and gives nearly an identical answer.

The general idea is that when the board is empty and I have a black king in my hand there are 64+1 (64 on the board and 1 off) places I can put it. For the black queen there are 63+1 remaining places ... assuming I put the king down on the board, otherwise there are 64+1 places. So the number of places for the black queen is 63+1 + 64+1.

When I go to put down the black knights there are 62+2 remaining. Since they're indistinguishable the number of combinations is nchoosek(62+2,2). Again this is assuming the black king and black queen were put down.

So assuming we have a count of the number of pieces in each class we can easily generalize this. If N is the number of pieces already placed, M is the number of items in this class and C is the number combinations:

C = 0;
for k = (64-N):64
  C = C+nchoosek(k+M, M);
end

So the entire thing can be implemented as:

iboard = [2,3,4,5,6,4,3,2,ones(1,8),zeros(1,32),-ones(1,8), ...
            -2,-3,-4,-5,-6,-4,-3,-2];
%count the pieces ... could've easily just started here
class_counts = histc(iboard, -6:6);
class_counts(7) = []; %remove the zeros

num_places = zeros(size(class_counts));
for i = 1:length(class_counts)
    %go through each piece type
    rem = 64-sum(class_counts(1:i)); %calculate the number of remaining places

      %since pieces can also be lost: rem+class_num
      for k = rem:64
          %need to deal with the issues of when previous pieces are 'missing'
          num_places(i) = num_places(i)+nchoosek(k+class_counts(i), ... 
                           class_counts(i));

      end

end
%number of configurations is the product of these.
num_boards = prod(num_places);

This gives a result of ~7.79E58 which generally makes sense. Most of the estimates of number of legal boards is ~10^47. So our superset should be much larger.

[Mr.Fritzy cat]

Thanks for the solution. I don't even know theses codes and my estimate is only 10^44 :(

[Will Dampier]

you know these! We covered nchoosek ... and besides a for-loop that's all there is!

[Sean de Wolski]

Don't overwrite MATLAB's builtin function rem() !!!

[Walter Roberson]

You wrote, "So the number of places for the black queen is 63+1 + 64+1." That is obviously wrong: there are not 127 places on the board. If the black king is not on the board, only _one_ more space is available.

[Will Dampier]

@Walter: ooooo ... that is a very good point!

[Will Dampier]

although simply removing it gives an estimate that is far too low ...