Strategy-stealing argument

In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game (one in which either player has the same set of available moves with the same results, so that the first player can "use" the second player's strategy) in which an extra move can never be a disadvantage.

The argument works by obtaining a contradiction. A winning strategy is assumed to exist for the second player, who is using it. But then, roughly speaking, after making an arbitrary first move – which by the conditions above is not a disadvantage – the first player may then also play according to this winning strategy. The result is that both players are guaranteed to win – which is absurd, thus contradicting the assumption that such a strategy exists.

Strategy-stealing was invented by John Nash in the 1940s to show that the game of hex is always a first-player win, as ties are not possible in this game.^[1] However, Nash did not publish this method, and Beck (2008) credits its first publication to Alfred W. Hales and Robert I. Jewett, in the 1963 paper on tic-tac-toe in which they also proved the Hales–Jewett theorem.^[2] Other examples of games to which the argument applies include the m,n,k-games such as gomoku. In the game of Sylver coinage, strategy stealing has been used to show that the first player wins, rather than that the game ends in a tie.^[3]

Example

A strategy-stealing argument can be used on the example of the game of tic-tac-toe, for a board and winning rows of any size.^[1][2] Suppose that the second player (P2) is using a strategy S which guarantees a win. The first player (P1) places an X in an arbitrary position. P2 responds by placing an O according to S. But if P1 ignores the first random X, P1 is now in the same situation as P2 on P2's first move: a single enemy piece on the board. P1 may therefore make a move according to S – that is, unless S calls for another X to be placed where the ignored X is already placed. But in this case, P1 may simply place an X in some other random position on the board, the net effect of which will be that one X is in the position demanded by S, while another is in a random position, and becomes the new ignored piece, leaving the situation as before. Continuing in this way, S is, by hypothesis, guaranteed to produce a winning position (with an additional ignored X of no consequence). But then P2 has lost – contradicting the supposition that P2 had a guaranteed winning strategy. Such a winning strategy for P2, therefore, does not exist, and tic-tac-toe is either a forced win for P1 or a tie. (Further analysis shows it is in fact a tie.)

어떤 강력한 포지셔닝 게임에도 같은 증거가 있다.

체스

주광이라는 체스 직종이 있는데, 주광은 이 직책이 허용되면 "통과"를 선호한다. 이 때문에 전략-스틸링 주장은 체스에 적용할 수 없다.^[4] 화이트와 블랙이 최적의 플레이로 승리를 강요할 수 있는지, 두 선수 모두 무승부를 강요할 수 있는지는 현재 알려지지 않았다. 그러나 사실상 모든 체스 학생들은 화이트의 첫 번째 움직임을 장점으로 여기고 있으며, 현대 고급 게임의 통계는 화이트의 승률이 블랙의 승률보다 약 10% 더 높다.

가다

In Go 패스 허용. 선발 포지션이 대칭(빈 보드, 어느 선수도 승점이 없을 때)일 때 첫 번째 선수가 첫 번째 동작을 포기하는 것만으로도 두 번째 선수의 승리 전략을 훔칠 수 있다는 뜻이다. 그러나 1930년대 이후 두 번째 선수에게는 전형적으로 일부 보상 포인트가 주어지기 때문에 출발 포지션이 비대칭적이게 되고, 전략 스틸링 논쟁은 더 이상 통하지 않을 것이다.^[5]

게임에서 기본적인 전략은 "미러 고"인데, 두 번째 플레이어는 이 상대와 대각선으로 반대되는 동작을 한다. 이 접근방식은 사다리 전술, ko 싸움 또는 이사회의 중심 지점의 제어를 위한 성공적인 경쟁을 통해 패배할 수 있다.

구성성

전략적인 논쟁은 두 번째 선수를 위한 어떤 가상적인 승리 전략에서 모순을 도출하는 수단으로 두 번째 선수가 이길 수 없다는 것을 보여준다. 이 주장은 일반적으로 무승부가 있을 수 없는 게임에서 배제된 중간부의 법칙에 의해 채택된다. 그러나 첫 번째 선수에게는 명시적인 전략을 제공하지 않으며, 이로 인해 비건설적이라고 불려왔다.^[4] 이에 따라 실제로 어떻게 승부 전략을 계산할지 의문이 제기된다.

촘프처럼 도달 가능한 포지션 수가 한정된 게임의 경우 철저한 검색을 통해 승리 전략을 찾을 수 있다.^[6] 그러나 직급이 많으면 비실용적일 수 있다.

2019년 그레그 보드윈과 오퍼 그로스먼은 전략-스테이닝 논쟁이 사용된 두 종류의 게임에서 승리 전략을 찾는 문제가 PSPACE-hard임을 증명했다: 최소 포셋 게임과 대칭 메이커 게임.^[7]

참조