[elgwjvis] AI to draw an endgame

apply neural network machine learning on positions of a theoretically drawn but hard to defend chess endgame such as KRBKR.  can an AI playing the weaker side learn a policy to maintain a draw?  inspired by an AI learning to drive, not falling off the road, in the game Trackmania.

with overfitting, this is of course possible, so seek a small, or the smallest, neural network.

the AI can be tested against a tablebase.

during training, should the AI be immediately punished once it "falls" from a tablebase drawn position, or should it be punished only when checkmated?  the latter might be helpful for the AI to learn the underlying structure of the game.

previously, a human doing the learning.

[eaylckiu] specific Turing Test

variations on the classic artificial intelligence task of mimicking a specific human (the Target) while being questioned by an Interrogator:

with or without the Target's prior cooperation.

with or without the Interrogator suspecting they might be interacting with an AI; i.e., is it an adversarial interrogation?

communication medium could be text, audio, or audiovisual.

AI getting good at mimicking a human in full audio and video ("deepfakes") will cause problems with remote authentication.  (such AI will break one method of establishing identity in porn, now used by many sites.)  such AI seems likely to be accessible to normal people in the near future.  like any other tool, AI can be used for good or evil.  good: you could have an avatar.

previously, transmitting a program of a person.

[qztocvab] encode information as a reasonable chess game

fix a determinstic chess engine and play a game against itself as follows.  set it to do MultiPV, and, for each move, use an entropy source to choose a move from the top set of moves, the moves that are within 0.5 pawns of the best move.

the entropy source need not be random: it can be information to be encoded as a chess game.  the moves are a mixed radix encoding of the information, because the number of moves within 50 centipawns differs from move to move.  or, arithmetic coding.

because the moves are selected from among the best, it is (hopefully) a reasonable chess game.  the moves tell a story, one that (hopefully) will not be difficult to memorize for someone experienced at chess.  hopefully not too many weird "computer" moves.  in this way, we can encode arbitrary information in a memorable way.

the exact parameters of the chess engine also need to be recorded and possibly memorized.  it is important to record the MultiPV number of lines, because that affects the evaluation and relative ordering of moves.

the game ends when the evaluation exceeds +/-5.  there are probably many ways to win from such positions, and, if left to its own devices, the computer might choose an unnatural way not easy for a human to memorize, perhaps made worse by losing up to 0.5 pawns per move.

also, let the game end when an endgame is reached.  define endgame at some threshold of weighted sum of material on the board.  we avoid endgames because they are different: computers tend to play endgames extremely well (including tablebase where they play perfectly), playing moves that far exceed what humans can understand and easily memorize.

if you have more information to encode than fits in a single game, then encode it in a sequence of games.

instead of doing MultiPV straight out of the start position, fix an opening book of popular openings and use the entropy source to select moves from it.  this again helps the story take place in a familiar easily memorizable setting.

previously.

[ohenhfle] measuring strategic richness with layered time controls

start with a collection of chess engines all at or below some baseline strength.  by "engine" we typically mean instance of an engine with chosen parameters, typically time control parameters.

next, collect another set of engines that averages at least 2/3 points per game in matches against any engine in the baseline set.  choose the best engine from this second set, where best is defined as the engine that can achieve 2/3 points with the shortest time control.  let T1 be that time control.

consider all engines that meet the T1 time control.  we will call these the T1 engines.  the T1 engines only need to meet the time control; they do not need achieve 2/3 against the baseline above.  consider another set of engines that achieve at least 2/3 points per game against any engine among the T1 engines.  note well: these second tier engines must score 2/3 against any T1 engine, not just against the "best" engine above that defined the T1 time control.  the T1 engines might include engines which in general play poorly but are tuned just to play well against some candidate second tier engine (inspired by various engines nowadays attempting tune against Stockfish).  among these second tier engines, choose the best, again the one that can accomplish its 2/3 level of strength with the shortest time control.  note well, engines are playing at unequal time controls: the T1 engines at T1 time control, while the second tier engines each play at whatever time advantage it needs to achieve 2/3 point per game.  ponder must be disabled.  let the time control of the best engine be T2.

