Join five (also known as morpion solitaire,cross 'n' lines or line game) is a paper and pencil game for one or two players, played on a plus-shaped grid of dots. The origins of the game are probably in northern Europe. References to the game first appeared in French publications in the 1970s. [1] In addition to being played recreationally, the game has been the subject of theoretical studies [2] and computer searches for solutions. [3]
An initial grid of dots are drawn; a square of 4x4 dots, with a rectangle of 4x3 added to each side. The initial cross is outlined in some versions of the game.
During each turn, draw a straight line that is exactly five "dots" long, such that:
In other words, make a five-segment line from four dots, and draw in the fifth (unless it is saved to draw two dots in later turns).
The game ends when no more segments can be drawn on the grid.
In the two player version, the last player to draw a line segment is the winner. In the single player version, scoring is accomplished by counting the number of segments drawn, or by calculating the total area of the grid at the end of play.
In the outlined version, the number of accomplished turns is the score. This is usually kept in check by using tally marks. It is unknown if this can be continued indefinitely, but the game becomes progressively more difficult (up to a point?) once the initial grid has been used completely.
Strategy differs according to whether the game is played alone or against an opponent. In the first case, moves are optimized for the maximum number of possible turns; in the second case, the goal is to be "inefficient" with move selection to restrict the opponent's available moves.
The rules may be varied by requiring lines of 4 marked points in a row rather than 5, with a reduced starting configuration. Also, the "disjoint" variation of the game does not allow two parallel lines to share an endpoint, whereas the standard "touching" version does allow this. [4]
For the "touching" version of the game with lines consisting of 5 marked points, the present record of 178 lines was established on 2011 August 12, using a Monte-Carlo search by algorithmist Christopher Rosin. [5] [6] This is eight moves more than the previous 1976 record of 170 lines. [3] [5] [7] The 1976 record was done by hand, and computer searches had not been able to approach this record [7] despite substantial progress, [8] until August 2010 when Christopher Rosin used a Monte-Carlo search to obtain a result of 172 moves, exceeding the 1976 record, and 178 moves one year later. [6]
For the "disjoint" version of the game with lines consisting of 5 marked points, the record of 82 lines [9] has been obtained by computer search, also found by Christopher Rosin. Previous 80 lines record was found in 2008 by Tristan Cazenave. [10] A 67-step solution was found in 2020 using an AlphaZero-like approach. [11]
Generalized morpion solitaire, in which the starting configuration may be any finite set of marked points, is a member of the NP-hard class of problems for which no efficient computational method for finding an optimal solution is known. Even the problem of finding an approximately optimal solution for generalized morpion solitaire is NP-hard. [2]
For the standard versions of morpion solitaire, infinitely large solutions do not exist; upper bounds have been proven [2] on the maximum number of lines that can be obtained. [12]
Dots and boxes is a pencil-and-paper game for two players. It was first published in the 19th century by French mathematician Édouard Lucas, who called it la pipopipette. It has gone by many other names, including the dots and dashes, game of dots, dot to dot grid, boxes, and pigs in a pen.
Sprouts is an impartial paper-and-pencil game which can be analyzed for its mathematical properties. It was invented by mathematicians John Horton Conway and Michael S. Paterson at Cambridge University in the early 1960s. The setup is even simpler than the popular Dots and Boxes game, but gameplay develops much more artistically and organically.
Klondike, also known as Canfield, is a card game for one player and the best known and most popular version of the patience or solitaire family, as well as one of the most challenging in widespread play. It has spawned numerous variants including Batsford, Easthaven, King Albert, Thumb and Pouch, Somerset or Usk and Whitehead, as well as the American variants of the games, Agnes and Westcliff. The distinguishing feature of all variants is a triangular layout of the tableau, building in ascending sequence and packing in descending order.
Monte Carlo methods, or Monte Carlo experiments, are a broad class of computational algorithms that rely on repeated random sampling to obtain numerical results. The underlying concept is to use randomness to solve problems that might be deterministic in principle. They are often used in physical and mathematical problems and are most useful when it is difficult or impossible to use other approaches. Monte Carlo methods are mainly used in three problem classes: optimization, numerical integration, and generating draws from a probability distribution.
Computer Go is the field of artificial intelligence (AI) dedicated to creating a computer program that plays the traditional board game Go. The field is sharply divided into two eras. Before 2015, the programs of the era were weak. The best efforts of the 1980s and 1990s produced only AIs that could be defeated by beginners, and AIs of the early 2000s were intermediate level at best. Professionals could defeat these programs even given handicaps of 10+ stones in favor of the AI. Many of the algorithms such as alpha-beta minimax that performed well as AIs for checkers and chess fell apart on Go's 19x19 board, as there were too many branching possibilities to consider. Creation of a human professional quality program with the techniques and hardware of the time was out of reach. Some AI researchers speculated that the problem was unsolvable without creation of human-like AI.
In recreational mathematics, a polystick is a polyform with a line segment as the basic shape. A polystick is a connected set of segments in a regular grid. A square polystick is a connected subset of a regular square grid. A triangular polystick is a connected subset of a regular triangular grid. Polysticks are classified according to how many line segments they contain.
Paper soccer is an abstract strategy game played on a square grid representing a soccer or hockey field. Two players take turns extending a line representing the position of a ball until it reaches one of the grid's two-goal spaces. A traditional paper-and-pencil game, it is commonly played in schools and can be found in some magazines. Many computer implementations of the game also exist. Despite the game's simple rules, paper soccer has various expanded strategies and tactics.
Golf is a card game where players try to earn the lowest number of points over the course of nine deals.
Monte Carlo is a pair-matching patience or card solitaire game using a pack of 52 playing cards where the object is to remove pairs from the tableau. Despite its name, it has no relation to the city with the same name nor to any casino-related game. Alternative names for this game include Good Neighbours and Weddings.
Fillomino (フィルオミノ) is a type of logic puzzle published by many publishers. Other published titles for the puzzle include Allied Occupation.
Slitherlink is a logic puzzle developed by publisher Nikoli.
Numberlink is a type of logic puzzle involving finding paths to connect numbers in a grid.
Cribbage Squares, occasionally Cribbage Square, is a patience or card solitaire based on Cribbage which can be played using a deck of playing cards. This game works the same way as Poker Squares, but with cribbage scoring.
The nine dots puzzle is a mathematical puzzle whose task is to connect nine squarely arranged points with a pen by four straight lines without lifting the pen.
Las Vegas Cool Hand, known as Cool Hand in Europe, is a casino game developed by Tarantula Studios and published by Take-Two Interactive for the Game Boy Color. It was released on December 1, 1998 in North America and Europe. The game was ported exclusively in Europe on 1998 for the Game Boy.
Planarity is a 2005 puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University. The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean plane so that no edges intersect. By Fáry's theorem, if a graph is planar, it can be drawn without crossings so that all of its edges are straight line segments. In the planarity game, the player is presented with a circular layout of a planar graph, with all the vertices placed on a single circle and with many crossings. The goal for the player is to eliminate all of the crossings and construct a straight-line embedding of the graph by moving the vertices one by one into better positions.
In mathematics, Lill's method is a visual method of finding the real roots of a univariate polynomial of any degree. It was developed by Austrian engineer Eduard Lill in 1867. A later paper by Lill dealt with the problem of complex roots.
In computer science, Monte Carlo tree search (MCTS) is a heuristic search algorithm for some kinds of decision processes, most notably those employed in software that plays board games. In that context MCTS is used to solve the game tree.
Arthur Eugène Langerman false Swarzberg, known as Arthur Langerman, is a Belgian diamantaire. He is known for having gathered of one of the largest private collections of antisemitic images in the world. The collection constitutes the Arthur Langerman Archive for the Study of Visual Antisemitism (ALAVA) at the Technical University of Berlin in Germany.
