Search the FAQ Archives

3 - A - B - C - D - E - F - G - H - I - J - K - L - M
N - O - P - Q - R - S - T - U - V - W - X - Y - Z
faqs.org - Internet FAQ Archives

REPOST: Artificial Intelligence FAQ: General Questions & Answers 1/6 [Monthly posting]
Section - [1-16] What does it mean to say a 2-player game is 'solved'?

( Part1 - Part2 - Part3 - Part4 - Part5 - Part6 - Part7 - Single Page )
[ Usenet FAQs | Web FAQs | Documents | RFC Index | Business Photos and Profiles ]


Top Document: REPOST: Artificial Intelligence FAQ: General Questions & Answers 1/6 [Monthly posting]
Previous Document: [1-15] How can I get the email address for Joe or Jill Researcher?
Next Document: [1-17] What are the rules for the game of "Life"?
See reader questions & answers on this topic! - Help others by sharing your knowledge
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.] 

User Contributions:

Comment about this article, ask questions, or add new information about this topic:

CAPTCHA