다음 조건을 만족하는 게임에 대해 논의할 것이다. 이는 backward induction을 위한 조건으로 볼 수 있다. Combinatorial game 1. 두 명의 플레이어가 번갈아가면서 게임을 진행한다. 2. 플레이어는 게임의 상태를 모두 알 수 있다. 3. 행동에 따른 게임 상태의 변화가 운에 의해 결정되지 않고 확정적이다. 4. 게임은 반드시 종료된다. (무한히 진행되지 않는다.) 5. 게임의 승패가 반드시 결정된다. (무승부가 존재하지 않는다.) Impartial game 취할 수 있는 행동은 오직 게임 상태에 의해 결정된다. 플레이어에 따라 취할 수 있는 행동이 달라지지 않는다. ex) Nim, 31 게임 cf. 체스 Normal game: 마지막에 움직이는 플레이어가 승리한다. Misére..