March 2014 - mathfun@mailman.xmission.com

[math-fun] KBBBk, all B's same square color
by Warren D Smith 26 Mar '14

26 Mar '14

Please. I'm pretty confident that ending has never arisen in any real chess game. (It actually is quite difficult to find real game instances containing even one bishop underpromotion. Know any?) If my rules failed to work in all chess endings that required >=2 underpromotions to get there, nobody would care. In fact, if you changed the rules of chess to forbid making more than 1 underpromotion per game, I doubt that would have ever altered any real game. Here is the old rule proposal back again with some minor typos fixed: --- WARREN'S PAWNLESS ENDGAME RULE: In a pawnless endgame with 6 men or fewer (this includes kings): Compute the total material points for both sides using the (very nontraditional!) N=4, B=3, R=7, Q=24, bonus if own two rooks=6, penalty if own "loner queen" faces 2 or more enemy officers=6 (if faces>=4 then penalty=15) bonus if own two bishops of opposite square-colors=5, penalty if own two knights=3, bonus if own both a rook and a non-rook=2, Let M>=0 be the difference between these two material points totals. If M>6.5 then WIN. If 0<=M<6.5, then DRAW. Allegedly the only exceptions are: the KQknn endgame, which is generally a draw although 18-5=13>>6.5; the KNNBkn and KNNBkb endgames, generally wins; and KBBNkb with the BBs having same square-color (not of great importance!) which is a draw. (Annoying man also pointed out KBBBk with all three B's same square color.) I am not sure what the KQQkqr ending usually is (win or draw?) but by redefining the word "non-rook" in the final bonus or adding a "have 2 queens" term if necessary, it should be able to handle this also. With our "if faces>=4" clause this also seems to handle all the common 7-man cases (specifically I think every case mentioned in http://en.wikipedia.org/wiki/Pawnless_chess_endgame is now handled? if I did not screw up) for example KBBNNkq is a win for the 4 pieces: 3+3+4+4-3+5=16 versus 24-15=9.

1 0

[math-fun] chess pawnless endgames
by Warren D Smith 26 Mar '14

26 Mar '14

I may be deluded (please tell me if see any counterexample!) but I found the following nifty rule for deciding which pawnless chess endgames are generally wins, versus which are generally drawn: WARREN'S PAWNLESS ENDGAME RULE: In a pawnless endgame with 6 men or fewer (this includes kings): Compute the total material points for both sides using the (very nontraditional!) N=4, B=3, R=7, Q=24, bonus if own two bishops of opposite colors=5, penalty if own two knights=3, bonus if own both a rook and a non-rook=2, bonus if own two rooks=6, penalty if own "loner queen" facing 2 or more enemy officers=6, Let M>=0 be the difference between these two material points totals. If M>6.5 then WIN. If 0<=M<6.5, then DRAW. Allegedly the only exceptions are: the KQknn endgame, which is generally a draw although 24-5=19>>6.5; the KNNBkn and KNNBkb endgames, generally wins; and KBBNkb with the BBs having same square-color (not of great importance!) which is a draw. I am not sure what the KQQkqr ending usually is (win or draw?) but by redefining the word "non-rook" in the final bonus if necessary, it should be able to handle this also. It might also be able to handle quite a few of the most common 7-man cases, but I have not checked and an additional term might then be needed.

3 2

Re: [math-fun] Computer Chess Critic ...
by Guy Haworth 26 Mar '14

26 Mar '14

The International Computer Games Association (ICGA), http://www.icga.org/, used to offer a prize for the best-commentating chess program but this did not attract sufficient interest. More recently, and partly because of an increased incidence in computer-aided cheating in human tournaments, there has been considerable activity in rating chess players on the basis of their moves rather than on the, e.g., 'ELO'-basis of the results they achieve in games. There are three approaches here: 1) 'Coincidence'. Notice that a player is playing the same moves as one's computer, searching to depth 'd'. This is the least mathematical way, and uses the least information. It scores a 'coincidence' even if there is no choice of move. It scores a 'non coincidence' if there are two 'equivalent' moves given the same evaluation, and the player chooses one the computer does not choose. 2) 'Average error'. If 'mb' is the best move, and the human loses 'pa' evaluation points (as evaluated by the computer searching to depth 'd') by playing move 'ma', then: Average error = average (pa) This uses more information but again, evaluation of a player is affected when a player plays a move which is the only one available. 3) 'Competence inferred by Bayesian Inference'. This hypothesises a range of stochastic 'model players' which choose a move randomly. The probabilities of choosing a move depend on the evaluation 'pi' of one's computer (searching to depth 'd') and the competence index 'c' of the stochastic players. One then infers the probability of the observed player being stochastic model-player 'i' in the available set of stochastic players. This is the approach I have taken as seen at http://centaur.reading.ac.uk/view/creators/90000763.default.html ... ... anything after 2001 mentioning 'fallibility', 'reference', 'Bayes' etc ... most recently http://centaur.reading.ac.uk/29423/ It uses more information than methods 1-2 and so should be more sensitive/accurate in ranking players - but how much better is not clear. Method 3 would be expected to give very similar results to the method of Ken Regan which uses a range of explicit, parameterised models - consciously trying to model chess-play. Method 1 has inferred that Capablanca played most accurately in his World Championship matches, and he certainly has a reputation for so doing. Capa was, as it were, playing 'The Goddess of Chess' whereas more recently, players have played on their specific opponent's known fallibilities to win - rather than playing the neutrally-objective best-move. At the FIDE Candidates Tournament in London, 2013, the audience were given tablets and a chess-app which compared the two sides' material, mobility, King-safety and overall advantage - an improvement on just giving overall advantage. Guy Haworth

1 0

[math-fun] how many chess positions?
by Warren D Smith 24 Mar '14

24 Mar '14

Ignore the 3-time repetition and 50-move rules. What is the number P of chess positions reachable via a legal game? Finding the exact answer is too hard, but finding good upper & lower bounds is doable. A "position" should know what the pieces are, where they are, who is to move, what are the castling rights, and what the available en passant captures (if any) are. Note that pawns can only be located on ranks 2-6, not 1,8; and that if M pieces and P pawns have been captured, then at most 2*M+3*P promotions could have happened. And many pawn configurations are impossible unless enough captures happened... John Tromp claimed P<=7728772977965919677164873487685453137329736522=2^152.437 as the result of a computer program he has not described, but this is unlikely to be optimal (assuming it is correct). For somebody determined enough: I think it should be possible to determine the answer accurate to 5% by first creating a good encoding scheme, say which proves P<2^155, and then sampling random positions for each deciding if it really would be reachable. Assuming deciding reachability is actually feasible 99.999% of the time, and assuming P>2^144, we would after 2 million random samples find at least about 1000 reachable positions and at most about 20 whose reachability was unknown. This would be good enough for a 5% accurate (Monte Carlo) estimate. If P<2^150, then the proof tree of chess (at least ignoring 50-move rule) would presumably be about 2^75 positions, suggesting chess might actually be feasibly solvable (?!). -- Warren D. Smith

1 0

Re: [math-fun] matrix semigroup, eigenvalues problem
by Warren D Smith 23 Mar '14

23 Mar '14

> I. The boundedness of all products of a pair of matrices is undecidable, > Systems & Control Letters 41 (2000) 135-140 > by Vincent D. Blondela & John N. Tsitsiklis > http://web.mit.edu/jnt/www/Papers/J081-00-vb-products.pdf --and as a result of this, Lunnon's problem of finding a sharp upper bound on c, is undecidable, in particular it is undecidable whether c<=1. So you will in general have to be satisfied with non-sharp upper bounds got by e.g. matrix-norm techniques -- lower bounds are also producable by computer exploration of many words -- or hope for miracles e.g. if you have a particularly nice set of generators in mind, you may be able to solve it. As some joker once said, "I solve undecidable problems all the time." (Actually I think the joker was Roger Penrose, who had the asinine utterly incorrect idea that this "proved" human minds had super-Turing power.)

1 0

[math-fun] Computer chess critic
by David Wilson 23 Mar '14

23 Mar '14

Has anyone ever tried to teach a computer to critique chess games? To distinguish between amateurish, bland, impressive and truly great chess games? I feel like this might be easier than over-the-board analysis.

2 1

[math-fun] New class of polyhedra
by Robert Baillie 21 Mar '14

21 Mar '14

I hope I'm not repeating a post, but I ran across an interesting article today in Science News: "Goldberg variations: New shapes for molecular cages" https://www.sciencenews.org/article/goldberg-variations-new-shapes-molecula… The original PNAS article is blocked unless one can break in or pay $10 to read it. The best description I've found on-line is: http://noiselesschatter.com/2014/02/25/polyhedra-and-the-media/

5 6

Re: [math-fun] matrix group with bounded eigenvalues
by Adam P. Goucher 21 Mar '14

21 Mar '14

Yes, Asimov's Law only applies if the matrices are orthogonally diagonalisable (<==> real symmetric). For other matrices, the `maximum length scale factor' can exceed the magnitude of the largest eigenvalue (e.g. in the case of a simple shear, where the eigenvalues are both unity). Sincerely, Adam P. Goucher > ----- Original Message ----- > From: Dan Asimov > Sent: 03/21/14 05:20 PM > To: math-fun > Subject: Re: [math-fun] matrix group with bounded eigenvalues > > I think I’ve verified what Jim says 32 ways from Sunday. I get > > (81/200)*(3+sqrt(5)) > > or about 2.12 for the largest eigenvalue. This is certainly counterintuitive from my naïve viewpoint. > > —Dan > > > On Mar 21, 2014, at 9:36 AM, James Propp <jamespropp(a)gmail.com> wrote: > > > I don't think this Dan'a guess is true. Consider the non-commuting matrices > > .9 .9 > > .0 .9 > > and > > .9 .0 > > .9 .9 > > Each of them has eigenvalues strictly inside the unit disk, but their > > product doesn't. > > > > (Unless I made a mistake, in which case, please let me know!) > > > > Jim > > > > On Friday, March 21, 2014, Dan Asimov <dasimov(a)earthlink.net> wrote: > > > >> If the eigenvalues are *strictly* inside the unit circle, then I would > >> expect the matrices to each be a contraction mapping on their vector space > >> (with some contraction constant L < 1 equal to the maximum |eigenvalue|). > >> > >> So then wouldn't a composite of finitely many of these matrices also be a > >> contraction mapping, with contraction constant equal to the maximum of the > >> finitely many contraction constants pertaining to each matrix in the > >> composite? > > > _______________________________________________ > math-fun mailing list > math-fun(a)mailman.xmission.com > http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun

3 3

[math-fun] matrix group with bounded eigenvalues
by Warren D Smith 21 Mar '14

21 Mar '14

AP Goucher: Yes, Asimov's Law only applies if the matrices are orthogonally diagonalisable (<==> real symmetric). WDS: it is not correct that orthogonally diagonalisable <==> real symmetric; Any matrix M that commutes with its transpose is orthogonally diagonalisable. WF Lunnon: Now wants, given any finite set of matrices, to prove any product of n of the matrices has all eigenvalues e obeying |e|<c^n for some positive constant c. (Is that right? That is now your goal?) WDS: Well, isn't this immediately obvious by using "submultiplicative matrix norms"? The spectral norm and the Frobenius norm of the matrices are submultiplicative (so both should work), and the max |eigenvalue| is upper bounded by sqrt(FrobeniusNorm). End of proof. http://en.wikipedia.org/wiki/Matrix_norm

1 0

[math-fun] matrix group
by Warren D Smith 21 Mar '14

21 Mar '14

> Given a finite set of complex matrices generating an infinite group, > I need to establish that every element of the group has all eigenvalues > within the unit circle. --you lose. If so, then the inverse elements have reciprocal eigenvalues, which are outside the circle. QED.

2 1