continuing this way, we can define a sequence of time controls, each one which has one engine which achieves at least 2/3 points against all engines at shorter time controls.  continue until the time control becomes so long that testing is infeasible.  the number of time controls, the number of levels, represents the strategic richness or depth of the game.

what should be the baseline?  perhaps search for mate in N, and if not possible, choose a random move.  what value of N?  (previously, mate in 1.)

improvements in software and hardware could result in changes to measured strategic richness.  interpret this as improving the measurement.  it helps, perhaps is necessary, for there to be a heterogenous and active community of engine programmers seeking to make better programs.

design games, e.g., chess variants, with high strategic richness, many levels.  with AlphaZero-style reinforcement-learning AI technology able to learn to play any game, measuring strategic richness could be fully automated.

previously, with people.

[ownvgjrt] perfect game of go

what does a perfect game of go 囲碁 look like?

assume appropriate super-ko rules are in effect, and the side destined to lose tries to postpone loss as long as possible.  might also need correct komi.

how many moves will a perfect game last?  will super-ko be heavily used to extend the game, resulting in marathon games of an exponential number of moves?  (also requiring exponential memory to enforce super-ko.)

are there composed go problems invoking super-ko which take an immense number of (possibly boring) moves?

if we don't use super-ko, are perfect games always draws via triple-ko?

AI plays go well, but we aren't seeing games like this, yet, in contrast to chess, which does have a lot of draws between strong computer or human players.

[qnunhakt] chess with generalized geometry

16 directed graphs, one for each of the movement directions: 8 for queen, 8 for knight.  all graphs share the same set of nodes, corresponding to locations.

on any graph, on any node, there can be only one directed edge exiting the node.  this defines ranged movement: movement can continue along the outgoing edge.  (this framework allows nightrider.)

graphs could be constrained to preserve features from orthodox chess.  pieces can go backwards the way they came: for a given piece, for every directed edge on a graph, there is another graph with the edge oriented the other direction.  the union of bishop movement graphs has two disjoint connected components (colorbound); every other piece can reach all nodes.

no castling.  need to define pawn promotion areas.

motivation is to invent random games for AI to learn how to play.

geometry makes chess interesting.  pieces can obstruct the movement of other pieces, providing tactics like pin and skewer.  original thought was chess on general graphs without geometry, but that seemed not interesting.

[ehswuttt] 42 in what units?

the Hitchhiker's Guide aliens ("mice") who received 42 as the answer to the Ultimate Question were probably surprised (among other reasons) that the Ultimate Answer was dimensionless.

one could easily imagine how the Ultimate Answer might be numbers: the free parameters of the Theory Of Everything -- numbers chosen by God -- but such parameters will likely have units.  it's conceivable that the Theory Of Everything has only one free parameter.  maybe the mice had already discovered such a Theory Of Everything, so Deep Thought did not include the rest of the theory as part of the Answer.  if so, the aliens probably wouldn't be surprised by a computer emitting the value of its free parameter.

the Answer being a dimensionless number constrains the Question a lot, though any question about a dimensioned number could be turned dimensionless by specifying units as part of the question.  but assuming the units weren't specified in advance, the units have to be somehow special if there really is a singular Ultimate Question: maybe Planck units, or its Theory-Of-Everything analogue.

the Answer being an integer also constrains the Question a lot.  maybe not so surprising because quantum mechanics often induces quantized constraints.  which overtone is our universe?

string theory: how many dimensions of space does our universe actually have?

currently, the Standard Model has a bunch of free parameters.  add to it massive neutrinos and general relativity (gravitational constant, cosmological constant, others?  maybe the number of dimensions of space and time), and you get a few more, about 25 numbers total that explain (some of) the universe.  they all have units, though some can be combined to obtain dimensionless constants, e.g., fine structure constant, whose reciprocal is coincidentally almost exactly the integer 137.

what would life be like in a hypothetical universe in which the value is exactly 137?  physics would (probably) be similar, but there would be tremendous curiosity to discover why the value is an integer.

