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