Solved game

From Wikipedia, the free encyclopedia A solved game is a game whose outcome (win, lose, or draw) can be correctly predicted from any position, given that both players play perfectly. Games which have not been solved are said to be “unsolved”. Games for which only some positions have been solved are said to be “partially … Continue reading Solved game

A solved game is a game whose outcome (win, lose, or draw) can be correctly predicted from any position, given that both players play perfectly. Games which have not been solved are said to be “unsolved”. Games for which only some positions have been solved are said to be “partially solved”. This article focuses on two-player games that have been solved.

A two-player game can be “solved” on several levels:[1][2]

Ultra-weak

Prove whether the first player will win, lose, or draw from the initial position, given perfect play on both sides. This can be a non-constructive proof (possibly involving astrategy-stealing argument) that need not actually determine any moves of the perfect play.

Weak

Provide an algorithm that secures a win for one player, or a draw for either, against any possible moves by the opponent, from the beginning of the game. That is, produce at least one complete ideal game (all moves start to end) with proof that each move is optimal for the player making it. It does not necessarily mean a computer program using the solution will play optimally against an imperfect opponent. For example, the checkers program Chinook will never turn a drawn position into a losing position (since the weak solution of checkers proves that it is a draw), but it might possibly turn a winning position into a drawn position because Chinook does not expect the opponent to play a move that will not win but could possibly lose, and so it does not analyze such moves completely.

Strong

Provide an algorithm that can produce perfect play (moves) from any position, even if mistakes have already been made on one or both sides.

Despite the name, many game theorists believe that “ultra-weak” are the deepest, most interesting and valuable proofs. “Ultra-weak” proofs require a scholar to reason about the abstract properties of the game, and show how these properties lead to certain outcomes if perfect play is realized.[citation needed]

By contrast, “strong” proofs often proceed by brute force — using a computer to exhaustively search a game tree to figure out what would happen if perfect play were realized. The resulting proof gives an optimal strategy for every possible position on the board. However, these proofs aren’t as helpful in understanding deeper reasons why some games are solvable as a draw, and other, seemingly very similar games are solvable as a win.

Given the rules of any two-person game with a finite number of positions, one can always trivially construct a minimax algorithm that would exhaustively traverse the game tree. However, since for many non-trivial games such an algorithm would require an infeasible amount of time to generate a move in a given position, a game is not considered to be solved weakly or strongly unless the algorithm can be run by existing hardware in a reasonable time. Many algorithms rely on a huge pre-generated database, and are effectively nothing more.

As an example of a strong solution, the game of tic-tac-toe is solvable as a draw for both players with perfect play (a result even manually determinable by schoolchildren). Games like nim also admit a rigorous analysis using combinatorial game theory.

Whether a game is solved is not necessarily the same as whether it remains interesting for humans to play. Even a strongly solved game can still be interesting if its solution is too complex to be memorized; conversely, a weakly solved game may lose its attraction if the winning strategy is simple enough to remember (e.g. Maharajah and the Sepoys). An ultra-weak solution (e.g. Chomp or Hex on a sufficiently large board) generally does not affect playability.

In non-perfect information games, one also has the notion of essentially weakly solved[3]. A game is said to be essentially weakly solved if a human lifetime of play is not sufficient to establish with statistical significance that the strategy is not an exact solution. As an example, the poker variation heads-up limit Texas hold ‘em have been essentially weakly solved by the poker bot Cepheus[3][4][5].

Perfect play

In game theory, perfect play is the behavior or strategy of a player that leads to the best possible outcome for that player regardless of the response by the opponent. Based on the rules of a game, every possible final position can be evaluated (as a win, loss or draw). By backward reasoning, one can recursively evaluate a non-final position as identical to that of the position that is one move away and best valued for the player whose move it is. Thus a transition between positions can never result in a better evaluation for the moving player, and a perfect move in a position would be a transition between positions that are equally evaluated. As an example, a perfect player in a drawn position would always get a draw or win, never a loss. If there are multiple options with the same outcome, perfect play is sometimes considered the fastest method leading to a good result, or the slowest method leading to a bad result.

