UVa 보드에서 퍼온글..

This is the basic brute-force method which works on basically all game theory problems where you can enumerate all states of the game:
 
1. Start by finding all final states and mark them as a win or a loss and put these states in a queue (in 10404, that would be marking 0 as a loss)
2. Pop the front element in the queue one by one, and generate all states preceeding this state (in 10404, that would be all m position when adding the poped position with all m different moves). Depending on who is to move and whether the popped state was a win or loss, do either of the following for each of the preceeding states x:
a) If the popped state is losing for the player to move in that state, then mark x as a win and add to queue.
b) If the popped state is winning for the player to move, then this move is bad from state x. Decrease the number of possible moves from state x. If this reaches 0, it means there are no moves from state x which will avoid a loss, thus mark state x as loss and add to queue
3. Proceed this until queue is empty. Now each state is marked as a win or a loss or not marked at all; in the latter case it means it's a draw (in 10404, this would be possible if n=5 and the only moves are >5, but i guess that's an illegal input).
 
In many problems you can simply this approach considerably, and 10404 is such a problem. It generally works if each move brings the game closer to the end (a game where the same state can never be repeated).You can then just loop from the final state up to the start state in the order the states can be visited (sort of like a topological sort, the graph consists of nodes representing each state and arrows indicate moves going from one state to another - if the game is non-repeatable, this graph will be acyclic and thus a topological sort exist) and apply the algorithm above directly.



간단히 정리를 하면.. (내 나름대로 이해한 것이므로 오류가 있을수 있음.. -_-)

나올수 있는 모든 상태에 대해서 win 또는 lose로 마크를 한다..
goal에서부터 거꾸로 마크해나가는데 그 전략은..

1) 지는 상태 바로 전 상태는 이기는 상태..
2) 현재 상태에서 한번에 지는 상태로 갈 수 없으면 지는 상태이다..


관련문제:
UVa 10404 - Bachet's Game 
LA 2321 - Calendar Game

기타 참고자료:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames 

'Problem Solving > Algorithm notes' 카테고리의 다른 글

Josephus Problem  (2) 2009.01.01
Number of Swap Operations  (0) 2008.07.24
소수 구하는 방법 (Sieve of Eratosthenes)  (2) 2008.07.15
Horner's Rule  (0) 2008.05.04
GCD SUM  (0) 2008.03.18
Erdos & Gallai  (0) 2008.03.04
Game Theory  (0) 2007.12.19
Misère Nim  (2) 2007.12.16
BSP Tree  (0) 2007.08.28
Catalan Number  (10) 2007.08.12
Multinomial Theorem  (0) 2007.08.04

Leave a Comment


to Top