#
The Evergreen(r,s) Game

The game is named after our
Evergreen Project.
It is not to be confused with the famous chess game
of Anderssen against Dufresne in 1852.
r and s are at least 2. The game is already interesting with r=s=2.

The purpose of the game is to introduce concepts and algorithms that are useful
for writing better MAX-CSP solvers. Surprisingly, brute-force-search is not one of them.

Anna and Bob, the players,
agree on a protocol P1 to choose a set G of s Boolean relations
(of at most rank r). For example, they choose two relations of rank r randomly,
except the all true and all false relations.
A CSP(G)-program (a constraint program)
is a non-empty bag of constraints only involving the
relations in G (allowing constraints to be duplicated).
Anna chooses a CSP(G)-program H with at most v_max=1000 variables.
Bob solves H and gets paid by Anna the fraction times a million dollars that
Bob satisfies in H.
Anna will choose a program that will minimize Bob's profit.
Take turns. Bob will choose a program and Anna solves it.
The alternation of the game is: Anna: program, Bob: solves, Bob: program,
Anna: solves, for one round of the game.
Then a new set of relations is chosen and Bob generates an instance, etc.

The variables used in a constraint must all be distinct, i.e., R(x,x,y) is not allowed.

Each player has a fixed amount of time for each move, say 2 minutes.
If the player fails to move in that time, the cost is $ 1 million and the
game starts with a new set of relations.

As an example, the protocol P1 chooses the following set
G={R1, R2} of relations (we could choose any pair of relations):
R1(a) = !a and R2(a,b) = or(a,b).
This is an Evergreen(2,2) game.

For G={R1,R2}, a program is:

!A
!B
!C
A or B
B or C
B or C

and the maximum assignment is M={!A B !C} which satisfies all
but one constraint, i.e., the satisfaction is 5/6.
What H should Anna choose for the G above?
Should she use the full set CSP(G)-programs or should she limit
herself to a subset?

##
Other Game properties

Iterated game of base zero-sum game.
Perfect information game.
If Anna acts irrationally, we can transform her program into an
S-CSP(G)-program in which fewer constraints can be satisfied
by the best assignment.

Bob can always find efficiently
an assignment J for the program H that Anna gives him
so that J is as good as if Anna would have used her best answer.

In the game Evergreen(2,2) using the relations
R1(a) = !a and R2(a,b) = or(a,b), the Fibonacci numbers play a role.

##
Surprise

It is surprising that the two strategies, when Anna and Bob both play optimally,
are in P. The game looks at first to be in Sigma-2.
Karl J. Lieberherr,
CCIS, Nostheastern University, March 2007