Chasing the output

Chasing the output is a logic game for two players. The goal is to iteratively construct an input that produces the target output for the given program.

Overview

Let's say that players are Alice and Bob. First, they choose a programming language and they pick one of them (for example flip a coin) who is going to write a program.

As an example, let's say that they choose C as a programming language and Alice is going to write a program. Alice can write any program she likes, but there are some constraints:

• The program's output must be deterministic for all inputs on which the program halts (and also whether it halts or not also needs to be deterministic). It means the program cannot depend on the current date/time, OS scheduler, external random number generator, etc. No undefined behavior can appear in the program.
• The program must halt on at least two different inputs and must produce different outputs for those two inputs.

Then, Alice must provide the two different inputs and the program must give different outputs for those two inputs. As an example, Alice writes the following program:

#include <stdio.h>
void main(){
  int n;
  scanf("%d", &n);
  printf("%s", n > 50 ? n > 100 ? "large" : "small" : "X");
}

Suppose that scanf writes 0 to the memory location of n for any irregular situation (to avoid undefined behavior). Also, suppose that int is signed 64-bit integer. This program reads a number and if the number is smaller or equal to 50 then outputs X. Otherwise, if the number is larger than 100 it outputs large, otherwise outputs small.

Alice provides the following two input-output pairs:

1. 51 ---> small
2. 123 ---> large

Now, Bob analyzes the program and decides who is going to play first and who will target which of the two given outputs. Let's say that Bob wants to play first and he picks the small output. So, Bob will make the first move, then Alice will make the second move, Bob will make the third move, and so on.

Move

A move in this game consists of appending a character to the standard input. The input is empty when the game starts and the player who plays the current turn appends a single character to the input. The goal for each player is to construct an input that will produce their target output (large for Alice and small for Bob, as Bob has decided).

After each move, the player must also provide at least one string that, when concatenated to the current input, produces the target output for the current player (if the current player is unable to do that, the other player wins). This string can contain zero or more characters.

If the current input already produces the target output for the given player (before the move), then the current player wins. If the input after the move produces the target output for the current player, then the current player does not win in this move, but instead the other player plays the next move.

For example, Bob makes the first move and he picks input character 7. Then he provides the following string that produces output small when concatenated to the current input: string 1 (because 71 is larger than 50 and not larger than 100).

Alice plays the second move. She picks character 0 and provides the following string: 9 (because 709 is larger than 100 and produces output large). The current input string is 70.

Bob plays the third move. Since 70 already gives his target output small, he wins. The game ends here.

Properties

It is not known whether there is an optimal strategy in this game. The game is designed to be heavily adaptable to different programming languages and easy to understand.

Some games (like Chess, Go, Gomoku, Tic-tac-toe, Dots-and-boxes, etc) have limited board size and theoretically all possible moves can be brute-forced and optimal strategy can be found, especially in the quantum computing era. This game tries to make finding an optimal strategy a hard problem.