Perfect play can be generalized to non-perfect information games, as the strategy that would guarantee the highest minimal expected outcome regardless of the strategy of the opponent. As an example, the perfect strategy for Rock, Paper, Scissors would be to randomly choose each of the options with equal (1/3) probability. The disadvantage in this example is that this strategy will never exploit non-optimal strategies of the opponent, so the expected outcome of this strategy versus any strategy will always be equal to the minimal expected outcome.

Although the optimal strategy of a game may not (yet) be known, a game-playing computer might still benefit from solutions of the game from certain endgame positions (in the form of endgame tablebases), which will allow it to play perfectly after some point in the game. Computer chess programs are well known for doing this.

Solved games

Awari (a game of the Mancala family)
The variant of Oware allowing game ending “grand slams” was strongly solved by Henri Bal and John Romein at the Vrije Universiteit in Amsterdam, Netherlands (2002). Either player can force the game into a draw.
Checkers
See “Draughts, English”
Chopsticks
The second player can always force a win.[6]
Connect Four
Solved first by James D. Allen (Oct 1, 1988), and independently by Victor Allis (Oct 16, 1988).[7] First player can force a win. Strongly solved by John Tromp’s 8-ply database[8](Feb 4, 1995). Weakly solved for all boardsizes where width+height is at most 15[7] (Feb 18, 2006).
Draughts, English (Checkers)
This 8×8 variant of draughts was weakly solved on April 29, 2007 by the team of Jonathan Schaeffer, known for Chinook, the “World Man-Machine Checkers Champion“. From the standard starting position, both players can guarantee a draw with perfect play.[9] Checkers is the largest game that has been solved to date, with a search space of 5×1020.[10] The number of calculations involved was 1014, which were done over a period of 18 years. The process involved from 200 desktop computers at its peak down to around 50.[11]

The game of checkers has roughly 500 billion billion possible positions (5 × 1020). The task of solving the game, determining the final result in a game with no mistakes made by either player, is daunting. Since 1989, almost continuously, dozens of computers have been working on solving checkers, applying state-of-the-art artificial intelligence techniques to the proving process. This paper announces that checkers is now solved: Perfect play by both sides leads to a draw. This is the most challenging popular game to be solved to date, roughly one million times as complex as Connect Four. Artificial intelligence technology has been used to generate strong heuristic-based game-playing programs, such as Deep Blue for chess. Solving a game takes this to the next level by replacing the heuristics with perfection.

Turing test

Eugene Goostman is an artificial intelligence chatterbot. First developed by a group of three programmers; the Russian-born Vladimir Veselov, Ukranian-born Eugene Demchenko, and Russian-born Sergey Ulasen in Saint Petersburg in 2001,[1][2] Goostman is portrayed as a 13-year old Ukranian boy in an effort to make his personality and … Continue reading

Eugene Goostman is an artificial intelligence chatterbot. First developed by a group of three programmers; the Russian-born Vladimir Veselov, Ukranian-born Eugene Demchenko, and Russian-born Sergey Ulasen in Saint Petersburg in 2001,[1][2] Goostman is portrayed as a 13-year old Ukranian boy in an effort to make his personality and knowledge level believable to users.

Goostman has competed in a number of Turing test contests since its creation, with several second-place finishes in the Loebner Prize. In June 2012, at a competition marking what would have been the 100th birthday of its namesake, Goostman won what was promoted as the largest-ever Turing test contest, successfully convincing 29% of its judges that it was human. On 7 June 2014, at a contest marking the 60th anniversary of Turing’s death, Goostman became, according to Kevin Warwick, the first ever computer to pass the Turing test, by convincing 33% of judges that it was human.

Personality

Eugene Goostman is portrayed as being a 13 year-old boy from OdessaUkraine, with a father who works as a gynaecologist, and a pet guinea pig. Veselov stated that Goostman was designed to be a “character with a believable personality”; the choice of age was intentional, as one who is thirteen is, in Veselov’s opinion, “not too old to know everything and not too young to know nothing”. His young age also provides forgiveness for minor grammatical errors in his responses.[1][3] In 2014, work was made on improving the bot’s “dialog controller”, allowing Goostman to output more human-like dialogue.[2]

Accolades

Eugune Goostman competed in a number of Turing test competitions; it finished as the runner-up in the 2001, 2005, and 2008 Loebner Prize competitions. On 23 June 2012, Goostman won a Turing test competition at Bletchley Park in Milton Keynes, held to mark the centenary of Alan Turing. The competition, which featured five bots, twenty-five hidden humans, and thirty judges, was considered to be the largest-ever Turing test contest by its organizers. After a series of five minute-long text conversations, 29% of the judges were convinced that the bot was an actual human—only one percent away from the 30% goal suggested by Turing in his paper Computing Machinery and Intelligence.[3]

