[weylfetj] Watching computer chess for a long time

Have a computer play chess against itself for a long time, months to years.  What about this might be entertaining for people to spectate?

One thing that probably won't be entertaining is a single game with a very long time control.  It will probably be a boring draw.  It is also a bad fit with technological advancement.  Computers (and software) become better over time, but a game becomes easier over time, with fewer and fewer pieces.

Three possibilities likely more entertaining:

1. Watch the development of opening theory.  Let the computer play many games against itself and do Monte Carlo tree search, probably also with reinforcement learning as Alphazero did.

As the computer becomes more powerful over time, the opening transposition table can become larger, neural networks can become larger, searches can become deeper and wider.  All of these (hopefully) lead to improvement in opening play.

A human spectating the computer's development, giving it attention occasionally, can query, what are the most interesting changes the computer discovered in opening theory since the human last checked?  Why did those changes occur?  (The reason may be because of a discovery of a key move, and continuation, that busts a line previously believed to be good.)  These are the same questions one asks about the development of opening theory in human games.

Some difficult UI issues: how can a computer quantify how interesting a change to opening theory is?  How can a computer explain why a opening is better?

2. Watch the development of endgame theory.  The simplest version is a progression over time of the computation of endgame tablebases from few pieces to more.  Again, this sort of lines up with computers becoming more powerful over time.

On one hand, it doesn't line up too well computers becoming more powerful because a tablebase of N+1 pieces requires so much more computing power than N that one may have to wait years for computers to become powerful enough to go one piece more.

On the other hand, there are some incremental steps that may be entertaining to spectate that require less computation than calculating a whole tablebase.  Find the positions one more step away from checkmate (or reduction) than previously calculated.  Show the interesting positions.  Keep refining machine learning to compress better existing tablebases or portions thereof.  Show interesting positions that the machine learning algorithm "recently" learned to play or classify correctly, and explain how it's doing so.  (But neural networks are especially bad when explanations of how or why are desired.)  Again, there are a bunch of UI issues, including how to quantify "interesting".

3. We reconsider a variation of the initial rejected idea of a single deeply calculated game of a computer playing itself.  Assuming we can quantify "interesting", we can have the computer play many not-so-deep games against itself and provide to spectators only the most interesting ones, at a rate tuned and suitable for the attention humans will give it.  (Probably around 1 game per week.)  Or maybe instead of an interesting game, just an interesting position that occurred in a game.  Humans will demand higher thresholds of interestingness over time: they become bored of things similar to what they have already seen.  The computer becoming more powerful over time can play more games, filter more exclusively, and deliver higher interestingness over time.  This repeated self-play could also be part of a Monte Carlo framework described above for improving computer play.

We don't have to limit to orthodox chess.  Consider calculating these on Chess960 and other chess variants.

[ijsjqque] Maze with walls of different heights

Instead of a maze with impenetrable walls, make them of varying heights which can climbed over with varying amounts of effort.

Inspired by labyrinths in Zelda BOTW whose walls can be climbed over (though they are all the same height).

Get to the goal with the least amount of effort.  Or, the player can choose how difficult the maze is by self-imposing constraints on the amount of climbing.

From another perspective, it's a 3D shortest path problem, especially if you are allowed to walk on top of walls.

This simplifies the problem for the maze designer who doesn't have to worry about making a maze that is accidentally unsolvable or too easy.

What distribution of wall heights yield entertaining mazes?

[etserisd] Random tree in a growing sphere

Root node at center surrounded by equally spaced concentric circles.  First concentric circle of radius 1.  Its circumference is approximately 6, so put 6 child nodes on the circle all connected to the center root node.

Second circle radius 2, circumference approximately 13.  Put 13 nodes on it, each node connected independently randomly to 1 of the 6 parents of the first circle.

Repeat for larger circles.  Each node on a circle uniformly randomly chooses a parent from among the nodes in the previous (inner) circle.

Graph layout problem: arrange the nodes on each circle nicely.  Edges shouldn't cross.  Nodes on a circle should be well separated.  Edges between parents and children should be short.  Color nodes to be able to tell how related they are: most recent common ancestor.  Reuse colors if a subtree dies out.

Repeat for 3D: concentric spheres.  On a given sphere, descendants of a common ancestor will probably clump geographically.

Simpler "1D" version: do it on a strip (or tube).  The number of nodes (population) stays constant between generations.

Population of a circle or sphere does not have to be proportional to circumference or surface area.  Maybe permit exponential growth.  It could be interpreted as a sequence of constant sized spheres over time with increasing population density.

[ftubmcnk] Generating a technology "tree"

Consider a game about obtaining items.  For each item, obtaining it requires having already obtained its set of prerequisite items.  This kind of mechanism is seen, for example, in games in which gaining an ability (skill, technology) requires first gaining other abilities.  Or completing some quests opens up other quests.