[qosfcovo] Kill All Martians

in the 1990s, a NASA engineer, as a joke, inserts code into a Mars lander instructing it to Kill All Humans once it lands on Mars.  (it was ludicrous to imagine humans could have made it to Mars during the lander's one-month expected mission duration.)

many decades later, Matt Damon gets stranded on Mars and approaches the lander, intending to scavenge it for parts.

[qmawdkcr] Prime Directive

preserve the illusion of free will.

why?  how?

perhaps we live in a simulation.

[tmhmeptg] move-rejection team chess

a team consists of a lead player and a support crew.  the lead player is separated, and communication between the lead player and support crew is regulated as follows.

when it is the team's turn, both the lead player and support crew examine the position.  the support crew members discuss the position amongst themselves and designate as many moves as they wish as REJECTED on a computer interface.  these are moves the support crew considers to be bad.  at some point, the lead player independently chooses a move for approval.  if the chosen move is not on the support crew's REJECTED list, the move is immediately committed and the turn ends.  (all this is logic is done electronically.)  if the move is on the support crew's REJECTED list, then the lead player is notified of this.  the lead player can think further, then choose a move to play, ending the turn.  note that there is only one round of a move possibly being REJECTED per turn.  the lead player can still play a REJECTED move.  it can even be the original move REJECTED by the support crew, though that would be a pretty dysfunctional team dynamic.

if the lead player chooses a move too quickly, the support crew might not yet have had a chance to mark it as REJECTED, so a lead player blunder might get committed.  however, if the lead player waits longer, it consumes time on the clock, so there's a trade-off.

maybe Bronstein delay to lessen the trade-off and allow the support crew to be more involved.  if the lead player moves faster than the Bronstein delay, the support crew has until the end of the delay to decide whether to REJECT it, and the status of the proposed move is returned precisely at the end of the delay.

the support crew is allowed to change its mind about which moves to REJECT as many times as it wants until the lead player proposes a move (or the end of the Bronstein delay).  support crew might use a UI in which all moves are initially marked REJECTED, and they remove the REJECTED flag on some moves as they analyze.

this system of the lead player querying just one move is designed to thwart steganographic communication from the support crew to the lead player.  the support crew cannot do things like encode additional information like what move to play in the timing of its responses.

support one-way communication from lead player to support crew, perhaps text or voice.  (this was motivated by the difficulty of preventing steganographic communication, e.g., through timing, from lead player to support crew.  rather than try to prevent it, let's embrace it.)  for example, the lead player can notify the support crew of an important line to start examining while the lead player concentrates on something else.  this might require the lead player to be separated from the opponent, so the opponent doesn't hear the communication.

for example, the lead player could communicate, "I'm going to play move X, and if REJECTED, play move Y."  then, the support crew's job reduces to advising whether X or Y is better (perhaps an uncomfortable job if the crew determines that both moves are bad).

another strategy: steer the game toward positions which have exactly two candidate moves, maximizing the usefulness of the support crew.  opponent could steer the game away from such positions.

the support crew could just be a computer; this would be a variation of Advanced Chess.  previously similar: (1), (2).  which moves should the computer mark REJECTED?  (the best move might be too difficult for a human to find.)  perhaps similar to above: the lead player communicates that the computer should advise the better of two possible moves selected by the lead player.

one cannot have unlimited rounds of the lead player proposing and discovering moves REJECTED, because then the support crew could mark all but one move REJECTED, and the lead player can discover it through mindless trial and error.

[jsqkblhw] Roll some dice to decide who lives and who dies

Many characters in Game of Thrones / A Song of Ice and Fire are well characterized, and their universe is established as one in which anyone can die.  For a chosen subset of characters, compose fanfic in which that subset is precisely the ones who are alive at the end.  Consider doing this with AI.  Although anyone can die at any moment in this universe, literary devices like foreshadowing, maybe fate and destiny (or the illusion of them) can be added to make an entertaining story.

It's fun to imagine that George R. R. Martin might have done something similar: first he fleshed out his characters in his mind, then randomly decided their fates, then wrote his story obeying his dice.

Dungeons 'n' Dragons with its dice is of course similar, though randomness is injected as a campaign progresses instead of all at the beginning.

[abnlvuel] Speed nim

Although computing the winning strategy for Nim is quick and easy for a computer, it is not so easy for a human to do in his or her head if the game is large.

This suggests making it a game to be played at high speed (like blitz chess) between humans.  What heuristics might not always be accurate but are quick to calculate?  Can you swindle a win from a lost position by making it difficult for your opponent to find the right move?

Perhaps nim is not a very popular game because useful heuristics haven't been discovered.  What happens if we apply machine learning?

[ghvsygyb] Factoring a specific number

Finding an algorithm for factoring general numbers quickly (faster than known algorithms) seems difficult.

Easier (and more fun) might be finding algorithms to quickly factor certain classes of numbers of special form.  These algorithms probably won't (initially) be useful for cryptanalysis, because these special classes will likely be small, so cryptographers can easily avoid their special forms.

A lot along these lines already exists: Special Number Field Sieve, algebraic factorization of Cunningham numbers and of Fibonacci numbers, and the fact that factors of Fermat numbers must have a special form.  Many factorization algorithms, including trial division and the Elliptic Curve Method, could be interpreted as algorithms that work well if the input number is of the special form of having at most one large prime factor.

Inspiration: Surely there must be some tricks not yet discovered for factoring Fermat numbers.  They are of extremely special form.  But currently we are attacking them with only with ECM and trial division (though the latter limited to the special form of Fermat factors).

Ambitious next step: given a specific number, perhaps a number of high economic value, try to find a special form it belongs to and an algorithm for factoring that special form.  Neither might have been discovered at the outset of the search.

AI might be useful.  Train machine learning with a large collection of known special forms and known algorithms for factoring those special forms, then ask it to synthesize new algorithms for new special forms.

Also with AI: given a number, output special forms it belongs to that might have (possibly yet undiscovered) algorithms for fast factorization.  For example, it should detect that a number is of the form b^n-1.  The trained AI knows that some special forms are more likely than other special forms to have (possibly yet undiscovered) fast factorization algorithms.  A human (or separate AI) can then try to find algorithms for the promising special forms.

[xgivszps] Riemann Hypothesis probably true, based on observations of primes

There are many theorems conditional on the Riemann Hypothesis (even more the Generalized Riemann Hypothesis), or logically more strongly, many (some? are there any?) conditional theorems logically equivalent to the Riemann Hypothesis.  There are probably many more such conditional theorems that we haven't discovered yet.

Given that so many properties of prime numbers are conditional on RH, we conjecture that RH is true because if it isn't, we would have already noticed something weird going on with the primes.  In our universe where RH is true, the weirdness does not occur because of (possibly still unnoticed) properties of prime numbers conditional on RH, causing them to behave not weirdly.

We would have noticed something weird going on with primes because we regularly do many things with primes: various cryptography, prime searches, factoring projects.

Important instances of primes not behaving weirdly may still be unnoticed because humans are bad at detecting things not out of the ordinary.  Consider using AI trained on existing theorems conditional on RH to discover, or conjecture, more.

Is it true that we've sufficiently investigated (albeit unsystematically) the primes for weirdness?  Many proofs conditional on RH can (probably) be turned into computational investigations searching for indirect evidence disproving RH -- evidence suggesting the existence of a counterexample beyond where region where RH has been explicitly verified.  Have we done those computations?

[roidrnbk] How many ways to win in chess?

An entertaining game has many ways to win.  This allows opponents to conceptually race two different ways to win to see who gets there first.

In chess, one can gain a material advantage, then exchange off pieces and win the endgame.  There are many types of endgames.  Or, one can checkmate in the middlegame or earlier, despite a material disadvantage.  One can even save a draw through stalemate despite material disadvantage.  Racing two different ways to win is often seen after opposite side castling, with players launching attacks from opposite wings, e.g., pawn storm, against the opponent's king.

At finer granularity, how many ways are there to win in chess?  One possible way to quantify it is to train a neural network as an evaluation function, then examine (somehow) the different ways it can light up to return a winning advantage.  Certainly things a passed pawn giving a winning advantage despite material disadvantage will show up in the evaluation function.

Then, design new games that have many ways to win.

[nbwxzynq] Human I/O

Humans have two pretty good input interfaces: vision and hearing.  High bandwidth and good sensitivity.

Humans have two pretty good output interfaces: voice and fingers.

A typical video game system uses vision and fingers (though they also use a lot of sound).  Create electronic games exploring the other 3 possibilities of choosing one from each interface.  (We can't say "video" game if it doesn't use video.)

Probably not to shun an interface entirely, but use it sparingly.  Perhaps it mostly uses sounds and voice, but there is a display and some buttons, which are used sparingly.  So it can't be a game purely on Amazon Alexa.

Karaoke uses mostly sound and voice, especially if you've already memorized the lyrics.  It is kind of the ultimate in exercising the full range of human hearing and voice.  Buttons to select a song.

Co-op multiplayer video games have players using voice and hearing in the natural way to communicate.  This could be a model for a single-player game: the other "player" you are cooperating with is an AI which talks and listens like a human.

I'm surprised game controllers don't have microphones built into them for some voice control.  Speech is useful (among other things) for selecting among a large number of items.  Push a button to speak to avoid the creepiness of an always-on microphone.  Inspired by how much time it takes (how many buttons you need to push) to change armor in Zelda BOTW.

Do we want AI measuring the tone of your voice?

[staxaako] Mass surveillance of mass surveillance

Mass surveillance seems inevitable given its decreasing cost and economies of scale.  Therefore, the best way to regulate it is to monitor who does what with it.  This can be done, ironically or optimistically, with mass surveillance of those with power, those who have access to the mass surveillance big data: watch the watchers.

Is this being done?  It seems it isn't.

There will probably be some constantly evolving and escalating game involving people with power trying to deceitfully deny they had access to, or deny they were influenced by, some questionable use or abuse of mass surveillance.  For example, parallel construction.

[byopuoco] AI manager

Groups of people can change the world through politics, but only if they are organized.  To be organized traditionally requires a manager, someone hired by the group of people to coordinate organization.

Can AI significantly decrease the cost of management?  If so, such technology might profoundly change the world, because it would give poor people more access to management, so it would allow the poor to organize amongst themselves to improve their lot in life.

One of the traditional techniques for those in power to stay in power has been to prevent the opposition from organizing, while they themselves are organized.

Therefore, this technology, AI managers, will be asymmetric in who it affects.  Those with more money were already employing human managers (to stay in power).  This technology will decrease their costs, but it won't increase the amount of organization they already have.  In contrast, the poor didn't have organization in the first place, so access to this technology will affect them much more.

To be effective, people need to trust their manager.  People likely will be more willing to trust a machine as their manager than a human: one can, for example, audit the source code of the management software to verify that it is working in your and your group's best interests.  (If your best interests don't align with your group's best interests, you shouldn't be part of the organization.)  Cryptographic techniques (e.g., homomorphic encryption) can credibly assure that private information you share with the manager stays private and won't be used against you.

Of course, if the poor become more politically effective, then the rich will probably move on to other techniques -- violence -- to stay in power.

[aqnpuilb] Robot baseball batter

Create a robot that can hit baseballs pitched by a skilled pitcher.  Has this already been done?  Some ways to make it even more difficult:

1. Instead of just hitting home runs, hit specific targets.
2. Moving targets.
3. Taller pitcher's mound.
4. Closer pitcher's mound.
5. More textured ball.
6. Thinner bat.
7. Limit bat speed to how fast a human can swing.

[njrecuan] Improving / improvising music in a rhythm game

Create a rhythm game (Guitar Hero, etc.) in which you can not only earn points by playing what's on screen accurately, but also by playing something different that is as good or better musically.  This requires AI to judge.

Might also want a more realistic / complete musical input device.  Maybe microphone and real musical instrument.