Editing Connect Four (section)

==Mathematical solution==
Connect Four is a two-player game with [[perfect information]] for both sides, meaning that nothing is hidden from anyone. Connect Four also belongs to the classification of an adversarial, [[zero-sum game]], since a player's advantage is an opponent's disadvantage.

One measure of complexity of the Connect Four game is the number of possible games board positions. For classic Connect Four played on a 7-column-wide, 6-row-high grid, there are 4,531,985,219,092 (about 4.5 trillion) positions<ref name="oeis">{{Cite web|title= Number of legal 7 X 6 Connect-Four positions after n plies''
|id=sequence A212693 |url=https://oeis.org/A212693|access-date=2023-02-12|website=Online Encyclopedia of Integer Sequences | date=2012
|editor= Neil Sloane | editor-link= Neil Sloane}}</ref> for all game boards populated with 0 to 42 pieces.

[[file:Connect Four.gif|thumb|Gameplay of Connect Four]]
The game was first [[Solved game|solved]] by James Dow Allen (October 1, 1988), and independently by [[Victor Allis]] (October 16, 1988).<ref name="Tromp">{{cite web |url=https://tromp.github.io/c4/c4.html |title=John's Connect Four Playground |publisher=Homepages |date=May 25, 2010}}</ref> Allis describes a knowledge-based approach,<ref name="Allis">Allis, Victor, [http://www.informatik.uni-trier.de/~fernau/DSL0607/Masterthesis-Viergewinnt.pdf ''A Knowledge-based Approach of Connect-Four''], Vrije Universiteit, October 1988</ref> with nine strategies, as a solution for Connect Four. Allen also describes winning strategies<ref name="Allen">
Allen, James D., [https://tromp.github.io/c4.html ''Expert Play in Connect-Four''], 1990</ref><ref name=allenBook>{{cite book|last=Allen|first=James D.|title=The Complete Book of Connect 4: History, Strategy, Puzzles|year=2010|publisher=Sterling Publishing Company|isbn=978-1402756214|url-access=registration|url=https://archive.org/details/isbn_9781402756214}}</ref> in his analysis of the game. At the time of the initial solutions for Connect Four, [[Brute-force search|brute-force analysis]] was not deemed feasible given the game's complexity and the computer technology available at the time.

Connect Four has since been solved with brute-force methods, beginning with [[John Tromp]]'s work in compiling an 8-ply database.<ref name="Tromp" /><ref>Tromp, John, [https://archive.ics.uci.edu/ml/datasets/Connect-4 ''Connect-4 Data Set''], February 4, 1995</ref> The artificial intelligence algorithms able to strongly solve Connect Four are [[minimax]] or [[negamax]], with optimizations that include [[alpha-beta pruning]], move ordering, and [[transposition table]]s. The code for solving Connect Four with these methods is also the basis for the [[Fhourstones]]<ref name="Fhourstones">Tromp, John, [https://tromp.github.io/c4/fhour.html ''The Fhourstones Benchmark''], 1992</ref> integer performance benchmark.

The solved conclusion for Connect Four is [[first-player-win]]. With [[perfect play]], the first player can force a win,<ref name="Tromp" /><ref name="Allis" /><ref name="Allen" /> on or before the 41st move<ref name="c4solve">{{cite book |author1=asun.net |title=Four in a Row Solver [computer software] |date=2013 |publisher=Microsoft Corporation}}</ref> by starting in the middle column. The game is a theoretical draw when the first player starts in the columns adjacent to the center. For the edges of the game board, column 1 and 2 on left (or column 7 and 6 on right), the exact move-value score for first player start is loss on the 40th move,<ref name="c4solve" /> and loss on the 42nd move,<ref name="c4solve" /> respectively. In other words, by starting with the four outer columns, the first player allows the second player to force a win.<ref>{{cite web | last=Cahn | first=Lauren | title=How to Win Connect 4 Every Time, According to the Computer Scientist Who Solved It | website=Reader&#039;s Digest | date=2023-11-01 | url=https://www.rd.com/article/how-to-win-connect-4/ | access-date=2025-05-24}}</ref>