First-player and second-player win: Difference between revisions

Revision as of 05:42, 24 March 2009

Latest revision as of 16:16, 2 November 2023

(32 intermediate revisions by 15 users not shown)

Line 1:

[[Image:Tictactoe-X.svg|thumb|right|Diagram showing optimal strategy for [[tic-tac-toe]]. With perfect play, and from any initial move, both players can always force a draw.]]

{{Unreferenced|date=March 2009}}

In [[combinatorial game theory]], a two-player deterministic [[perfect information]] [[Sequential game|turn-based game]] is a '''first-player-win''' if with [[Solved game#Perfect play|perfect play]] the first player to move can always force a win. Similarly, a game is '''second-player-win''' if with perfect play the second player to move can always force a win. With perfect play, if neither side can force a win, the game is a [[Draw (tie)|draw]].

Some games with relatively small [[game tree]]s have been proven to be first or second-player wins. For example, the game of [[Nimnim]] with the classic 3–4–5 starting position is an example of a first-player-win game. ItHowever, remainsNim awith matterthe of1-3-5-7 conjecturestarting asposition tois whether other games such as [[chess]]a are firstsecond-player-wins;win. seeThe theclassic articlegame of [[first-moveConnect advantage in chessFour]] forhas morebeen onmathematically thisproven to be first-player-win.

In [[game theory]], a two-player [[turn-based game]] is a '''first-player-win''' if a [[optimal play|perfect player]] can always force a win.

With perfect play, [[English draughts|checkers]] has been determined to be a draw; neither player can force a win.<ref>{{cite journal|title=Checkers Is Solved |doi=10.1126/science.1144079 |pmid=17641166 |volume=317 |issue=5844 |journal=Science |pages=1518–1522|year=2007 |last1=Schaeffer |first1=J. |last2=Burch |first2=N. |last3=Bjornsson |first3=Y. |last4=Kishimoto |first4=A. |last5=Muller |first5=M. |last6=Lake |first6=R. |last7=Lu |first7=P. |last8=Sutphen |first8=S. |bibcode=2007Sci...317.1518S |s2cid=10274228 |doi-access=free }}</ref> Another example of a game which leads to a draw with perfect play is [[tic-tac-toe]], and this includes play from any opening move.

Some games with relatively small [[game tree]]s have been proven to be first player wins. For example, the game of [[Nim]] with the classic 3–4–5 starting position is an example of a first-player-win game. It remains a matter of conjecture as to whether other games such as [[chess]] are first-player-wins; see the article [[first-move advantage in chess]] for more on this.

Significant theory has been completed in the effort to [[Solving chess|solve chess]]. It has been speculated that there may be [[First-move advantage in chess|first-move advantage]] which can be detected when the game is played imperfectly (such as with all humans and all current [[chess engine]]s). However, with perfect play, it remains unsolved as to whether the game is a first-player win (White), a second player win (Black), or a forced draw.<ref>J.W.H.M. Uiterwijk, H.J. van den Herik. [https://web.archive.org/web/20180109064212/https://pdfs.semanticscholar.org/55dd/2fee1f0981fbfabd4b158a6584eefaacbcea.pdf "The Advantage of the Initiative]". (August 1999).</ref><ref>{{cite journal

== See also ==

|author-link=Claude Shannon

* [[Strategy-stealing argument]]

|last=Shannon

* [[Second player win]]

|first=C.

* [[Forced draw]]

|series=7

* [[Zugzwang]]

|volume=41

* [[Determinacy]]

|number=314

* [[Combinatorial game theory]]

|date=March 1950

|title=Programming a Computer for Playing Chess

|url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf

|journal=[[Philosophical Magazine]]

|access-date=2008-06-27

|archive-url=https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf

|archive-date=2010-07-06

|url-status=dead

}}</ref><ref>{{cite web

|author=Victor Allis

|url=http://www.dphu.org/uploads/attachements/books/books_3721_0.pdf

|title=PhD thesis: Searching for Solutions in Games and Artificial Intelligence

|work=Department of Computer Science

|publisher=[[University of Limburg]]

|year=1994

|access-date=2012-07-14

|author-link=Victor Allis

|archive-date=2020-11-22

|archive-url=https://web.archive.org/web/20201122211341/https://www.dphu.org/uploads/attachements/books/books_3721_0.pdf

|url-status=dead

}}</ref>

[[Category:Game theory]]

== See also ==

*[[Solved game]]

* [[Strategy-stealing argument]]

* [[Zugzwang]]

* [[Determinacy]]

* [[Combinatorial game theory]]

*[[First-move advantage in chess]]

==References==

{{Reflist}}

[[Category:Non-cooperative games]]

[[Category:Mathematical games]]

[[Category:{{Game theory]]}}

{{Mathapplied-stub}}