전략

잘 알려진 심리학 실험에서 두 참가자가 다음 게임을 반복한다. 매 만남마다 각 참가자는 상대와 협력(TRADE)할지, 아니면 상대를 배신(CHEAT)할지를 서로 독립적으로 선택한다. 한 번의 만남에 대한 점수는 다음과 같다.

• 두 참가자가 모두 TRADE하면 각자 1점을 얻는다.
• 한 명은 TRADE하고 다른 한 명은 CHEAT하면, TRADE한 사람은 2점을 잃고 CHEAT한 사람은 2점을 얻는다.
• 두 참가자가 모두 CHEAT하면 각자 1점을 잃는다.

많은 사람은 이기는 전략을 찾지 못하거나, 정한 전략을 끝까지 지키지 못한다. 그래서 전략들을 컴퓨터로 시뮬레이션하여 비교하는 편이 더 공정하다. 각 전략은 하나의 자동자(automaton)로 표현되며, 자동자는 전략을 인코딩한 프로그램, 이전 만남들에 대한 기억, 그리고 누적 점수의 세 부분으로 이루어진다. 점수는 0에서 시작하며 매 만남 이후 위 규칙에 따라 갱신된다. 기억은 현재 상대와의 직전 두 번의 만남에서 무슨 일이 있었는지까지 조회할 수 있다.

최대 10개의 전략을 입력받는다. 모든 전략을 서로 다른 모든 전략과(자기 자신과는 겨루지 않는다) 정확히 10번씩 겨루게 하되, 상대 쌍마다 기억을 따로 유지한다. 매 만남에서 두 자동자는 이전 만남들의 기억만으로 각자의 수를 동시에 결정하고, 그 다음 두 자동자의 기억이 함께 갱신된다. 모든 대결이 끝나면 각 전략의 최종 점수를 출력한다.

각 전략은 다음 문법을 따르는 작은 프로그램이다.

<program>   ::= <statement>.
<statement> ::= <command> | <ifstat>
<ifstat>    ::= IF <condition> THEN <statement> ELSE <statement>
<condition> ::= <cond> | <cond> <op> <condition>
<op>        ::= AND | OR
<cond>      ::= <memory> {= | #} {<command> | NULL}
<memory>    ::= {MY | YOUR} LAST {1 | 2}
<command>   ::= TRADE | CHEAT

• LAST1은 두 자동자 사이의 직전 만남을, LAST2는 그 전 만남을 가리킨다.
• MY는 이 자동자 자신의 과거 수를, YOUR는 상대의 과거 수를 가리킨다.
• '='는 "같다", '#'는 "같지 않다"를 뜻한다.
• NULL은 해당 만남이 아직 일어나지 않았음을 뜻한다(예를 들어 첫 만남에서는 LAST1이 NULL이고, 처음 두 만남에서는 LAST2가 NULL이다).
• 조건은 여러 개의 단순 비교를 AND / OR로 이은 것이며, 연산자 우선순위는 없고 오른쪽에서 왼쪽으로 묶인다(a op b op c는 a op (b op c)를 뜻한다).
• 공백과 줄바꿈은 프로그램 어디에나 나타날 수 있으며 가독성을 위한 것일 뿐이다.

예를 들어 다음은 모두 올바른 프로그램이다.

CHEAT.
IF MY LAST1 = CHEAT THEN TRADE ELSE CHEAT.
IFYOURLAST2=NULLTHENTRADEELSEIFYOURLAST1=TRADETHENTRADE
ELSECHEAT.

입력은 여러 개의 프로그램으로 이루어진다. 각 프로그램은 최대 255자이며 편의상 여러 줄에 걸쳐 나뉘어 있을 수 있다. 프로그램은 최대 10개이다. 입력은 '#' 한 글자만 있는 줄로 끝난다.

프로그램마다 한 줄씩, 입력에 주어진 순서대로 출력한다. 각 줄에는 해당 프로그램의 최종 점수를 폭 3의 필드에 오른쪽 정렬하여 출력한다.