March 2016 - mathfun@mailman.xmission.com

[math-fun] Lee Sedol wins game 4, humanity may not yet be complete toast (but almost)
by Warren D Smith 13 Mar '16

13 Mar '16

That was interesting and revealed how the monte carlo approach to go is flawed. LS had to be brilliant and play some "improbable" moves the machine may not have appreciated until too late. He did. As a result, LS got a won position by a small but clear (to strong players) margin (don't know exactly, but let's say 2-5 points), but to do so LS used up all of his 2-hour time budget plus two of his three overtimes. Meanwhile AG had only used up 1 hour. From then on, the rules were LS had to make every move within 1 minute. So at that point, if LS had been up against a top human (TH), TH would have tried to complicate and pose LS one or two difficult problems, which hopefully he'd be unable to solve in 1 minute. Hence LS would either lose on time or risk giving up his advantage via a mistake. There was still enough scope for creating complexity for this. Also, TH could have used his spare hour to think a lot of it out ahead of time, then sprung it on LS suddenly with quick moves in 1 second each. That would mean LS could not think on TH's time when it got difficult. But no. AG instead played a few totally stupid and pointless time-waste moves (even I could see that), as well as playing a lot of trivially-easy-to-answer forcing moves. That took the heat off and gave LS an easy ride to the win. Also AG's time-usage algorithm is very uniform. Completely uniform would be to always use exactly 1 minute per move (say), and while AG is not completely uniform, it is fairly close to it, much more so than a human. A human will play an easy move in 2 seconds. AG will grind on for 30 sec. So what is the matter with monte carlo go? AG works as follows. It looks ahead and then evaluates a leaf position P. The eval(P) is a linear combination of (i) a neural network(P) estimating win probability, and (ii) play out N "random games" from P to end (or what it thinks is the end, anyhow) finding how what percentage it would win. The random games use random moves generated from the approximately-human move probability distribution from its "policy neural network." (iii) the coefficients in the linear combination depend on N and are tuned to maximize experimental performance. This approach works badly when the position is "clearly won" or clearly lost. Because then, even for large N, essentially all the random games are wins (or losses) meaning part (ii) generates little or no useful information, and most of the "signal" is actually random "noise." Part (i) to some extent saves them from that pathology, but not enough, especially since they trained it to output win probability, not to output predicted final score. As a result, monte carlo go will in won positions decide between move A and move B , assuming they both win, largely at random. Ditto in lost positions. That's not the smartest way to play won positions -- although usually good enough -- and definitely it's not the smartest way to play lost positions when your opponent is in severe time trouble! How could this problem be cured? Well, the cheap and easy fix would be, also make the neural net predict final score and final territory, which by the way would be 361 bits of learnable info per training position, not merely 1 bit, so it'd learn 361 times faster. Also make the monte carlo in step (ii) know about score not just winning. Then in a lost position, let's say some node's winprob estimate was P=0.05. Really, due to random noise, (which should be estimated by the computer) it is, say 0.05+-0.03. My point is, if & when the noise is comparable to or larger than the signal, then it is worth looking at final score estimates too. Although those are the wrong signal (winning is the "only thing" said football coach) they happen to be a better quality source of signal, supplying more bits, enabling better signal/noise ratio if you used it appropriately rather than ignoring it. I believe this would improve the machine's play in won and especially in lost positions. Now the more correct fix is to employ "BPIP search" (invented by me about 20 years ago) not UCT monte carlo search, which is sort of a flawed randomized approximation to BPIP. Nobody in the AI community paid much attention to BPIP search, and now they are paying for that. BPIP involves eval(P) which outputs a probability distribution, not a mere number. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 1

[math-fun] Is this true?
by David Wilson 13 Mar '16

13 Mar '16

x^x == k (mod n) is solvable for all k iff gcd(n, phi(n)) = 1.

3 3

Re: [math-fun] can't win by resigning
by Jim Gillogly 13 Mar '16

13 Mar '16

