Mathematics desk
< February 17	<< Jan \| February \| Mar >>	Current desk >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

February 18

Vacuous question

If no question is asked then any answer written here is correct. Count Iblis (talk) 12:32, 18 February 2014 (UTC)[reply]

And you didn't even link to vacuous truth! —Quondum 15:26, 18 February 2014 (UTC)[reply]

Thanks, I didn't know that this is called that way (English is not my mother tongue) :). You also encounter this when taking the intersection of a collection of sets. If the collection of the sets is empty then the intersection is the whole space. In some statements in topology or measure theory you then don't have to explicitly address the exceptional cases when a collection of sets is empty. Count Iblis (talk) 15:59, 18 February 2014 (UTC)[reply]

1 + 1 + 1 + 1 + 1 + · · · = −1/2 Count Iblis (talk) 16:44, 11 March 2014 (UTC)[reply]

If

$f(x)=\sum _{k=0}^{\infty }(-1)^{k}{\frac {c(k)}{k!}}x^{k}$

then

$\int _{0}^{\infty }x^{s-1}f(x)dx=\Gamma (s)c(-s)$

Count Iblis (talk) 01:02, 27 March 2014 (UTC)[reply]

calculating entropy of full chess board position

I am trying to calculate how much entropy is in a chess position - average entropy that it takes to transfer a total chess position for someone else to continue on, then I could approximate an upper bounds like this: there are 32 pieces, each one could be set as knowing where it is: horizontal (1 of 8 so 3 bits of entropy) vertical (1 of 8 so 3 more bits) and that is enough to determine where it is on the board, if you allow a 65th board position (an additional 0.02 bits of entropy) for being off the board. Additionally the rooks and king need 1 bit each for whether they have castled yet (this can be reduced slightly as the king has to have not moved, so the possibility space for both sides is, K+R1+R2 haven't moved, K+R1 haven't mvoed, KR+2 haven't moved or X no castle possible for that side - this is 4 possibilities so 2 bits of entropy), the pawns need about 2.3 bits to state what piece they currently are, as they can be promoted, and we need 1 bit to determine whose move it is. If we add that all up we get to a number. The problem is that this still doesn't represent the whole state of the board - for example, the first time a position occurs is not the same as the third time. So, how many bits of entropy does a full board state really contain? --91.120.14.30 (talk) 15:21, 18 February 2014 (UTC)[reply]

You should take care with your use of "entropy", in which the relative probability of each state enters into the equation. It sounds to me as though you are asking what the minimum fixed-length codeword size is to describe the layout of a chessboard plus some additional information, given simple heuristics that allow exclusion of many states. Defining the heuristics (as you have started doing) is a flexible process, and affects the result. Your constraints on encoding and decoding complexity permitted will also play a part. It is simple if tedious to produce some very crude upper and lower bounds, if you have the energy for it. —Quondum 16:15, 18 February 2014 (UTC)[reply]

That entropy link should probably be to Entropy (information theory), or Entropy_(disambiguation)#Interdisciplinary_applications_of_entropy, rather than the thermodynamic version. AndrewWTaylor (talk) 16:19, 18 February 2014 (UTC)[reply]

It depends whether or not you exclude illegal board positions i.e. board positions that cannot be reached through a legal sequence of moves from the normal starting position (so a legal position requires both kings on the board, kings cannot be adjacent, cannot have both kings in checkmate etc etc).MathWorld estimates the number of different chess games with 40 moves or less as between 10⁴⁰ and 10⁴³. Taking the upper bound here, we get about 143 bits of information. This is a lot smaller than your "6 bits per piece with some adjustments" upper bound because most board positions created by placing pieces on the board "at random" are illegal. Gandalf61 (talk) 16:21, 18 February 2014 (UTC)[reply]

143 bits is really tiny. For example, on a typical chess board position there are 30 possible moves (according to our article shannon number, which was quoted when I googled "average number of legal moves in chess"), so if your algorithm is a means to enumerate in some deterministic way the possible moves - and you then try to say which number was chosen out of those possibilities, then you get an average of 4.9 bits per move per side, so about 10 bits per move. That means that you can only represent 14.3 moves by encoding the space of actual chess games. That makes me extremely incredulous that 143 bits can encode any chess position. It seems the pigeonhole principal would come into play, assuming that there are more than 15 moves in the average chess game, and that the number of possible moves per board position is correct from that article. Thoughts? - 91.120.14.30 (talk) 16:50, 18 February 2014 (UTC)[reply]

Yes, you are right - Shannon number says Shannon's estimate of 10⁴³ is the number of possible (and presumably legal) positions, not the number of games. The MathWorld article quotes Shannon's estimate without clarifying that it is an estimate of positions and not games. So 143 bits can encode a legal position (according to Shannon's estimate), but does not distinguish between the many different sequences of moves that could lead to that position. Shannon number also mentions a more recent estimated upper bound on the number of legal positions, which is equivalent to 155 bits. Gandalf61 (talk) 17:08, 18 February 2014 (UTC)[reply]

If one records a chess game as a sequence of moves starting from a standard position, then a simple naive coding of beginning position-ending position suggests 12 bits per move, plus a little extra for keeping track of non deterministic events like pawn promotion. Then that is 12 bits per board position, amortized over the length of a game. If we allow for a chess engine to store the history of the game and compute a set of legal moves at each point, then we need only encode which legal move was chosen. There are no more than something like 218 legal moves[1], so that suggests creating a list of legal moves, ordering them by say rank and file of starting position and end position and encoding the move's position in the list would take 8 bits or less. This is getting closer to Gandalf's estimate. If one then computed the probabilities for each numerical position on the list of the chosen moves and Huffman encoded that, that would reduce the amortized size down to something like 5-6 bits, assuming there are on average 30 legal moves per position.--Mark viking (talk) 17:24, 18 February 2014 (UTC)[reply]

There's not that many good moves in each position, if you code by some approximation of best move first then for two grandmasters the encoding would be very short. However for two novices one might get practically anything. Dmcq (talk) 18:33, 18 February 2014 (UTC)[reply]

I changed my link as per suggestion Huffman coding (and the simpler, slightly more efficient arithmetic coding) requires estimates of relative probability of each move, which brings us back to the problem statement: is the objective to optimally encode a position (or game sequence?) under an average encoding length metric, or under a maximum coding length metric? If this is not intended to be envisaging something that is in principle practical, arithmetic coding of the move history simpler to analyse, and a pretty accurate figure of average coding length should be possible from analysing a database of historical games played using the ideas as per Mark & Dmcq's comments. —Quondum 19:41, 18 February 2014 (UTC)[reply]

Another piece of data that would need to be encoded is whether any of the pawns have been promoted. Also it is entirely possible to have two boards with the same position where two equivalent pieces have switched positions (one white rook on A4, the other on B5, or vice versa)

I find myself wondering if just storing the game history wouldn't be better. Each move can be coded as a from position and a target position, at 6 bits each, or 12 bits total. If a piece moves to the position of another piece, that's a capture. If a king moves two spaces, that's a castle. If a pawn moves diagonally and there's no piece there, that's an en pessant capture. You would need two extra bits for pawn promotions, to show which piece was selected. So, with, say, 50 moves and two promotions, that would be 604 bits, and contains the entire game history. That's not bad. And yes, the computer would need to play through the entire game to get to the current board position, but that should only take a fraction of a second, and it could check for repeated moves, illegal moves, etc., while it runs. StuRat (talk) 04:13, 19 February 2014 (UTC)[reply]

Another issue. The board position does not contain all of the information necessary to determine what moves are possible in the future.

Consider a board where white and black have moved their King and Queen Pawns, and none of the Knights and Bishops are on their home squares. From that, white moving a Knight back and forth to a second square and Black doing the same thing will restore the board to the same position. OTOH, if one of both of them moves their King Rook back and forth then the board is in a different "position" because of the inability to castle than it will *not* be the same position
taking En-Passant *must* be done on the move immediately following the move of the pawn from the second to the fourth rank. If a pawn has moved to the fourth rank and then both players move knights back and forth, the "position" of the board has changed since the EP capture can no longer occur
fifty move rule and three times repetition. Two identical boards will be in different positions if a different number of moves have occured since the last pawn captures *or* based on how many times the particular position has occured.Naraht (talk) 17:53, 20 February 2014 (UTC)[reply]

Yes, this is why I suggested storing the entire game history, in my previous response. StuRat (talk) 18:08, 20 February 2014 (UTC)[reply]