[1-21] What does it mean to say a 2-player game is 'solved'?

Is tic-tac-toe solved? How about game z?

We say a game is solved when we know for sure the result when both
players play optimally.  The result is either a guaranteed win for the
first player, a guaranteed win for the second player, or a draw.  We
find this out by searching the mini-max game tree to the game ending
positions.  If you do this for 3x3 tic-tac-toe, it is easy to see that it
is a forced draw. 

other games:
3x3x3 tic-tac-toe: win for the first player.
4x4x4 tic-tac-toe: win for the first player.
Connect-4: win for the first player.
Go-Moku: win for the first player.

[Maintainer's note: Please let us know about your favorite solved
game.]

Top Document: Artificial Intelligence FAQ:1/6 General Questions & Answers [Monthly posting]
Previous Document: [1-20] How can I get the email address for Joe or Jill Researcher?
Next Document: [1-22] What's this Information Theory thing?

Part1 - Part2 - Part3 - Part4 - Part5 - Part6 - Single Page

[ Usenet FAQs | Search | Web FAQs | Documents | RFC Index ]

Send corrections/additions to the FAQ Maintainer:
crabbe@usna.edu, adubey@coli.uni-sb.de

Last Update July 24 2008 @ 00:12 AM