Connect 4 Search Trees
These drawings are a representation of the abstract strategy game, Connect Four. More specifically, these drawings represent not only the Connect Four game space, which is as simple as a grid, or the game being played, which would agin be as trivial as that grid in an animate state, but a computational strategy for playing Connect Four. Each drawing corresponds to an artificial intelligence algorithm thinking about one game as it is played. Strategy entails projecting ahead to a series of possible moves and subsequent moves, then searching through that tree for the path to the best possible outcome given that the two players have contradictory motivations. It quickly becomes apparent that investigating all possible moves is inefficient, if not impossible. It's necessary to search with some scrutiny, filtering out moves that are unlikely or wasteful–to prune certain branches of the tree. These algorithms constitute rudimentary artificial intelligence–elegant, perhaps, but neither novel nor new. Alpha-Beta search, the key algorithm, is articulated in many introductory Artificial Intelligence text books. [see, Artificial Intelligence (3rd Edition) by Patrick Winston, for example] The contribution here is instead a matter of drawing–a confrontation of scale and quantity through a reduction of dimension. Because Connect Four provides fuel but not meaningful data, these drawings can be considered works of art rather than visualizations. They exist because of Connect Four and the Alpha-Beta search algorithm, but offer little about Connect Four except as, perhaps, a poetic commentary on the humbling complexities and the nearly incompressible scope of possibilities in an obviously finite and discrete world.
This is a drawing made by a human playing the against the computer. Each line is a move considered, from the perspective of the computer. The two colors correspond to the computer's mindset at the starting level of that line of inquiry, looking for the best state at its turn and the worst state at the human's turn. The human player played a piece in row six (the rightmost row) as the opening play of this game, which is why the tree begins at the right.
These drawings are created with a pen-plotter, which allows for the legible overlay of lines, and the punctuation of the start and end points.
A human-computer game played to a draw.
A human-computer game played to an end-game computer win
Although there are over four trillion possible unique game states, (See John Tromp's Connect Four Playground
, and Edelkamp, Stefan et al, “Symbolic Classiﬁcation of General Two-Player Games”) this algorithm considers between 5,000 and 15,000 of the most relevant of those possible states per game. In this game, around 6,000 board states were considered by the computer and drawn. Board states that were actually played are rendered with more dense lines.
Instead of drawing the board states in neat rows, they can be drawn reciprocally, with future board states (and subsequent states_ nested within the position of each possible current move.