# CNN training data size for determing the winner of tic-tac-toe

I'm trying to learn machine learning with tensorflow and wrote a program that uses CNNs to determine game results for a given tic-tac-toe board. Its inputs and outputs are -

Input - An array of 9 elements that represents the board (0=empty, 1='X', 2='O')

Output - An array of 3 elements ([1,0,0]=draw, [0,1,0]=player1 won, [0,0,1]=player2 won).

Below is the tensorflow graph part of the program (it is a modified version of tensorflow tutorial at - https://www.tensorflow.org/get_started/mnist/pros).

baseFeatureSize = 64
x = tf.placeholder(tf.float32, shape=[None, 9])
x_image = tf.reshape(x, [-1, 3, 3, 1])
W_conv1 = nn_utils.weight_variable([2, 2, 1, baseFeatureSize])
b_conv1 = nn_utils.bias_variable([baseFeatureSize])
h_conv1 = tf.nn.relu(nn_utils.conv2d(x_image, W_conv1) + b_conv1)
W_conv2 = nn_utils.weight_variable([2, 2, baseFeatureSize, baseFeatureSize * 2])
b_conv2 = nn_utils.bias_variable([baseFeatureSize * 2])
h_conv2 = tf.nn.relu(nn_utils.conv2d(h_conv1, W_conv2) + b_conv2)
W_fc1 = nn_utils.weight_variable([3 * 3 * baseFeatureSize * 2, baseFeatureSize * 4])
b_fc1 = nn_utils.bias_variable([baseFeatureSize * 4])
h_pool2_flat = tf.reshape(h_conv2, [-1, 3 * 3 * baseFeatureSize * 2])
h_fc1 = tf.nn.relu(tf.matmul(h_pool2_flat, W_fc1) + b_fc1)
keep_prob = tf.placeholder(tf.float32)
h_fc1_drop = tf.nn.dropout(h_fc1, keep_prob)
W_fc2 = nn_utils.weight_variable([baseFeatureSize * 4, 3])
b_fc2 = nn_utils.bias_variable([3])
y_ = tf.placeholder(tf.float32, shape=[None, 3])
y_conv = tf.matmul(h_fc1_drop, W_fc2) + b_fc2

cross_entropy = tf.reduce_mean(tf.nn.softmax_cross_entropy_with_logits(labels=y_, logits=y_conv))
correct_prediction = tf.equal(tf.argmax(y_conv,1), tf.argmax(y_,1))
accuracy = tf.reduce_mean(tf.cast(correct_prediction, tf.float32))

def conv2d(x, W): return tf.nn.conv2d(x, W, strides=[1, 1, 1, 1], padding='SAME')
def max_pool_2x2(x): return tf.nn.max_pool(x, ksize=[1, 2, 2, 1], strides=[1, 2, 2, 1], padding='SAME')
def weight_variable(shape):
initial = tf.truncated_normal(shape, stddev=0.1)
return tf.Variable(initial)
def bias_variable(shape):
initial = tf.constant(0.1, shape=shape)
return tf.Variable(initial)


Questions - The above model works well but requires to train with over 700k inputs to get output prediction accuracy up to 80%. But the total possible permutations of the game board are less than 300K. If I feed just all of the unique permutations, then the accuracy worsens.

1. Is it normal for CNNs to require training data size to be much larger than all possible permutations of the inputs? I'm assuming this is not true or else they'd not be able to play chess and go etc, so what am I doing wrong?

2. Based on your experience, how big a training sample size would typically make sense for this setup?

• There are 19,683 game states, even counting impossible ones and ignoring symmetry. That's as opposed to move sequences which you asked in the linked question - but you are not using move sequences, the CNN is clearly processing the state of the board in your code. Really a CNN is a bad choice here, and your network is far too complex for the task you are attempting. You could likely get 100% accuracy using simple 1-hidden-layer fully connected network. Feb 25 '17 at 10:51
• Thank you. Yes, thanks for the correction regarding the game states, I had misinterpreted that question. I'll try a simpler model as you suggested. Feb 25 '17 at 11:01
• Could you elaborate on why a cnn is a bad choice though? I'm a newbie. Assuming a cnn could do the job (while probably being too much for this problem), is the lower accuracy because of it being overly complicated? Feb 25 '17 at 11:08
• I cannot really say where the CNN is going wrong in your case, so it is just a gut reaction. If I knew for certain then I would post an answer, but to do that I'd basically had to of already done your project or something very similar. I suggest that if simplifying your network is the fix, that you post your own answer here later . . . Feb 25 '17 at 11:12
• @Achilles No. CNN is not a good choice. Try a simple single layer, if not two layers. Don't do CNN here. A better model would require far less data. Feb 25 '17 at 11:32

I experimented with some other approaches as well and discovered that MLPs produce equivalent or better results for this problem. Thanks to the commenters Neil Slater and Student T for pointing me in the right direction.

For anyone interested, this is the model that eventually worked for me

boardSize = 3*3
featureSize = #I experimented with 500-1500 with varying results here
output = 3
x = tf.placeholder(tf.float32, [None, boardSize])
y_ = tf.placeholder(tf.float32, [None, featureSize])
learning_rate = 0.01
seed = 128
weights = {
'hidden': tf.Variable(tf.random_normal([boardSize, featureSize], seed=seed)),
'output': tf.Variable(tf.random_normal([featureSize, output], seed=seed))
}
biases = {
'hidden': tf.Variable(tf.random_normal([featureSize], seed=seed)),
'output': tf.Variable(tf.random_normal([output], seed=seed))
}
keep_prob = tf.placeholder(tf.float32)