Now that Lee Sedol has won game 4 of the 5-game match (having lost the match yesterday with the third game), it looks like AlphaGo does indeed need some fine-tuning in the end-game. When it's behind at the end it seems to try cheap tricks that might work on kyu-level players, and make forcing moves that delay the inevitable even while losing a few more points. It eventually resigned - I don't know whether it's wired for that or whether its trainers threw its virtual towel into the ring. When it's ahead it makes what the commentator called "slack" moves - safe moves that take the pressure off the opponent. When I ran my chess program in several human tournaments in Pittsburgh (I still have its USCF membership cards for a couple of years in the early 70's-- that's before they stopped accepting computers) it would thrash around when it saw an inevitable mate coming, sacrificing material just to push the mate out another move. Looked bizarre. I resigned for it several times. Oh, the embarrassment. But the bug didn't seem worth fixing. AlphaGo's play is interestingly different from humans in another way: its evaluation ignores the amount of the win in order to maximize the probability of a win. This led to the third game, for example, seeming closer than it was - AlphaGo apparently had other aces up its conduits if it had run into trouble. Many players will attack anything attackable just to finish off the game. Bobby Fischer wasn't satisfied with winning his chess games - he felt he had to crush his opponents. > From: Gareth McCaughan <gareth.mccaughan(a)pobox.com> > > On 10/03/2016 17:19, Warren D Smith wrote: > > > Well, if software testers refused to try to find bugs due to "etiquette" > > then there would be a lot more bugs. > > My guess as to the actual question here: once the game > gets near the end, I suspect AlphaGo's tree search will > produce extremely strong play even if its neural networks > mess up. So even conditional on the scenario you describe > where AlphaGo's training hasn't equipped it to evaluate > things well in unusual positions, I think it's very > unlikely that playing on would have given Lee Sedol > a non-negligible extra chance of winning. > -- Jim Gillogly

4 4

[math-fun] Grabbing Cubes
by Mike Beeler 12 Mar '16

12 Mar '16

I tried 4 tie breaking rules, applied when more than one candidate cube has the same (maximal) size of family that would be removed. If the rule leaves more than one candidate, the one with smallest index x+5y+65z is chosen, where box dimensions in x, y, z are 5, 13, 31 and x, y, z begin at 0. A) Remove cube closest to any corner of the box. B) Remove cube closest to center of any edge of the box. C) Remove cube closest to center of any side of the box. D) Remove cube closest to center of the box. I was surprised that all four rules make games that end after 65 moves. Maybe it’s time to look for a proof. However, the number of cubes Alice and Bob end with differ: A) Alice 1023, Bob 992 (like Taylor and Jamie found) B) same as A C) Alice 1025, Bob 990 D) Alice 1021, Bob 994 Perhaps Dmitry (Alice 1024, Bob 991) had yet another tie breaking rule. — Mike

5 9

[math-fun] N-dimensional rotation matrix decomposition
by Tom Karzes 12 Mar '16

12 Mar '16

