source: orange/orange/doc/datasets/tic-tac-toe.htm @ 1760:9d4bb141fb0e

Revision 1760:9d4bb141fb0e, 3.3 KB checked in by blaz <blaz.zupan@…>, 9 years ago (diff)

data info file

Line 
1<html>
2<head>
3<title>Tic-Tac-Toe Endgame Data Base</title>
4</head>
5<body>
6<h1>Info on Tic-Tac-Toe Endgame Data Base</h1>
7<pre>
81. Title: Tic-Tac-Toe Endgame database
9
102. Source Information
11   -- Creator: David W. Aha (aha@cs.jhu.edu)
12   -- Donor: David W. Aha (aha@cs.jhu.edu)
13   -- Date: 19 August 1991
14 
153. Known Past Usage:
16   1. Matheus,~C.~J., \& Rendell,~L.~A. (1989).  Constructive
17      induction on decision trees.  In {\it Proceedings of the
18      Eleventh International Joint Conference on Artificial Intelligence}
19      (pp. 645--650).  Detroit, MI: Morgan Kaufmann.
20      -- CITRE was applied to 100-instance training and 200-instance test
21         sets.  In a study using various amounts of domain-specific
22         knowledge, its highest average accuracy was 76.7% (using the
23         final decision tree created for testing).
24
25   2. Matheus,~C.~J. (1990). Adding domain knowledge to SBL through
26      feature construction.  In {\it Proceedings of the Eighth National
27      Conference on Artificial Intelligence} (pp. 803--808).
28      Boston, MA: AAAI Press.
29      -- Similar experiments with CITRE, includes learning curves up
30         to 500-instance training sets but used _all_ instances in the
31         database for testing.  Accuracies reached above 90%, but specific
32         values are not given (see Chris's dissertation for more details).
33
34   3. Aha,~D.~W. (1991). Incremental constructive induction: An instance-based
35      approach.  In {\it Proceedings of the Eighth International Workshop
36      on Machine Learning} (pp. 117--121).  Evanston, ILL: Morgan Kaufmann.
37      -- Used 70% for training, 30% of the instances for testing, evaluated
38         over 10 trials.  Results reported for six algorithms:
39         -- NewID:   84.0%
40         -- CN2:     98.1% 
41         -- MBRtalk: 88.4%
42         -- IB1:     98.1%
43         -- IB3:     82.0%
44         -- IB3-CI:  99.1%
45      -- Results also reported when adding an additional 10 irrelevant
46         ternary-valued attributes; similar _relative_ results except that
47         IB1's performance degraded more quickly than the others.
48
494. Relevant Information:
50
51   This database encodes the complete set of possible board configurations
52   at the end of tic-tac-toe games, where "x" is assumed to have played
53   first.  The target concept is "win for x" (i.e., true when "x" has one
54   of 8 possible ways to create a "three-in-a-row"). 
55
56   Interestingly, this raw database gives a stripped-down decision tree
57   algorithm (e.g., ID3) fits.  However, the rule-based CN2 algorithm, the
58   simple IB1 instance-based learning algorithm, and the CITRE
59   feature-constructing decision tree algorithm perform well on it.
60
615. Number of Instances: 958 (legal tic-tac-toe endgame boards)
62
636. Number of Attributes: 9, each corresponding to one tic-tac-toe square
64
657. Attribute Information: (x=player x has taken, o=player o has taken, b=blank)
66
67    1. top-left-square: {x,o,b}
68    2. top-middle-square: {x,o,b}
69    3. top-right-square: {x,o,b}
70    4. middle-left-square: {x,o,b}
71    5. middle-middle-square: {x,o,b}
72    6. middle-right-square: {x,o,b}
73    7. bottom-left-square: {x,o,b}
74    8. bottom-middle-square: {x,o,b}
75    9. bottom-right-square: {x,o,b}
76   10. Class: {positive,negative}
77
788. Missing Attribute Values: None
79
809. Class Distribution: About 65.3% are positive (i.e., wins for "x")
Note: See TracBrowser for help on using the repository browser.