Turing test pass

On 7 June 2014, in a Turing test competition at the Royal Society, organized by Kevin Warwick of the University of Reading to mark the 60th anniversary of Turing’s death, Goostman was named the first ever computer to pass a Turing test. 33% of the judges (which included John Sharkey, a sponsor of the bill granting a posthumous pardon to Turing, and Red Dwarf actor Robert Llewellyn) were convinced that Eugene Goostman was a human.[4][2]

In response to the achievement, Warwick stated that “some will claim that the Test has already been passed. The words Turing Test have been applied to similar competitions around the world. However this event involved the most simultaneous comparison tests than ever before, was independently verified and, crucially, the conversations were unrestricted. A true Turing Test does not set the questions or topics prior to the conversations. We are therefore proud to declare that Alan Turing’s Test was passed for the first time on Saturday.”[2]

Herbert Alexander Simon

Herbert Alexander Simon (June 15, 1916 – February 9, 2001) was an American political scientist, economist, sociologist, psychologist, and professor—most notably at Carnegie Mellon University—whose research ranged across the fields of cognitive psychology, cognitive science, computer science, public administration, economics, management, philosophy of science, sociology, and political science. With almost a thousand very highly-cited publications, he was one of the most influential social […]

Herbert Alexander Simon (June 15, 1916 – February 9, 2001) was an American political scientist, economist, sociologist, psychologist, and professor—most notably at Carnegie Mellon University—whose research ranged across the fields of cognitive psychologycognitive science, computer science, public administration, economics, management, philosophy of science, sociology, and political science. With almost a thousand very highly-cited publications, he was one of the most influential social scientists of the twentieth century.[4]

Simon was among the founding fathers of several of today’s important scientific domains, including artificial intelligenceinformation processingdecision-makingproblem-solvingattention economicsorganization theorycomplex systems, and computer simulation of scientific discovery.

He coined the terms bounded rationality and satisficing, and was the first to analyze the architecture of complexity and to propose apreferential attachment mechanism to explain power law distributions.[5]

He also received many top-level honors later in life. These include: becoming a fellow of the American Academy of Arts and Sciencesin 1959;[6] election to the National Academy of Sciences in 1967;[7] the ACM‘s Turing Award for making “basic contributions to artificial intelligence, the psychology of human cognition, and list processing” (1975); the Nobel Memorial Prize in Economics “for his pioneering research into the decision-making process within economic organizations” (1978); the National Medal of Science (1986); and the APA‘s Award for Outstanding Lifetime Contributions to Psychology (1993).

As a testament to his interdisciplinary approach, Simon was affiliated with such varied Carnegie Mellon departments as the School of Computer ScienceTepper School of Business, departments of Philosophy, Social and Decision Sciences, and Psychology. Simon received an honorary Doctor of Political science degree from University of Pavia in 1988 and an honorary Doctor of Laws (LL.D.) degree from Harvard University in 1990.

Creatures Of Self Destruction?

Published on Oct 4, 2013 http://www.singularityweblog.com/noam… Dr. Noam Chomsky is a famed linguist, political activist, prolific author and recognized public speaker, who has spent the last 60 years living a double life — one as a political activist and another as a linguist. His activism allegedly made him the US government’s public enemy number one. […]

Published on Oct 4, 2013

http://www.singularityweblog.com/noam…

Dr. Noam Chomsky is a famed linguist, political activist, prolific author and recognized public speaker, who has spent the last 60 years living a double life — one as a political activist and another as a linguist. His activism allegedly made him the US government’s public enemy number one. As a linguist he is often credited for dethroning behaviorism and becoming the “father of modern linguistics” (and/or cognitive science). Put together his accomplishments are the reasons why he is often listed as one of the most important intellectuals of the 20th century.

During our 28 minute conversation with Noam Chomsky we cover a variety of interesting topics such as: the balance between his academic and his political life; artificial intelligence and reverse engineering the human brain; why in his view both Deep Blue and Watson are little more than PR; the slow but substantial progress of our civilization; the technological singularity…