We consider randomly generating such a collection of prerequisite dependencies.  First, (totally) order the items.  For each item, select a subset of items before it in the total order as the prerequisites.  Some items might have no prerequisites (so they are easy to obtain); some may have many.  All the prerequisites in a set must be satisfied in order to obtain the item (Boolean conjunction).

At this point, because we started with a total ordering, there are no cycles among dependencies, so every item is reachable.  It could be drawn as a directed acyclic graph, but that representation becomes less useful for what we are doing next.  (If all the prerequisite sets contain exactly one item (except the root, which has an empty prerequisite set), then that graph would be a tree.  If every prerequisite set has zero or one items, then the graph would be a forest.)

Next, for every item, give it zero or more alternative prerequisite sets.  Each alternative prerequisite set is an alternate way (Boolean disjunction) of satisfying the prerequisites for getting the item.  This resembles Disjunctive Normal Form in Boolean logic (sum of products), except there are no negated literals (never a penalty for having an item).  These alternative prerequisites can include items coming after the item in the total ordering established above.  It is OK to create cycles because we've previously ensured an acyclic way to reach every item.

To simplify computation, restrict the possible prerequisite items of a given item to within a window (forward and backward) of the given item in the total ordering.  Items with no prerequisites must be within the window around the beginning of the total ordering.  This allows answering the question "given the items I currently have, what can I immediately access?" without having to search too far forward in the total ordering.  This restriction allows the number of items to be infinite, with prerequisites generated on the fly as they fall within the windows of items you already have.  The prerequisites for an item can be generated using a pseudorandom number generator seeded by the item's unique identifier.  (An easy such an identifier would be its number in the total ordering.)  Despite an infinite number of items, generating and doing queries against such a seemingly complicated infinite collection of prerequisites requires very little space, probably logarithmic.  (However, keeping track of the items a player has already obtained requires n log n space.)  The factors of log n are for the size of each item's unique identifier or label.

What should be the probability distribution of the number items in a prerequisite set?  What should be the distribution of the number of alternative prerequisite sets?  Although the items for the alternate prerequisite sets can be from anywhere within an item's window, what should be the distribution within the window from which prerequisites are selected?  Perhaps items nearer in the total ordering are required more frequently.  Similarly, what should be the distribution of prerequisites in each item's first prerequisite set, the one which obeys the total ordering?

Avoid creating impossible alternative prerequisite sets.  Avoid creating prerequisite sets which are monotonically more difficult than a different prerequisite set for the item; that is, satisfying the more difficult set necessarily satisfies the easier one.  Without introducing another constraint, testing for these situations might be difficult or impossible because of paths of arbitrary length among infinite items: go forward then back in the total ordering.

It is an abstract maze (perhaps the goal is to reach a certain item), but there isn't a need for the kind of backtracking seen in solving SAT in CNF with negated literals.  The penalty for choosing to get the "wrong" item is resources wasted making no progress toward the goal.  What choices to the above questions tend to make it an entertaining maze?

[axuqcsaj] Primes 2 away from a perfect power

Numbers of the form b^n +/- 1 get a lot of attention (Fermat primes, Mersenne primes, Cunningham project).  We go off the beaten path and examine b^n +/- 2.  These numbers can be prime if b is odd.

We restrict our attention to numbers less than 2^1200.  We restrict our attention to numbers with b<=n, i.e., the exponent is equal to or larger than the base, i.e., top-heavy.

Here is some Pari/GP code to find primes of the form b^n+2, also printing out its size in bits.

thresh=1200 ; for(i=3 , +oo , if( i*log(i)/log(2) > thresh , break) ; if(i%2 && (isprimepower(i)<2) , for(j=i , +oo , p=i^j+2 ; z=log(p)/log(2) ; if(z>thresh , break) ; if(ispseudoprime(p) , print(i , " ^ " , j , " + 2 " , z)))))

Below we list all the primes of both forms, sorted by size.

There are 182 primes on the list.  73 are +2.  109 are -2.  Is this disparity expected?

The first (and only) instance of base 11 on the list is 11^287+2.  There are no primes 11^n-2 for 11 <= n <= 13000.  (However, 11^4-2 and 11^6-2 are non-top-heavy primes.)  Is 11 especially sparse?  If so, why?

3^4+2 and 7^12-2 are the only safe primes on the list.  Intriguingly, the multiplicative group order of prime b^n+2 is b^n+1, which is a Cunningham form.

The only cousin primes (primes separated by 4) straddling a perfect power on the list are around 3^4 (79 and 83) and 51^66.