I have a question about a particular type of decomposition of N-dimensional rotation matrices. The specific types of matrices I am considering are orthogonal matrices (the rows form a set of orthogonal unit vectors, as do the columns). Further, I am only considering the case where the determinant is 1 (as opposed to -1). I.e., I am disallowing reflections. I am interested in factoring such a matrix into a sequence of "primitive rotations" (I'm not sure what the proper term is). By this I mean rotations which only affect two coordinate axes. This defines a rotation within a plane, with the restriction that the plane be the product of two of the standard coordinate axes. For an N-dimensional matrix, there are (N take 2) = N*(N-1)/2 possible pairs of axes. For example, in 3 dimensions they are XY, XZ, and YZ. Any such rotation matrix, as defined above, can be factored into a sequence of N*(N-1)/2 primitive rotations, which each pair of axes occurring exactly once. I know certain orderings will work. One such ordering is to first perform all rotations involving some particular axis, then perform all remaining rotations involving some other particular axis, etc. For instance, in 4 dimensions, the sequence could be (a1,a2), (a1,a3), (a1,a4), (a2,a3), (a2,a4), (a3,a4). The opposite ordering can easily be shown to work as well, i.e. (a3,a4), (a2,a4), (a2,a3), (a1,a4), (a1,a3), (a1,a2). My question is this: Can *any* fixed ordering be made to work, for any such rotation matrix? Or do only some orderings work? Some observations: There are a number of transformations that can be performed on any ordering to produce a new ordering which will work. In some cases the rotation amounts can be preserved. In others, the rotation amounts need to change. Here's an example of a transformation that works in 4 dimensions: (a1,a2), (a1,a3), (a2,a3), (a1,a4), (a2,a4), (a3,a4) Here I have have swapped adjacent primitive rotations (a1,a4) and (a2,a3). This can always be done, without changing the rotation amounts, since they have no coordinates in common. But what about the case where they do have a coordinate in common? In three dimensions, we know that any order works, so XY, XZ, YZ works, and so does XY, YZ, XZ, although when switching from one to the other, in general all *three* rotation amounts must be changed. Does anyone know the answer to this? In N dimensions, will any fixed ordering work? Or do only some fixed orderings work? Tom

5 7

Re: [math-fun] can't win by resigning
by Warren D Smith 12 Mar '16

12 Mar '16

Actually, the go endgame isn't just "tidying up the boundaries": I can just invade your territory. If you play right my invasion will eventually die, it was unjustified, so humans do not do it. (Except: if it is a pro versus me, he'd likely do an unjustified invasion anyhow because he'd guess I'd often be too dumb to respond correctly.) But my point is, all those invasions and refutations always are there like a sleeping volcano beneath the surface, strong humans just never play them and their refutations, since it'd be a waste of time; they just agree to end the game. It doesn't hurt your score in chinese rules if you play an unjustified invasion which gets killed, so in principle you should try it. What that also means: the part of alphago's training that was based on strong human games, contained zero examples of that stuff! So maybe if Lee Sedol tried it, alphago would mess up. I guarantee you, it has a higher probability of working than resigning. Also, presumably alphago usually works well, but even its designers really do not understand why and cannot guarantee it will not do something crazy next move. It really is an AI in the sense that nobody understands what it is thinking and there is no way it could explain it to us. Unlike, say, today's strongest chess programs, which I feel I pretty much totally understand -- they have human designed evaluation functions with some parameters tuned by fairly crude automated methods, but the whole evaluation function is something a human understands. That again, means if Lee Sedol took more of a software tester attitude, it could pay. Anyhow, LS has been rocked! There was a little press interview with LS after, and he looked a bit like he might break into tears. He said he just could not believe the machine could beat him, and even when LS felt he was behind, he still figured it was just a matter of time before machine would find a way to blow it. :) -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)

2 3

[math-fun] pi day, pizza hut, conway,
by Simon Plouffe 12 Mar '16

12 Mar '16

hello, apparently there is a contest sponsorized by pizza hut, actualy there is a contest where you can win 2 years worth of pizza, ... no questions ask, just give your name and address, you just need to live in continental usa (+ hawaii, alaska). I looked up for any math question but there are none, it is just a publicity for pi day, pizza and john conway. Best regards, Simon Plouffe http://blog.pizzahut.com/tag/contest/

2 1

[math-fun] what is the Fibonacci salad ?
by Simon Plouffe 12 Mar '16

12 Mar '16

Hello, thought of the day, Fibonacci salad: For today's salad, mix yesterday's leftover salad with that of the day before. Simon Plouffe

2 1

[math-fun] Isn't "The lesser of two evils"
by Henry Baker 11 Mar '16

11 Mar '16

inherently ambiguous in English? After all, if evil is a negative thing, then wouldn't "the lesser of two negatives" would be the worser thing ? Perhaps teaching coding in public schools might be a positive thing after all... Jus' sayin'... (Or perhaps people misheard the advice as "the lessOr of two evils" ???)

8 9

Re: [math-fun] Filling a much-needed gap
by Jim Gillogly 10 Mar '16

10 Mar '16

Dan Asimov writes: > Which reminds me of an oft-repeated bit of math folklore: > > A review of a certain math paper read: "This paper fills a > much-needed gap in the literature." > > I wonder if this is apocryphal. Or is it pocryphal? The pocryphality of this review is discussed at length in one of my favorite sites: Quote Investigator. Part 2 is here: http://quoteinvestigator.com/2010/05/03/fills-a-much-needed-gap-pt2/ and it includes a link to Part 1. Executive summary - it's appeared as unintentional humour, and nearly made it into print intentionally. Though attributed frequently to Moses Hadas, the Quote Investigator was unable to locate it in his work. It did not quite appear in Mathematical Reviews. -- Jim Gillogly

1 0