3 ^ 3 + 2
3 ^ 4 - 2
3 ^ 4 + 2
3 ^ 5 - 2
3 ^ 6 - 2
3 ^ 8 + 2
3 ^ 9 - 2
3 ^ 10 + 2
7 ^ 7 - 2
3 ^ 14 + 2
7 ^ 8 - 2
3 ^ 15 + 2
5 ^ 14 - 2
7 ^ 12 - 2
3 ^ 22 - 2
3 ^ 24 + 2
5 ^ 17 + 2
3 ^ 26 + 2
7 ^ 15 - 2
3 ^ 36 + 2
3 ^ 37 - 2
5 ^ 26 - 2
15 ^ 16 + 2
3 ^ 41 - 2
15 ^ 17 - 2
15 ^ 19 - 2
15 ^ 20 + 2
7 ^ 28 - 2
19 ^ 19 - 2
19 ^ 20 - 2
7 ^ 31 - 2
21 ^ 21 - 2
19 ^ 23 - 2
17 ^ 24 - 2
3 ^ 63 + 2
21 ^ 24 + 2
23 ^ 24 - 2
21 ^ 25 - 2
5 ^ 50 - 2
21 ^ 27 - 2
17 ^ 30 - 2
21 ^ 32 - 2
3 ^ 90 - 2
3 ^ 98 + 2
19 ^ 38 - 2
3 ^ 102 - 2
3 ^ 105 - 2
3 ^ 110 + 2
21 ^ 40 + 2
23 ^ 39 + 2
3 ^ 123 + 2
15 ^ 51 - 2
3 ^ 126 + 2
15 ^ 52 + 2
29 ^ 42 - 2
3 ^ 139 + 2
7 ^ 84 - 2
15 ^ 65 - 2
35 ^ 50 - 2
21 ^ 60 - 2
7 ^ 98 - 2
45 ^ 52 - 2
13 ^ 78 - 2
51 ^ 51 - 2
5 ^ 126 - 2
15 ^ 75 + 2
13 ^ 80 - 2
33 ^ 60 + 2
29 ^ 63 + 2
5 ^ 143 + 2
13 ^ 90 - 2
5 ^ 144 - 2
31 ^ 69 - 2
7 ^ 128 - 2
3 ^ 235 + 2
51 ^ 66 - 2
51 ^ 66 + 2
3 ^ 243 + 2
21 ^ 88 - 2
57 ^ 67 - 2
51 ^ 69 - 2
51 ^ 72 + 2
43 ^ 76 - 2
15 ^ 106 + 2
63 ^ 70 + 2
29 ^ 87 + 2
35 ^ 83 + 2
17 ^ 105 + 2
13 ^ 117 - 2
17 ^ 106 - 2
15 ^ 112 + 2
59 ^ 75 + 2
13 ^ 120 - 2
71 ^ 74 - 2
61 ^ 78 - 2
21 ^ 106 - 2
35 ^ 92 - 2
57 ^ 81 + 2
39 ^ 93 + 2
21 ^ 112 + 2
3 ^ 315 + 2
3 ^ 317 - 2
15 ^ 132 + 2
39 ^ 99 + 2
21 ^ 120 - 2
31 ^ 109 - 2
35 ^ 110 - 2
45 ^ 104 + 2
65 ^ 95 + 2
3 ^ 363 + 2
69 ^ 96 - 2
83 ^ 92 - 2
87 ^ 92 + 2
5 ^ 260 - 2
5 ^ 261 + 2
3 ^ 386 + 2
3 ^ 391 + 2
37 ^ 119 - 2
45 ^ 114 + 2
47 ^ 113 + 2
91 ^ 97 - 2
93 ^ 98 - 2
21 ^ 146 - 2
33 ^ 128 - 2
7 ^ 238 - 2
69 ^ 111 - 2
87 ^ 106 - 2
39 ^ 132 + 2
77 ^ 113 + 2
99 ^ 109 - 2
45 ^ 135 + 2
95 ^ 113 + 2
17 ^ 184 - 2
61 ^ 127 - 2
103 ^ 113 - 2
69 ^ 127 - 2
3 ^ 494 + 2
75 ^ 128 - 2
3 ^ 520 - 2
51 ^ 146 - 2
73 ^ 136 - 2
115 ^ 123 - 2
7 ^ 302 - 2
33 ^ 169 - 2
3 ^ 541 - 2
63 ^ 144 + 2
105 ^ 129 + 2
87 ^ 136 + 2
55 ^ 153 - 2
95 ^ 135 + 2
3 ^ 561 - 2
93 ^ 137 - 2
29 ^ 189 + 2
113 ^ 135 + 2
17 ^ 232 - 2
133 ^ 136 - 2
65 ^ 161 + 2
69 ^ 159 - 2
111 ^ 144 + 2
69 ^ 161 - 2
115 ^ 144 - 2
45 ^ 180 - 2
11 ^ 287 + 2
123 ^ 144 + 2
87 ^ 156 + 2
3 ^ 648 - 2
45 ^ 190 - 2
53 ^ 184 - 2
39 ^ 204 - 2
33 ^ 218 + 2
35 ^ 220 - 2
39 ^ 216 - 2
153 ^ 158 + 2
39 ^ 217 + 2
21 ^ 264 - 2
29 ^ 239 + 2
43 ^ 214 - 2
57 ^ 200 - 2
117 ^ 171 - 2
91 ^ 181 - 2
137 ^ 166 - 2
111 ^ 176 + 2