Гипотеза: робот научится играть сам
Робот сыграет сам с собою много-много партий и таким образом сам научится хорошо играть. Вот такую гипотезу мы сформулировали для обучения робота.
Допускаем, что есть две различающиеся ситуации:
Число комбинаций условно невелико, и за некоторое количество партий можно сыграть все комбинации хотя бы по одному разу или по несколько раз.
Число комбинаций условно велико, и маловероятно, что даже за большое количество партий удастся сыграть все комбинации хотя бы по разу или по несколько раз.
Примером первой ситуации являются «Крестики-Нолики».
При поле 3X3 и двух типах фишек общее число возможных комбинаций равно 3 в 9 степени, то есть 19683 комбинаций.
При этом есть еще и невозможные комбинации. Например, на поле только 7 крестиков, или ряд крестиков и ряд ноликов и так далее. Фактически корректных комбинаций будет в разы меньше. Мы даже не будем оптимизировать с учетом симметричности, а возьмем все как есть и просто переберем.
Возможно, что, например, в шахматах ситуация другая и комбинаций уже много.Теоретически, это 33 в 64 степени, то есть 1,53 на 10 в 97 степени.
Это довольно много.
Конечно, могут быть ситуации и глупые, и невозможные, но это все равно очень много.
Для такой ситуации уже все комбинации не перебрать, нужно искать закономерности.
Оставим шахматы как пример второй ситуации и вернемся к "Крестики-Нолики".
Пусть робот сыграет много партий случайным выбором и сам определит «лучшие» ходы как те, при которых процент победных партий наибольший.
Обучение
Алгоритм обучения (псевдокод)
повторяем заданное число раз:
присваиваем отметку ходящей стороны
цикл "пока есть доступные ходы":
делаем ход:
делаем ход из доступных случайным выбором
формируем кодовое значение комбинации
запоминаем комбинацию в истории текущей партии
делаем проверку на победу
если победа, то:
присваиваем статус "победа"
выходим из цикла "пока есть доступные ходы"
удаляем ход из списка доступных
меняем сторону
если по окончании доступных ходов статуса нет, то "ничья"
фиксация:
цикл по каждой стороне по каждой комбинации из партии:
если такая комбинация есть, то +1 в количество с соответствующим статусом
если такой комбинации нет, то добавляем комбинацию и ставим 1 в количество с соответствующим статусом
Неоптимизированный код на python
# Заданное количество партий
# количество партий
N = 10**5
import random
print('started...')
available_list = list(range(1,10)) # список доступных ходов
win_list = ['123','456','789', '147', '258', '369', '159', '357'] # список выигрышных комбинаций
tableX = [] # таблица комбинаций X
tableO = [] # таблица комбинаций O
previous_tableX_length = len(tableX)
previous_tableO_length = len(tableO)
#tableX_procents = []
tableX_quantity = []
for k in range(N):
#print('Party', (k+1))
available_list = list(range(1,10))
current_status = 'start' # текущий статус партии
current_side = 'X' # текущая сторона
combination_code = 'C---------' # код комбинации
combination_code_history = [] # история комбинаций
# цикл делания ходов
while len(available_list):
side_step = random.choice(available_list)
#print(side_step)
combination_code = combination_code[:side_step] + current_side + combination_code[side_step + 1:]
#print(combination_code)
combination_code_history.append(combination_code)
for key in win_list:
if combination_code[int(key[0])] == current_side and combination_code[int(key[1])] == current_side and combination_code[int(key[2])] == current_side:
current_status = 'win' + current_side
#print(key)
break
if current_status == 'winX' or current_status == 'winO': break
available_list.remove(side_step)
#print(available_list)
current_side = 'O' if current_side == 'X' else 'X'
if current_status != 'winX' and current_status != 'winO':
current_status = 'draw'
# фиксация в базу
#для каждой комбинации в истории
for index,value in enumerate(combination_code_history):
# print()
# ищем комбинацию в крестиках
if index % 2 == 0:
#print(index,value)
# перебираем таблицу tableX
find_status = False
#print('tableX',tableX, len(tableX))
#print('value',value)
for index2,value2 in enumerate(tableX):
#print(value,value2[0])
# если находим
if value == value2[0]:
find_status = True
#print('нашли X', value)
previous_tableX_length = previous_tableX_length-1
#print(index,value,tableX[int(index2)][1],tableX[int(index2)][2],tableX[int(index2)][3])
if current_status == 'winX': tableX[int(index2)][1] = tableX[int(index2)][1] + 1
if current_status == 'winO': tableX[int(index2)][2] = tableX[int(index2)][2] + 1
if current_status == 'draw': tableX[int(index2)][3] = tableX[int(index2)][3] + 1
#print(index,value,tableX[int(index2)][1],tableX[int(index2)][2],tableX[int(index2)][3])
#print(tableX)
break
# если всю историю прошли и не нашли, то добавляем
if not find_status:
tableX.append([value,0,0,0])
#print('не нашли X')
#print(index,value,current_status,tableX[int(index/2+previous_tableX_length)][1],tableX[int(index/2)+previous_tableX_length][2],tableX[int(index/2)+previous_tableX_length][3])
if current_status == 'winX': tableX[int(index/2)+previous_tableX_length][1] = tableX[int(index/2)+previous_tableX_length][1] + 1
if current_status == 'winO': tableX[int(index/2)+previous_tableX_length][2] = tableX[int(index/2)+previous_tableX_length][2] + 1
if current_status == 'draw': tableX[int(index/2+previous_tableX_length)][3] = tableX[int(index/2)+previous_tableX_length][3] + 1
#print(index,value,current_status,tableX[int(index/2)+previous_tableX_length][1],tableX[int(index/2)+previous_tableX_length][2],tableX[int(index/2)+previous_tableX_length][3])
# то же самое в ноликах
else:
#print(index,value)
# перебираем таблицу tableO
find_status = False
for index2,value2 in enumerate(tableO):
#print(value,value2[0])
# если находим
if value == value2[0]:
find_status = True
#print('нашли O', value)
previous_tableO_length = previous_tableO_length - 1
#print(index,value,tableO[int(index2)][1],tableO[int(index2)][2],tableO[int(index2)][3])
if current_status == 'winO': tableO[int(index2)][1] = tableO[int(index2)][1] + 1
if current_status == 'winX': tableO[int(index2)][2] = tableO[int(index2)][2] + 1
if current_status == 'draw': tableO[int(index2)][3] = tableO[int(index2)][3] + 1
#print(index,value,tableO[int(index2)][1],tableO[int(index2)][2],tableO[int(index2)][3])
#print(tableO)
break
# если всю историю прошли и не нашли, то добавляем
if not find_status:
tableO.append([value,0,0,0])
#print('не нашли O')
#print(index,value,current_status,tableO[int(index/2+previous_tableO_length)][1],tableO[int(index/2+previous_tableO_length)][2],tableO[int(index/2)+previous_tableO_length][3])
if current_status == 'winO': tableO[int(index/2)+previous_tableO_length][1] = tableO[int(index/2)+previous_tableO_length][1] + 1
if current_status == 'winX': tableO[int(index/2)+previous_tableO_length][2] = tableO[int(index/2)+previous_tableO_length][2] + 1
if current_status == 'draw': tableO[int(index/2)+previous_tableO_length][3] = tableO[int(index/2)+previous_tableO_length][3] + 1
#print(index,value,current_status,tableO[int(index/2)+previous_tableO_length][1],tableO[int(index/2+previous_tableO_length)][2],tableO[int(index/2)+previous_tableO_length][3])
previous_tableX_length = len(tableX)
previous_tableO_length = len(tableO)
#tableX_procents.append(100*previous_tableX_length/(3**9))
tableX_quantity.append(previous_tableX_length)
if (k+1) % 10**4 == 0: print(k+1)
tableO.insert(0,['C---------','-','-','-'])
print('Party', (k+1))
print()
print('tableX', len(tableX))
print('table0', len(tableO))
Задаем количество партий, и робот играет сам с собой за обе стороны.
Уже со 100 000 партий робот находит 2739 комбинаций для крестиков и это количество не увеличивается с дальнейшим увеличением числа партий. При 1 миллионе партий и при 10 миллионах партий количество комбинаций остается тем же. Будем считать, что это и есть полное число корректных комбинаций. Теоретически, если робот выявил не все уникальные комбинации, то в процессе игры робот столкнется с неизвестной комбинацией и мы это увидим.
Выбор хода
Для выбора хода определяем возможные комбинации и по каждой возможной комбинации смотрим, в скольких процентах случаев достигается победа. Комбинация с наибольшим процентом и будет «лучшим» ходом.
Рассмотрим игру робота за «Крестики».
Первый ход для «Крестиков»:
CX-------- 11083 6720 60.63%
C-X------- 11172 6023 53.91%
C--X------ 10890 6609 60.69%
C---X----- 11077 5969 53.89%
C----X---- 11120 7728 69.50%
C-----X--- 11264 6018 53.43%
C------X-- 11104 6728 60.59%
C-------X- 11170 5950 53.27%
C--------X 11120 6698 60.23%
best_combination: C----X---- 69.50%
best_step: 5
best_step_history_1: [5]
- - -
- X -
- - -Ожидаемо, что лучший первый ход за «Крестики» - в самый центр поля.
Дальше смотрим все возможные ходы для «Ноликов» и на каждый из них все возможные ходы для «Крестиков». Ходы для «Ноликов» смотрим все, а за «Крестики» ходим «лучшими» ходами, то есть на каждый возможны ход «Ноликов» ходим «лучшим» ходов «Крестиков».
Возможные ответные ходы за «Нолики» после первого хода "Крестиков" в центр поля:
CO---X----
C-O--X----
C--O-X----
C---OX----
C----XO---
C----X-O--
C----X--O-
C----X---OПеребираем все возможные ходы за «Нолики» и ставим «лучший» за «Крестики».
История после ответного хода за «Крестики» получается такая:
best_step_history_2:
['513', '521', '539', '549', '569', '579', '587', '597']Для последующих ходов все аналогично.
Итог сыгранных партий
В итоге получаем полный перебор сыгранных партии за «Крестики», в которых перебраны все ходы за «Нолики», и на каждый ход «Ноликов» поставлен «лучший» ход «Крестиков»:
history_winX: ['51327:winX', '51327:winX', '51347:winX', '51347:winX', '51367:winX', '51367:winX', '51387:winX', '51387:winX', '51397:winX', '51397:winX', '52139:winX', '52139:winX', '52149:winX', '52149:winX', '52169:winX', '52169:winX', '52179:winX', '52179:winX', '52189:winX', '52189:winX', '53921:winX', '53921:winX', '53941:winX', '53941:winX', '53961:winX', '53961:winX', '53971:winX', '53971:winX', '53981:winX', '53981:winX', '54921:winX', '54921:winX', '54931:winX', '54931:winX', '54971:winX', '54971:winX', '54981:winX', '54981:winX', '56921:winX', '56921:winX', '56931:winX', '56931:winX', '56971:winX', '56971:winX', '56981:winX', '56981:winX', '57921:winX', '57921:winX', '57931:winX', '57931:winX', '57941:winX', '57941:winX', '57961:winX', '57961:winX', '57981:winX', '57981:winX', '58713:winX', '58713:winX', '58723:winX', '58723:winX', '58743:winX', '58743:winX', '58763:winX', '58763:winX', '58793:winX', '58793:winX', '59713:winX', '59713:winX', '59723:winX', '59723:winX', '59743:winX', '59743:winX', '59763:winX', '59763:winX', '59783:winX', '59783:winX', '5137426:winX', '5137486:winX', '5219734:winX', '5219743:winX', '5219764:winX', '5391248:winX', '5391268:winX', '5391278:winX', '5491728:winX', '5491738:winX', '5491768:winX', '5491783:winX', '5496718:winX', '5496728:winX', '5496738:winX', '5496783:winX', '5691728:winX', '5691738:winX', '5691748:winX', '5691783:winX', '5694718:winX', '5694728:winX', '5694738:winX', '5694783:winX', '5791426:winX', '5791436:winX', '5791486:winX', '5873129:winX', '5873149:winX', '5873169:winX', '5873194:winX', '5973614:winX', '5973624:winX', '5973684:winX', '513746892:winX', '513749826:winX', '513749862:winX', '521978634:winX', '521978643:winX', '539128674:winX', '579146238:winX', '597364218:winX']
history_winO: []
history_draw:['513746829:draw', '539128647:draw', '579146283:draw', '597364281:draw']
total: 122
winX: 118 96.72%
winO: 0 0.00%
draw: 4 3.28%Видно, что итог соответствует реальной игре.
Если после первого хода «Крестиков» «Нолик» ставится на боковое поле, то при корректной игре «Крестики» гарантированно выигрывают.
Если после первого хода «Крестиков» «Нолик» ставится в угол, то «Нолики» могут вытянуть самое большее на ничью, но не выиграть.
Подробнее по каждым ходам:
Первый ход
первый ход
CX-------- 11083 6720 60.63%
C-X------- 11172 6023 53.91%
C--X------ 10890 6609 60.69%
C---X----- 11077 5969 53.89%
C----X---- 11120 7728 69.50%
C-----X--- 11264 6018 53.43%
C------X-- 11104 6728 60.59%
C-------X- 11170 5950 53.27%
C--------X 11120 6698 60.23%
best_combination: C----X---- 69.50%
best_step: 5
best_step_history_1: [5]
- - -
- X -
- - -Второй ход
второй ход
current_combination_code: C----X----
1
analised_combibation_code_O: CO---X----
best_combination: CO-X-X---- 74.37%
best_step: 3
O - X
- X -
- - -
2
analised_combibation_code_O: C-O--X----
best_combination: CXO--X---- 79.32%
best_step: 1
X O -
- X -
- - -
3
analised_combibation_code_O: C--O-X----
best_combination: C--O-X---X 72.62%
best_step: 9
- - O
- X -
- - X
4
analised_combibation_code_O: C---OX----
best_combination: C---OX---X 79.19%
best_step: 9
- - -
O X -
- - X
6
analised_combibation_code_O: C----XO---
best_combination: C----XO--X 79.23%
best_step: 9
- - -
- X O
- - X
7
analised_combibation_code_O: C----X-O--
best_combination: C----X-O-X 73.63%
best_step: 9
- - -
- X -
O - X
8
analised_combibation_code_O: C----X--O-
best_combination: C----X-XO- 80.05%
best_step: 7
- - -
- X -
X O -
9
analised_combibation_code_O: C----X---O
best_combination: C----X-X-O 70.74%
best_step: 7
- - -
- X -
X - O
best_step_history_2:
['513', '521', '539', '549', '569', '579', '587', '597']
Третий ход
третий ход
513
current_combination_code: CO-X-X----
analised_combibation_code_O: COOX-X----
best_combination: COOX-X-X-- 100.00%
best_step: 7
winX
O O X
- X -
X - -
analised_combibation_code_O: CO-XOX----
best_combination: CO-XOX-X-- 100.00%
best_step: 7
winX
O - X
O X -
X - -
analised_combibation_code_O: CO-X-XO---
best_combination: CO-X-XOX-- 100.00%
best_step: 7
winX
O - X
- X O
X - -
analised_combibation_code_O: CO-X-X-O--
best_combination: CO-XXX-O-- 56.41%
best_step: 4
O - X
X X -
O - -
analised_combibation_code_O: CO-X-X--O-
best_combination: CO-X-X-XO- 100.00%
best_step: 7
winX
O - X
- X -
X O -
analised_combibation_code_O: CO-X-X---O
best_combination: CO-X-X-X-O 100.00%
best_step: 7
winX
O - X
- X -
X - O
521
current_combination_code: CXO--X----
analised_combibation_code_O: CXOO-X----
best_combination: CXOO-X---X 100.00%
best_step: 9
winX
X O O
- X -
- - X
analised_combibation_code_O: CXO-OX----
best_combination: CXO-OX---X 100.00%
best_step: 9
winX
X O -
O X -
- - X
analised_combibation_code_O: CXO--XO---
best_combination: CXO--XO--X 100.00%
best_step: 9
winX
X O -
- X O
- - X
analised_combibation_code_O: CXO--X-O--
best_combination: CXO--X-O-X 100.00%
best_step: 9
winX
X O -
- X -
O - X
analised_combibation_code_O: CXO--X--O-
best_combination: CXO--X--OX 100.00%
best_step: 9
winX
X O -
- X -
- O X
analised_combibation_code_O: CXO--X---O
best_combination: CXO--X-X-O 77.63%
best_step: 7
X O -
- X -
X - O
539
current_combination_code: C--O-X---X
analised_combibation_code_O: CO-O-X---X
best_combination: COXO-X---X 53.09%
best_step: 2
O X O
- X -
- - X
analised_combibation_code_O: C-OO-X---X
best_combination: CXOO-X---X 100.00%
best_step: 1
winX
X O O
- X -
- - X
analised_combibation_code_O: C--OOX---X
best_combination: CX-OOX---X 100.00%
best_step: 1
winX
X - O
O X -
- - X
analised_combibation_code_O: C--O-XO--X
best_combination: CX-O-XO--X 100.00%
best_step: 1
winX
X - O
- X O
- - X
analised_combibation_code_O: C--O-X-O-X
best_combination: CX-O-X-O-X 100.00%
best_step: 1
winX
X - O
- X -
O - X
analised_combibation_code_O: C--O-X--OX
best_combination: CX-O-X--OX 100.00%
best_step: 1
winX
X - O
- X -
- O X
549
current_combination_code: C---OX---X
analised_combibation_code_O: CO--OX---X
best_combination: CO--OX-X-X 77.50%
best_step: 7
O - -
O X -
X - X
analised_combibation_code_O: C-O-OX---X
best_combination: CXO-OX---X 100.00%
best_step: 1
winX
X O -
O X -
- - X
analised_combibation_code_O: C--OOX---X
best_combination: CX-OOX---X 100.00%
best_step: 1
winX
X - O
O X -
- - X
analised_combibation_code_O: C---OXO--X
best_combination: C---OXOX-X 100.00%
best_step: 7
- - -
O X O
X - X
analised_combibation_code_O: C---OX-O-X
best_combination: CX--OX-O-X 100.00%
best_step: 1
winX
X - -
O X -
O - X
analised_combibation_code_O: C---OX--OX
best_combination: CX--OX--OX 100.00%
best_step: 1
winX
X - -
O X -
- O X
569
current_combination_code: C----XO--X
analised_combibation_code_O: CO---XO--X
best_combination: CO---XOX-X 76.39%
best_step: 7
O - -
- X O
X - X
analised_combibation_code_O: C-O--XO--X
best_combination: CXO--XO--X 100.00%
best_step: 1
winX
X O -
- X O
- - X
analised_combibation_code_O: C--O-XO--X
best_combination: CX-O-XO--X 100.00%
best_step: 1
winX
X - O
- X O
- - X
analised_combibation_code_O: C---OXO--X
best_combination: C---OXOX-X 100.00%
best_step: 7
- - -
O X O
X - X
analised_combibation_code_O: C----XOO-X
best_combination: CX---XOO-X 100.00%
best_step: 1
winX
X - -
- X O
O - X
analised_combibation_code_O: C----XO-OX
best_combination: CX---XO-OX 100.00%
best_step: 1
winX
X - -
- X O
- O X
579
current_combination_code: C----X-O-X
analised_combibation_code_O: CO---X-O-X
best_combination: CO--XX-O-X 52.05%
best_step: 4
O - -
X X -
O - X
analised_combibation_code_O: C-O--X-O-X
best_combination: CXO--X-O-X 100.00%
best_step: 1
winX
X O -
- X -
O - X
analised_combibation_code_O: C--O-X-O-X
best_combination: CX-O-X-O-X 100.00%
best_step: 1
winX
X - O
- X -
O - X
analised_combibation_code_O: C---OX-O-X
best_combination: CX--OX-O-X 100.00%
best_step: 1
winX
X - -
O X -
O - X
analised_combibation_code_O: C----XOO-X
best_combination: CX---XOO-X 100.00%
best_step: 1
winX
X - -
- X O
O - X
analised_combibation_code_O: C----X-OOX
best_combination: CX---X-OOX 100.00%
best_step: 1
winX
X - -
- X -
O O X
587
current_combination_code: C----X-XO-
analised_combibation_code_O: CO---X-XO-
best_combination: CO-X-X-XO- 100.00%
best_step: 3
winX
O - X
- X -
X O -
analised_combibation_code_O: C-O--X-XO-
best_combination: C-OX-X-XO- 100.00%
best_step: 3
winX
- O X
- X -
X O -
analised_combibation_code_O: C--O-X-XO-
best_combination: CX-O-X-XO- 82.61%
best_step: 1
X - O
- X -
X O -
analised_combibation_code_O: C---OX-XO-
best_combination: C--XOX-XO- 100.00%
best_step: 3
winX
- - X
O X -
X O -
analised_combibation_code_O: C----XOXO-
best_combination: C--X-XOXO- 100.00%
best_step: 3
winX
- - X
- X O
X O -
analised_combibation_code_O: C----X-XOO
best_combination: C--X-X-XOO 100.00%
best_step: 3
winX
- - X
- X -
X O O
597
current_combination_code: C----X-X-O
analised_combibation_code_O: CO---X-X-O
best_combination: CO-X-X-X-O 100.00%
best_step: 3
winX
O - X
- X -
X - O
analised_combibation_code_O: C-O--X-X-O
best_combination: C-OX-X-X-O 100.00%
best_step: 3
winX
- O X
- X -
X - O
analised_combibation_code_O: C--O-X-X-O
best_combination: C--O-XXX-O 48.86%
best_step: 6
- - O
- X X
X - O
analised_combibation_code_O: C---OX-X-O
best_combination: C--XOX-X-O 100.00%
best_step: 3
winX
- - X
O X -
X - O
analised_combibation_code_O: C----XOX-O
best_combination: C--X-XOX-O 100.00%
best_step: 3
winX
- - X
- X O
X - O
analised_combibation_code_O: C----X-XOO
best_combination: C--X-X-XOO 100.00%
best_step: 3
winX
- - X
- X -
X O O
best_step_history_3:
['51327:winX', '51347:winX', '51367:winX', '51374', '51387:winX', '51397:winX', '52139:winX', '52149:winX', '52169:winX', '52179:winX', '52189:winX', '52197', '53912', '53921:winX', '53941:winX', '53961:winX', '53971:winX', '53981:winX', '54917', '54921:winX', '54931:winX', '54967', '54971:winX', '54981:winX', '56917', '56921:winX', '56931:winX', '56947', '56971:winX', '56981:winX', '57914', '57921:winX', '57931:winX', '57941:winX', '57961:winX', '57981:winX', '58713:winX', '58723:winX', '58731', '58743:winX', '58763:winX', '58793:winX', '59713:winX', '59723:winX', '59736', '59743:winX', '59763:winX', '59783:winX']Четвертый ход
четвертый ход
51374
current_combination_code: CO-XXX-O--
analised_combibation_code_O: COOXXX-O--
best_combination: COOXXXXO-- 100.00%
best_step: 6
winX
O O X
X X X
O - -
analised_combibation_code_O: CO-XXXOO--
best_combination: CO-XXXOOX- 51.52%
best_step: 8
O - X
X X O
O X -
analised_combibation_code_O: CO-XXX-OO-
best_combination: CO-XXXXOO- 100.00%
best_step: 6
winX
O - X
X X X
O O -
analised_combibation_code_O: CO-XXX-O-O
best_combination: CO-XXX-OXO 100.00%
best_step: 8
O - X
X X -
O X O
52197
current_combination_code: CXO--X-X-O
analised_combibation_code_O: CXOO-X-X-O
best_combination: CXOOXX-X-O 100.00%
best_step: 4
winX
X O O
X X -
X - O
analised_combibation_code_O: CXO-OX-X-O
best_combination: CXOXOX-X-O 100.00%
best_step: 3
winX
X O X
O X -
X - O
analised_combibation_code_O: CXO--XOX-O
best_combination: CXO-XXOX-O 100.00%
best_step: 4
winX
X O -
X X O
X - O
analised_combibation_code_O: CXO--X-XOO
best_combination: CXO--XXXOO 100.00%
best_step: 6
X O -
- X X
X O O
53912
current_combination_code: COXO-X---X
analised_combibation_code_O: COXOOX---X
best_combination: COXOOX--XX 100.00%
best_step: 8
winX
O X O
O X -
- X X
analised_combibation_code_O: COXO-XO--X
best_combination: COXO-XO-XX 100.00%
best_step: 8
winX
O X O
- X O
- X X
analised_combibation_code_O: COXO-X-O-X
best_combination: COXO-X-OXX 100.00%
best_step: 8
winX
O X O
- X -
O X X
analised_combibation_code_O: COXO-X--OX
best_combination: COXO-XX-OX 61.97%
best_step: 6
O X O
- X X
- O X
54917
current_combination_code: CO--OX-X-X
analised_combibation_code_O: COO-OX-X-X
best_combination: COO-OX-XXX 100.00%
best_step: 8
winX
O O -
O X -
X X X
analised_combibation_code_O: CO-OOX-X-X
best_combination: CO-OOX-XXX 100.00%
best_step: 8
winX
O - O
O X -
X X X
analised_combibation_code_O: CO--OXOX-X
best_combination: CO--OXOXXX 100.00%
best_step: 8
winX
O - -
O X O
X X X
analised_combibation_code_O: CO--OX-XOX
best_combination: CO-XOX-XOX 100.00%
best_step: 3
winX
O - X
O X -
X O X
54967
current_combination_code: C---OXOX-X
analised_combibation_code_O: CO--OXOX-X
best_combination: CO--OXOXXX 100.00%
best_step: 8
winX
O - -
O X O
X X X
analised_combibation_code_O: C-O-OXOX-X
best_combination: C-O-OXOXXX 100.00%
best_step: 8
winX
- O -
O X O
X X X
analised_combibation_code_O: C--OOXOX-X
best_combination: C--OOXOXXX 100.00%
best_step: 8
winX
- - O
O X O
X X X
analised_combibation_code_O: C---OXOXOX
best_combination: C--XOXOXOX 100.00%
best_step: 3
winX
- - X
O X O
X O X
56917
current_combination_code: CO---XOX-X
analised_combibation_code_O: COO--XOX-X
best_combination: COO--XOXXX 100.00%
best_step: 8
winX
O O -
- X O
X X X
analised_combibation_code_O: CO-O-XOX-X
best_combination: CO-O-XOXXX 100.00%
best_step: 8
winX
O - O
- X O
X X X
analised_combibation_code_O: CO--OXOX-X
best_combination: CO--OXOXXX 100.00%
best_step: 8
winX
O - -
O X O
X X X
analised_combibation_code_O: CO---XOXOX
best_combination: CO-X-XOXOX 100.00%
best_step: 3
winX
O - X
- X O
X O X
56947
current_combination_code: C---OXOX-X
analised_combibation_code_O: CO--OXOX-X
best_combination: CO--OXOXXX 100.00%
best_step: 8
winX
O - -
O X O
X X X
analised_combibation_code_O: C-O-OXOX-X
best_combination: C-O-OXOXXX 100.00%
best_step: 8
winX
- O -
O X O
X X X
analised_combibation_code_O: C--OOXOX-X
best_combination: C--OOXOXXX 100.00%
best_step: 8
winX
- - O
O X O
X X X
analised_combibation_code_O: C---OXOXOX
best_combination: C--XOXOXOX 100.00%
best_step: 3
winX
- - X
O X O
X O X
57914
current_combination_code: CO--XX-O-X
analised_combibation_code_O: COO-XX-O-X
best_combination: COO-XXXO-X 100.00%
best_step: 6
winX
O O -
X X X
O - X
analised_combibation_code_O: CO-OXX-O-X
best_combination: CO-OXXXO-X 100.00%
best_step: 6
winX
O - O
X X X
O - X
analised_combibation_code_O: CO--XXOO-X
best_combination: COX-XXOO-X 58.67%
best_step: 2
O X -
X X O
O - X
analised_combibation_code_O: CO--XX-OOX
best_combination: CO--XXXOOX 100.00%
best_step: 6
winX
O - -
X X X
O O X
58731
current_combination_code: CX-O-X-XO-
analised_combibation_code_O: CXOO-X-XO-
best_combination: CXOO-X-XOX 100.00%
best_step: 9
winX
X O O
- X -
X O X
analised_combibation_code_O: CX-OOX-XO-
best_combination: CX-OOX-XOX 100.00%
best_step: 9
winX
X - O
O X -
X O X
analised_combibation_code_O: CX-O-XOXO-
best_combination: CX-O-XOXOX 100.00%
best_step: 9
winX
X - O
- X O
X O X
analised_combibation_code_O: CX-O-X-XOO
best_combination: CX-OXX-XOO 100.00%
best_step: 4
winX
X - O
X X -
X O O
59736
current_combination_code: C--O-XXX-O
analised_combibation_code_O: CO-O-XXX-O
best_combination: CO-OXXXX-O 100.00%
best_step: 4
winX
O - O
X X X
X - O
analised_combibation_code_O: C-OO-XXX-O
best_combination: C-OOXXXX-O 100.00%
best_step: 4
winX
- O O
X X X
X - O
analised_combibation_code_O: C--OOXXX-O
best_combination: C-XOOXXX-O 53.42%
best_step: 2
- X O
O X X
X - O
analised_combibation_code_O: C--O-XXXOO
best_combination: C--OXXXXOO 100.00%
best_step: 4
winX
- - O
X X X
X O O
best_step_history_4:
['5137426:winX', '5137468', '5137486:winX', '5137498', '5219734:winX', '5219743:winX', '5219764:winX', '5219786', '5391248:winX', '5391268:winX', '5391278:winX', '5391286', '5491728:winX', '5491738:winX', '5491768:winX', '5491783:winX', '5496718:winX', '5496728:winX', '5496738:winX', '5496783:winX', '5691728:winX', '5691738:winX', '5691748:winX', '5691783:winX', '5694718:winX', '5694728:winX', '5694738:winX', '5694783:winX', '5791426:winX', '5791436:winX', '5791462', '5791486:winX', '5873129:winX', '5873149:winX', '5873169:winX', '5873194:winX', '5973614:winX', '5973624:winX', '5973642', '5973684:winX']Пятый ход
пятый ход
5137468
current_combination_code: CO-XXXOOX-
analised_combibation_code_O: COOXXXOOX-
best_combination: COOXXXOOXX 0.00%
best_step: 9
O O X
X X O
O X X
analised_combibation_code_O: CO-XXXOOXO
best_combination: COXXXXOOXO 100.00%
best_step: 2
winX
O X X
X X O
O X O
5137498
current_combination_code: CO-XXX-OXO
analised_combibation_code_O: COOXXX-OXO
best_combination: COOXXXXOXO 100.00%
best_step: 6
winX
O O X
X X X
O X O
analised_combibation_code_O: CO-XXXOOXO
best_combination: COXXXXOOXO 100.00%
best_step: 2
winX
O X X
X X O
O X O
5219786
current_combination_code: CXO--XXXOO
analised_combibation_code_O: CXOO-XXXOO
best_combination: CXOOXXXXOO 100.00%
best_step: 4
winX
X O O
X X X
X O O
analised_combibation_code_O: CXO-OXXXOO
best_combination: CXOXOXXXOO 100.00%
best_step: 3
winX
X O X
O X X
X O O
5391286
current_combination_code: COXO-XX-OX
analised_combibation_code_O: COXOOXX-OX
best_combination: COXOOXXXOX 0.00%
best_step: 7
O X O
O X X
X O X
analised_combibation_code_O: COXO-XXOOX
best_combination: COXOXXXOOX 100.00%
best_step: 4
winX
O X O
X X X
O O X
5791462
current_combination_code: COX-XXOO-X
analised_combibation_code_O: COXOXXOO-X
best_combination: COXOXXOOXX 100.00%
best_step: 8
winX
O X O
X X O
O X X
analised_combibation_code_O: COX-XXOOOX
best_combination: COXXXXOOOX 0.00%
best_step: 3
O X X
X X O
O O X
5973642
current_combination_code: C-XOOXXX-O
analised_combibation_code_O: COXOOXXX-O
best_combination: COXOOXXXXO 100.00%
best_step: 8
winX
O X O
O X X
X X O
analised_combibation_code_O: C-XOOXXXOO
best_combination: CXXOOXXXOO 0.00%
best_step: 1
X X O
O X X
X O O
best_step_history_5:
['513746829:draw', '513746892:winX', '513749826:winX', '513749862:winX', '521978634:winX', '521978643:winX', '539128647:draw', '539128674:winX', '579146238:winX', '579146283:draw', '597364218:winX', '597364281:draw']Создание базы «лучших» ходов
Теперь создадим базу «лучших» ходов для «Крестиков».
Для этого будем брать каждую комбинацию «Ноликов», определять возможные ходы для «Крестиков» и фиксировать ход, при котором процент выигранных партий наибольший.
Неоптимизированный код на python
# таблица лучших ходов для крестиков
combination_code = 'C---------'
current_side = 'X'
current_status = ''
tableO_for_best_step_for_X = []
print('started...')
print()
# для каждой комбинации после хода ноликов
for index, value in enumerate(tableO):
analysed_combination_code = value[0]
# создаем возможные ходы для крестиков
available_list = []
for index2, value2 in enumerate(analysed_combination_code):
if analysed_combination_code[index2] == '-': available_list.append(index2)
if index or not index:
#if index < 2:
#print(analysed_combination_code)
#print(available_list)
# смотрим "лучший" ход
best_procent = 0
best_combination = ''
best_step = ''
#смотрим возможные комбинации X
for key in available_list:
current_status = ''
combination_code = analysed_combination_code[:key] + current_side + analysed_combination_code[key + 1:]
#print(combination_code)
for key2 in tableX:
if combination_code == key2[0]:
total = key2[1] + key2[2] + key2[3]
#print(key2[0], total, key2[1], "{:.2%}".format(key2[1]/total))
if key2[1]/total >= best_procent:
best_procent = key2[1]/total
best_combination = key2[0]
best_step = key
if not best_step:
best_step = 'none'
#print('best_step:',best_step)
tableO_for_best_step_for_X.append([analysed_combination_code, best_step])
#print()
print(tableO_for_best_step_for_X)
print(len(tableO_for_best_step_for_X))
print() Получили базу «лучших» ходов для «Крестиков»:
[['C---------', 5], ['C-----X--O', 5], ['C--OX-X--O', 5], ['CX------O-', 5], ['CX-X--O-O-', 2], ['CXOXX-O-O-', 7], ['CXOXXXOOO-', 9], ['C------X-O', 5], ['COX----X-O', 5], ['COX--OXX-O', 'none'], ['C-------OX', 5], ['CO----X-OX', 3], ['CO--OXX-OX', 3], ['COXOOXX-OX', 7], ['C---XO----', 1], ['C-O-XO--X-', 7], ['COO-XO--XX', 7], ['C--O---X--', 9], ['C--O--OX-X', 8], ['COXO--OX-X', 8], ['COXO-XOXOX', 4], ['COX---XOOX', 4], ['COX-OXXOOX', 'none'], ['CO-X------', 5], ['CO-X-OX---', 9], ['CO-XXOX-O-', 9], ['C----O-X--', 9], ['C-X--OOX--', 1], ['C-XX-OOX-O', 1], ['C--X--O---', 5], ['CXOX--O---', 5], ['CXOX--O-OX', 5], ['C-O------X', 5], ['C-OX--O--X', 5], ['COOXX-O--X', 7], ['COOXXXO-OX', 7], ['CXO----O-X', 5], ['CXO--OXO-X', 3], ['CXO-XOXOOX', 'none'], ['C--X-----O', 5], ['C--X--XO-O', 8], ['CX-X-OXO-O', 2], ['CX-----O--', 5], ['CX-O-X-O--', 9], ['CX-O-XXO-O', 8], ['CX-O------', 9], ['CX-OXO----', 7], ['CX-OXO-O-X', 'none'], ['CO----X---', 3], ['COO---X--X', 3], ['COOO--XX-X', 'none'], ['C-X---O---', 5], ['C-X-O-OX--', 5], ['CXX-O-OX-O', 3], ['C--O-X----', 9], ['C--OXX---O', 6], ['C-X--O----', 3], ['C-X-XO--O-', 1], ['C-X-XOOXO-', 1], ['C---X---O-', 5], ['C---XX-OO-', 6], ['C-OXXX-OO-', 9], ['CXOXXX-OOO', 'none'], ['CX--O-----', 5], ['CX--OOX---', 3], ['CXOXOOX---', 9], ['C-O-X-----', 5], ['C-O-X-X--O', 5], ['C-OXX-X-OO', 5], ['CXOOX-----', 7], ['CXOOX-O-X-', 9], ['CXOOXOO-XX', 7], ['C----X-O--', 2], ['CX---X-O-O', 8], ['CXO-XX-O-O', 6], ['C-----X-O-', 5], ['C--XO-X-O-', 9], ['CX-XO-X-OO', 7], ['CXOXO-XXOO', 5], ['C-OX------', 5], ['C-OXO----X', 6], ['CX-OX--O--', 5], ['CXXOX-OO--', 5], ['CXXOXOOO-X', 'none'], ['C-----XO--', 5], ['C--X-OXO--', 9], ['C-O----X--', 1], ['CXOO---X--', 4], ['CXOO--XXO-', 5], ['CXOOO-XXOX', 5], ['C----OXO-X', 3], ['CO-------X', 7], ['COO-X----X', 3], ['COOXX---OX', 6], ['C--OX---OX', 5], ['C--OXXO-OX', 1], ['C-----O--X', 5], ['C----OO-XX', 7], ['C-OX-OO-XX', 7], ['CXOX-OOOXX', 4], ['CO------X-', 5], ['COO----XX-', 9], ['COO--XOXX-', 9], ['C--O-X--XO', 2], ['CX-O-X-OXO', 6], ['CXOOXX-OXO', 6], ['C--X-O----', 2], ['C--X-OO-X-', 7], ['CXOX-OO-X-', 4], ['C--X-OXOXO', 1], ['CX-XOOXOXO', 2], ['CO-X--X--O', 5], ['COOX-XX--O', 8], ['C--OX-OX--', 1], ['CX--O--OX-', 5], ['CX--OOXOX-', 3], ['CXX-OOXOXO', 3], ['C---O--X--', 9], ['C-X-OO-X--', 6], ['C-X-OOOXX-', 'none'], ['C--O-OXX--', 8], ['C--O-OXXOX', 4], ['C-OOXOXXOX', 'none'], ['C-O--O-XX-', 9], ['C-O--OXXXO', 4], ['C-OXOOXXXO', 1], ['C-XX----OO', 1], ['C-XXO--XOO', 6], ['C--X---O--', 9], ['C--X-X-OO-', 9], ['CX-X-X-OOO', 'none'], ['C---X--O--', 5], ['CO--X-XO--', 5], ['C--X-XO-O-', 7], ['CX-XOXO-O-', 9], ['CX--OX-O--', 9], ['CX-XOX-O-O', 2], ['CXOXOX-OXO', 6], ['C-OXX--O--', 6], ['C-OXX-OO-X', 1], ['CXOXX-OOOX', 5], ['C-X-----O-', 1], ['C-XXX-O-OO', 7], ['C-XXXOOXOO', 1], ['C---O-X---', 9], ['C---O-X-XO', 5], ['CO-XO-X-XO', 5], ['COXXO-XOXO', 'none'], ['C-O-X-OX--', 1], ['COOXX-OX--', 9], ['COX---O--X', 7], ['COXO--O-XX', 7], ['C--X-X-O-O', 8], ['C--XXXOO-O', 2], ['CO-XXXOOXO', 2], ['C-----OX--', 5], ['CO--X-OX--', 3], ['CO--XXOXO-', 3], ['CO-OXXOXOX', 2], ['C-O--X----', 6], ['C-O-XX---O', 6], ['COOXXX---O', 8], ['COOXXXO-XO', 7], ['CXOX---O--', 9], ['CXOXOX-O--', 9], ['CXOXOXOOX-', 9], ['CO-X---X-O', 5], ['COOX--XX-O', 5], ['COOX-OXXXO', 'none'], ['C--O--XX-O', 4], ['C--O-XXXOO', 4], ['CX-OOXXXOO', 2], ['C-O--XX-O-', 4], ['COO--XX-OX', 4], ['COO-OXXXOX', 3], ['CX---O----', 4], ['CX--OO---X', 3], ['CX-XOOO--X', 'none'], ['C---O---X-', 5], ['CXO-O---X-', 9], ['CXO-O-OXX-', 9], ['CXO-OXOXXO', 3], ['C--O-----X', 1], ['C--O--XO-X', 5], ['CX-O--XOOX', 5], ['CXOOX-XOOX', 5], ['C------O-X', 5], ['CO--XOXO-X', 3], ['COXOXOXO-X', 'none'], ['C---OXX--O', 8], ['CX--OXX-OO', 7], ['CX-XOXXOOO', 'none'], ['CX-O--X--O', 4], ['CX-OOXXOXO', 2], ['C-O-X-O--X', 7], ['C-OXX-O-OX', 5], ['C-OXXXOOOX', 1], ['C------OX-', 5], ['C-X--O-OX-', 1], ['CXXO-O-OX-', 'none'], ['C----X---O', 3], ['C-O-OXX-XO', 3], ['CXO-OXXOXO', 3], ['CXOO-OXOXX', 'none'], ['C------XO-', 5], ['C--X--OXO-', 5], ['CX-X-OOXO-', 4], ['CX-X---OO-', 2], ['CX-----OOX', 5], ['C--O----X-', 9], ['C--O-XO-X-', 2], ['CX-O-XO-XO', 'none'], ['C-O---X---', 5], ['C-O--XX--O', 4], ['C-OXX---O-', 5], ['C-OXXXO-O-', 9], ['CXOXXXO-OO', 7], ['C-X---XOO-', 9], ['CXX-O-XOO-', 9], ['COX-------', 5], ['COX----O-X', 6], ['COXXO--O-X', 'none'], ['C-OO---XX-', 9], ['CXOOO--XX-', 9], ['CXOOOXOXX-', 9], ['C----XO---', 2], ['C--O-XO--X', 1], ['C--OXXOO-X', 8], ['CO-OXXOOXX', 2], ['CO---X----', 3], ['CO---X-XO-', 3], ['CO-O-X-XOX', 6], ['C-OO--X--X', 1], ['COX--X-O--', 8], ['COXX-X-O-O', 8], ['C--OX-----', 5], ['CX-OXO--OX', 7], ['CXOOXOX-OX', 'none'], ['C--O--X---', 5], ['COXO--X---', 5], ['COXOO-X--X', 8], ['COXOO-XOXX', 'none'], ['CXO-------', 7], ['CXO--O-X--', 4], ['CXO--O-XOX', 'none'], ['C-OX---XO-', 5], ['C-OXO-XXO-', 9], ['C--O-X-OX-', 2], ['CX-OOX-OX-', 9], ['COX-O-X---', 7], ['COX-O-XOX-', 'none'], ['C-OO---X-X', 8], ['C-OO-XOX-X', 8], ['C----X--O-', 7], ['C--O-X--OX', 1], ['C-OO-X-XOX', 1], ['C-OOXXOXOX', 1], ['CO-OX-X---', 5], ['CO-OX-XX-O', 5], ['COXOXOXX-O', 'none'], ['CXO--OOXX-', 9], ['COX---X--O', 5], ['COX-OXX--O', 8], ['COXXOXX-OO', 7], ['CXO--O---X', 8], ['CXOX-OO--X', 8], ['CXOXOOO-XX', 'none'], ['C--OXO---X', 7], ['C--OXOOX-X', 8], ['CXO--X-O--', 9], ['CXOO-XXO--', 9], ['CXOO-XXOXO', 4], ['CO---XO-X-', 2], ['CO-X-XO-XO', 7], ['C-OXO-X-XO', 5], ['CXOXOOX-XO', 7], ['C--OO--XX-', 9], ['C--OOOXXX-', 9], ['CXOOOOXXX-', 9], ['C-XX--OO--', 1], ['COXX--OOX-', 5], ['COXXO-OOXX', 'none'], ['CXO-O----X', 5], ['CXO-O-OX-X', 8], ['COX--XO---', 8], ['CX---OXO--', 3], ['CX-OOOXOXX', 'none'], ['C--XO-----', 5], ['C--XO-XXOO', 5], ['C-X-O-X-O-', 3], ['C-XOOXX-O-', 9], ['C---X----O', 7], ['CX--X--O-O', 8], ['CX-OX--OXO', 6], ['CX-OXXOOXO', 'none'], ['C-OX---X-O', 5], ['CXOX---XOO', 5], ['CXO-----OX', 5], ['CXO---XOOX', 5], ['COX--OX---', 9], ['CX-------O', 3], ['CX--XO---O', 7], ['CX-XXO--OO', 7], ['C-----O-X-', 5], ['C--XO-O-X-', 5], ['C-OXO-OXX-', 9], ['CX--XO--O-', 7], ['CXOXXO--O-', 'none'], ['C--OXOX---', 1], ['CO-OXOX-X-', 9], ['COOOXOXXX-', 'none'], ['C----O-XOX', 3], ['C---OOXXOX', 3], ['CX-OOOXXOX', 2], ['C-OOX--X--', 1], ['C--X----O-', 5], ['CO-X--X-O-', 9], ['C---X-X-OO', 5], ['CO--X-XXOO', 5], ['C----O---X', 3], ['C--X-O-O-X', 6], ['C--XXO-OOX', 6], ['CXOXXO-OOX', 'none'], ['C-O----XXO', 1], ['C-OO--XXXO', 4], ['COOOX-XXXO', 'none'], ['C--OX--OX-', 5], ['C--X-OX-O-', 9], ['C--X-OXXOO', 1], ['CXOX-OXXOO', 'none'], ['C-OX--XO--', 9], ['C-OXOXXO--', 9], ['C---X-O---', 1], ['C---X-O-XO', 3], ['CX-OX-O-XO', 'none'], ['C--X-OO--X', 4], ['C--XXOO-OX', 1], ['C-OXXOOXOX', 'none'], ['C-XO--OX--', 9], ['C-XO--OXXO', 'none'], ['C-O-X--XO-', 1], ['C-O-XOXXO-', 'none'], ['C---O--OXX', 1], ['C-X-O-OOXX', 5], ['CX-O-O-X--', 4], ['CXOO-OXX--', 8], ['CXOOOOXX-X', 8], ['CX--O--X-O', 3], ['CX--O-OXXO', 3], ['CX-XOOOXXO', 'none'], ['C-X-O-O-X-', 5], ['COX-O-OXX-', 9], ['C-XXO---O-', 1], ['COX-----XO', 5], ['COXXO---XO', 5], ['COXXO-OXXO', 5], ['C--OXOXO-X', 'none'], ['C-OX--X--O', 5], ['CXOX-OX--O', 8], ['CXOXXOXO-O', 8], ['CXO-OO--XX', 7], ['CXO-OOXOXX', 3], ['CO-O-X---X', 2], ['CO-OOX--XX', 7], ['C--O-X-XO-', 4], ['C--O-XOXOX', 1], ['C---XOO--X', 7], ['C-OXXOO--X', 7], ['CXOXXOO-OX', 'none'], ['CXO-O--X--', 5], ['CXOXO-OX--', 5], ['CXOXO-OXOX', 5], ['CX-XO-XOO-', 9], ['CO-O-XX---', 4], ['C-------XO', 5], ['C---OX--XO', 2], ['C--OOX-XXO', 2], ['CX-OOXOXXO', 'none'], ['C---XOXO--', 9], ['C-O-XOXO-X', 3], ['C-X----O--', 5], ['COX----OX-', 5], ['COX---XOXO', 5], ['CO---XX-O-', 4], ['CO-X-XX-OO', 7], ['C--XO--OX-', 1], ['CO-XO--OXX', 'none'], ['C-O-----X-', 7], ['C-O---O-XX', 7], ['CXO---OOXX', 5], ['CXOOX-OOXX', 5], ['C-XOX--O--', 5], ['C-XOXOXO--', 'none'], ['C-O----XOX', 5], ['C-OOX--XOX', 1], ['COOOX-XXOX', 'none'], ['C---OX-OX-', 2], ['C----OX---', 3], ['C-X-OOX---', 3], ['C-XXOOX-O-', 9], ['COXXOOXXO-', 9], ['C-X-X-OO--', 3], ['C-XXXOOO--', 1], ['COXXXOOO-X', 8], ['CX----X-OO', 7], ['CX--XOX-OO', 7], ['CX-XXOXOOO', 'none'], ['CX--OXOX-O', 3], ['CX----O---', 5], ['CXO---O-X-', 7], ['CXO-XOO-X-', 7], ['C--X---OXO', 2], ['C--XOX-OXO', 2], ['CX-XOXOOXO', 2], ['C-X----OOX', 1], ['CXXO---OOX', 5], ['CXXO-OXOOX', 'none'], ['CXOO--X-OX', 5], ['C-OXX-OOX-', 9], ['C-OXXOOOXX', 1], ['CX--OO-OXX', 6], ['CXXOOO-OXX', 'none'], ['C---OO-XX-', 9], ['C---OOXXXO', 3], ['C--OX---XO', 6], ['COXOX---XO', 5], ['COXOX-XOXO', 5], ['C-O-XOOXX-', 9], ['CX-XO-O---', 5], ['C-OOX----X', 1], ['CXOOXO---X', 7], ['C-X-O-----', 5], ['C-X-OOXXO-', 3], ['C-XOOOXXOX', 1], ['C-X-O-XO--', 1], ['C-X-O-XOXO', 5], ['CO-----X--', 3], ['COO----X-X', 8], ['COO-XO-X-X', 8], ['C-X-O--O-X', 1], ['C-X-OX-OOX', 1], ['C-X--OO-X-', 4], ['COX-XOO-X-', 9], ['COX-XOOXXO', 'none'], ['C--OO-XX--', 9], ['C-XOOOXX--', 8], ['CXOXO--OX-', 9], ['CXOO-----X', 5], ['CXOOX--O-X', 5], ['CXOOXO-OXX', 'none'], ['C-OO--X-X-', 1], ['C-OO-XX-XO', 4], ['C-OOOXXXXO', 1], ['C-XO------', 5], ['C-XOO--X--', 9], ['C-XOOO-X-X', 8], ['C----XXO-O', 4], ['C-X--O-O-X', 3], ['COX--O-OXX', 6], ['COX-OOXOXX', 'none'], ['C-X--OXO--', 3], ['CXX--OXOO-', 3], ['CXX-OOXOOX', 3], ['C-XO-X-O--', 8], ['CXXO-X-O-O', 8], ['CXXOXX-OOO', 'none'], ['CXO-X--OXO', 6], ['CXO-XOXOXO', 3], ['C--O--X-OX', 5], ['CO-OX-X-OX', 5], ['COXOXOX-OX', 7], ['CO---OX-X-', 9], ['COXO-OX-X-', 9], ['COXOXOXOX-', 'none'], ['C-OOXXOX--', 1], ['COOOXXOXX-', 'none'], ['CO----X-XO', 5], ['CO---XXOXO', 4], ['CO-XOXXOXO', 'none'], ['CX-OO-X---', 5], ['CX-OO-X-OX', 5], ['C--XXO--O-', 2], ['C-XXXOOOOX', 1], ['C--O---XXO', 6], ['C--OXO-XXO', 1], ['C-X--XO--O', 8], ['C-X-X-O--O', 3], ['CXXOX-O--O', 'none'], ['COXO-XOX--', 8], ['COXOXXOXO-', 9], ['COX-OX----', 8], ['CO--O--XX-', 9], ['COXOO--XX-', 9], ['C-O---OXX-', 9], ['C-XXO--O--', 1], ['C-XXO--OOX', 6], ['COXXOX-OOX', 'none'], ['CXXO-OX--O', 4], ['CXXOOOXX-O', 8], ['C---OX----', 1], ['CX--OXXO-O', 8], ['COXXO-----', 7], ['COXXOO---X', 6], ['COXXOO-OXX', 'none'], ['COXX----O-', 7], ['COXXX---OO', 7], ['COXXX-XOOO', 'none'], ['CO--X--OX-', 5], ['COX-X-OOX-', 5], ['COXXXOOOX-', 9], ['C-O-X--OX-', 6], ['COO-X--OXX', 6], ['COO-XXOOXX', 3], ['CO----XO-X', 3], ['CXX---O-O-', 3], ['CXXO--O-OX', 7], ['CXXOX-OOOX', 5], ['CO----O-XX', 7], ['CO-X-OO-XX', 7], ['COXX-OOOXX', 4], ['CXOO--X---', 4], ['CXOOO-XX--', 9], ['C-OX--X-O-', 9], ['CXXO-----O', 6], ['CXXO-O-X-O', 4], ['CXXO-OOXXO', 'none'], ['COXX---OXO', 5], ['COXXX-OOXO', 5], ['COOX----X-', 6], ['COOX-X--XO', 7], ['C--O-O-X-X', 8], ['COXOO-XX--', 8], ['COXOOXXX-O', 8], ['CX--O-OX--', 5], ['CX--OOOX-X', 'none'], ['C-XOX----O', 5], ['C-XOX-XO-O', 5], ['CXXOXOXO-O', 'none'], ['CXOXO-----', 5], ['CXOXOO-X--', 9], ['CXOXOOOXX-', 'none'], ['CXO----XO-', 5], ['CXO--OXXO-', 'none'], ['C-XXOO----', 1], ['CO--X-----', 5], ['CO--X--O-X', 6], ['CO--XX-OOX', 6], ['COX-XXOOOX', 3], ['C----O--X-', 7], ['C---OOX-X-', 9], ['CX-OOOX-X-', 7], ['C-XXXO--OO', 1], ['COXXXOX-OO', 'none'], ['C-OXO--X--', 5], ['COOXO--X-X', 8], ['CXOO-X-XO-', 9], ['CX---OOX--', 4], ['CXX-OOOX--', 'none'], ['CX--OX--O-', 9], ['CX-OOX-XO-', 9], ['CXO----OX-', 9], ['CXOO---OXX', 5], ['C---O----X', 5], ['C---OO-X-X', 8], ['C-----XOXO', 5], ['CX--O-XOXO', 2], ['C-XOX-O---', 9], ['C-XOXXO-O-', 9], ['C-XOXXOXOO', 'none'], ['CXOXOX--O-', 9], ['CX-----OXO', 2], ['CXX---OOXO', 5], ['CXO-OX----', 9], ['CXOOOXX---', 9], ['C-OX-X-O--', 9], ['C-OX-XOO-X', 1], ['COOXXXOO-X', 8], ['CX-O-OO-XX', 7], ['CO----OXX-', 9], ['CO-XO-OXX-', 9], ['CXX-----OO', 3], ['CXX-XO--OO', 7], ['CX-XOOOOXX', 'none'], ['C--X--X-OO', 7], ['CX-XOOXXOO', 2], ['CXXOX--O-O', 8], ['CXXOXO-OXO', 'none'], ['CX-XOOOX--', 'none'], ['CXO--OO-XX', 7], ['C---O-X-OX', 3], ['C-X-X-O-O-', 1], ['C-XOX-O-OX', 1], ['CXXOXOO-OX', 7], ['COX--OX-OX', 3], ['COX-OOXXOX', 3], ['C---O-XXO-', 3], ['C--XOOXXO-', 9], ['C--XO-O--X', 5], ['C-XXO-O-OX', 5], ['CO--OXX---', 7], ['COO-OXX--X', 3], ['COOOOXX-XX', 'none'], ['CXO-O-XOX-', 9], ['CXOO-OXXXO', 4], ['C---O-O-XX', 7], ['CX--OOO-XX', 'none'], ['C--XO---OX', 6], ['CXO---X--O', 4], ['CXO-X-X-OO', 7], ['C-X---OXO-', 1], ['CXX-O-OXO-', 5], ['CXXOO-OXOX', 5], ['C-XO--X-O-', 4], ['COXO--XXO-', 5], ['COXOXOXXO-', 9], ['C-XO-X---O', 8], ['COX-O----X', 7], ['COX-OO-X-X', 8], ['C--XX-O-O-', 1], ['C--XXXOOO-', 1], ['COXXXXOOO-', 9], ['C-XOX-OOX-', 5], ['C-XOXOOOXX', 'none'], ['C-X-XOO---', 1], ['COX-XOOX--', 9], ['COX-XOOXOX', 3], ['C-OXX----O', 7], ['CXOXX--O-O', 8], ['CXOXX-XOOO', 'none'], ['C--XOX-O--', 1], ['CX-XOX-OO-', 9], ['COXX--OO-X', 8], ['CO--XOX---', 9], ['CO-XXOXO--', 9], ['COXXXOXO-O', 'none'], ['CX---X--OO', 7], ['CXO-XX--OO', 7], ['CX--O--O-X', 5], ['CX--O-XOOX', 5], ['CO-X----OX', 6], ['CO-XO--XOX', 6], ['COXX-OO--X', 8], ['C-O-O--XX-', 9], ['C-OOO-XXX-', 9], ['CXOOO-XXXO', 5], ['C-XO-O--X-', 9], ['C-XOXO--XO', 7], ['C-XOXOOXXO', 'none'], ['COXX---O--', 4], ['CO--X-X-O-', 5], ['CO-XX-X-OO', 5], ['COOXX-XXOO', 5], ['COX--X--O-', 7], ['COXO-XX-O-', 4], ['COXOOXXXO-', 9], ['CX---O-XO-', 4], ['CX-OO--X--', 9], ['CX-OO-XXO-', 9], ['C-O-XXO---', 7], ['CO-O--XX--', 8], ['CO-OX-OXX-', 9], ['CO-OXXOXXO', 'none'], ['C-X-OXO---', 8], ['C-XXOXOO--', 8], ['COXXOX-O--', 'none'], ['C-O--XXO--', 4], ['C-OX-XXOO-', 9], ['C----X-OOX', 1], ['C-X--XOOOX', 1], ['COXX-XOOOX', 4], ['C--OOX---X', 1], ['C--OOX-OXX', 2], ['CO--OX-X--', 3], ['CO--OXXXO-', 3], ['C--OX--O-X', 5], ['C-XOXO-O-X', 'none'], ['C--XOOO-XX', 'none'], ['C---XO-O-X', 3], ['C--XXOOO-X', 2], ['C--OX-X-O-', 5], ['C-XOX-X-OO', 7], ['CXXOXOX-OO', 7], ['C--OXOXOX-', 'none'], ['C-O--OXOXX', 3], ['CX-X-O---O', 2], ['CXOXXO-O--', 9], ['CX-OO---X-', 9], ['CXOOO---XX', 7], ['C-XO--O--X', 5], ['CXXO--OO-X', 5], ['C--OXO--X-', 7], ['C-XO--X--O', 5], ['C-XOO-XX-O', 5], ['CXXOO-XXOO', 5], ['COX-O-X-OX', 3], ['COOX-X----', 7], ['COOXXX--O-', 9], ['C-X--O--XO', 1], ['C-X--OXOXO', 3], ['COX-XOXOXO', 'none'], ['CO-----OXX', 4], ['COXO---OXX', 5], ['COXOXO-OXX', 'none'], ['C-XX--O-O-', 1], ['C-XXOXO-O-', 9], ['C-XXOXOOOX', 1], ['C-OO-X--X-', 1], ['C-OO-XO-XX', 7], ['C---XO-XO-', 1], ['CO--XO-XOX', 6], ['COOXXO-XOX', 'none'], ['CX-O----XO', 6], ['CXXO-O--XO', 7], ['CXXOXOO-XO', 'none'], ['C----X-OXO', 2], ['CXO--X-OXO', 6], ['CXO-XXOOXO', 3], ['C-X-XO-O--', 3], ['C-X-XO-OOX', 3], ['CXX-XOOOOX', 3], ['CXX-O--O--', 3], ['CXXOO--O-X', 5], ['C-OXXO----', 8], ['CXOXXO---O', 7], ['C-OX---O-X', 6], ['C-OXXO-O-X', 6], ['CXOXXOOO-X', 8], ['C--OO-X--X', 1], ['CX-OO-XO-X', 5], ['C--XOO---X', 6], ['C--X-OOX--', 4], ['C--XXOOXO-', 1], ['C---XOX--O', 1], ['CO--XOX-XO', 'none'], ['C-OO-XX---', 4], ['COOO-XXX--', 'none'], ['C--O--X-XO', 5], ['C--OX-XOXO', 5], ['C---X-XO-O', 5], ['CX-O-X---O', 6], ['CX-OXX-O-O', 6], ['C--OXXO---', 9], ['COXOXXOO-X', 8], ['C--X--O-XO', 5], ['COXX--O-XO', 5], ['CXO-O-X---', 9], ['CXOOO-X-X-', 9], ['CXOOOXX-XO', 7], ['C-O-XX--O-', 6], ['C-O-XXOXO-', 9], ['C-XOO-X---', 8], ['COXOOXX---', 8], ['C---XX--OO', 6], ['CO-XXX--OO', 7], ['COXXXX-OOO', 'none'], ['C-XO----OX', 1], ['COXO-X--OX', 6], ['CXOOO-X--X', 8], ['C----O-OXX', 6], ['C---XOOOXX', 3], ['CXO-XOOOXX', 3], ['C-OO-X-X--', 1], ['C-OOOX-X-X', 8], ['C---O-XX-O', 5], ['CO--O-XXXO', 5], ['COOXO-XXXO', 5], ['C---XO-X-O', 1], ['CXOXOOXX-O', 8], ['CX--O-O--X', 5], ['C--XOX---O', 7], ['CO-XOXX--O', 7], ['COXXOXXO-O', 'none'], ['CXO----X-O', 4], ['CXO--XOX-O', 4], ['C--X-O-OX-', 1], ['C--X-OOOXX', 4], ['CXO-X----O', 7], ['CXOXXXOO-O', 8], ['CX-O-O--X-', 7], ['CX-O-OXOX-', 'none'], ['C-X-O---OX', 3], ['CXX-OO--OX', 3], ['C-X---OO-X', 5], ['CXX-OOOOXX', 'none'], ['C-O--XO--X', 1], ['C-XXOOO--X', 'none'], ['CX-O--XO--', 5], ['CX-OX-XOO-', 5], ['C-X------O', 5], ['CXX-O----O', 3], ['CXX-OXO--O', 8], ['CXX-OXOXOO', 3], ['C--O-X-X-O', 6], ['C--XO-XO--', 9], ['C--XOOXOX-', 9], ['C-X--X--OO', 7], ['CXX--X-OOO', 'none'], ['CO--OXXX-O', 8], ['C--OXO-X--', 1], ['C--OXO-XOX', 1], ['COXOXO-XOX', 6], ['COO-X-X---', 5], ['COO-X-X-OX', 5], ['CX--OO--X-', 6], ['CXX-OO-OX-', 3], ['CXXOOOXOX-', 'none'], ['CX-OXOXO--', 'none'], ['C-XOOOX-X-', 9], ['COXOOOXXX-', 9], ['CX---OO-X-', 4], ['CX---OOOXX', 4], ['COXX--OXO-', 5], ['COXXX-OXOO', 5], ['C-X-XOXOO-', 9], ['C-XOXOXOOX', 'none'], ['C-XO-XO---', 8], ['CXXO-XOO--', 9], ['CX-O-OXXO-', 4], ['CXOO-OXXOX', 'none'], ['CX-O-O---X', 7], ['CXXO-O--OX', 4], ['CXXOXO-OOX', 'none'], ['CO-X-X-O--', 4], ['COXXXXOO-O', 8], ['CO-OXX----', 6], ['CO-OXXO--X', 8], ['CO---OX--X', 3], ['CO-O-OXX-X', 8], ['CX---OX--O', 7], ['CX-O-OX-XO', 7], ['CXOOXOX-XO', 7], ['COX-OXO--X', 8], ['COXXOXO-OX', 7], ['C--O-OX-X-', 7], ['C--XOXO---', 7], ['C-XXOXO--O', 8], ['C-XO--XO--', 5], ['COXO-XXO--', 8], ['COXO-XXOOX', 4], ['C-O-O-XX--', 9], ['COOX--OXX-', 9], ['C---XO-OX-', 3], ['CX-O-OXO-X', 'none'], ['C--X---XOO', 5], ['C----OOXX-', 9], ['C-X-XOOX-O', 1], ['COXXXOOX-O', 'none'], ['C--XOOX---', 9], ['C-O-O-X--X', 3], ['COO-O-XX-X', 8], ['COX-O---X-', 5], ['COX-OO-XX-', 9], ['COX-OOXXXO', 'none'], ['CO---OXXOX', 3], ['C--OO---XX', 7], ['C-X-O--OX-', 5], ['C-XOO--OXX', 5], ['C-XOOOXOXX', 'none'], ['C-X-O---XO', 5], ['CO---OXOXX', 3], ['C---XOX-O-', 2], ['C--OXOX-OX', 7], ['C--OX-XO--', 5], ['CO-OX-XOX-', 5], ['COOOX-XOXX', 'none'], ['CX----O-XO', 3], ['CX-XO-O-XO', 5], ['CXXO----O-', 9], ['C-OX-O--X-', 9], ['C--OOXX---', 1], ['CX-OOXX-O-', 9], ['CXXOOXX-OO', 7], ['C-OX-X---O', 7], ['C-OX-X-OXO', 6], ['C-OXXXOOXO', 1], ['CO-X---XO-', 5], ['CO-X---OX-', 4], ['CO-XXO-OX-', 6], ['CO-XXOXOXO', 'none'], ['CXX--OO---', 3], ['CXX--OO-OX', 4], ['COOXXOO-XX', 7], ['COXO--X-OX', 5], ['CXOO--O-XX', 7], ['CXO-X-OOX-', 9], ['CXOXX-OOXO', 5], ['C-X--OX--O', 1], ['COXX-OX--O', 'none'], ['C--XX-OO--', 2], ['C--XXOOOX-', 1], ['CXOXXOOOX-', 9], ['CX-O--O-X-', 9], ['CX-OXOO-X-', 7], ['C---OXO-X-', 2], ['C---OXOOXX', 2], ['C--OX-XOOX', 5], ['COX-X--OOX', 6], ['COXXXO-OOX', 6], ['CX--OXO---', 9], ['CX--OXOXO-', 9], ['C--XO--X-O', 5], ['CO-XO--XXO', 5], ['CO-XOOXXXO', 'none'], ['C-O-O--X-X', 8], ['C-O-OOXX-X', 8], ['C-XO-XXOO-', 9], ['C-O---XOX-', 4], ['C-OO-XXOX-', 4], ['C-OOOXXOXX', 1], ['COXOX-O--X', 8], ['COXOXXO-OX', 7], ['COX--O--X-', 9], ['COX--O-XXO', 'none'], ['C-OXO-X---', 9], ['CO--XX-O--', 6], ['COO-XX-OX-', 6], ['COOXXX-OXO', 6], ['C--OOXOX-X', 8], ['C--X--OX-O', 5], ['CXX-XOXOOO', 'none'], ['C-O-X---XO', 1], ['C-OXXO--XO', 1], ['CXOXXOO-XO', 7], ['CXO-XO----', 7], ['CXO-XO-O-X', 8], ['COXX-O----', 9], ['COXX-O--XO', 'none'], ['CO-XOXXO--', 'none'], ['C-OOO-XX-X', 8], ['COOOOXXX-X', 'none'], ['CX-OXO--XO', 7], ['C-O---OX-X', 8], ['C-O-XOOX-X', 8], ['CX-OX---O-', 7], ['CXXOX---OO', 7], ['CXXOXXO-OO', 'none'], ['CXO-OXXO--', 9], ['COX--OX-XO', 'none'], ['C-XOXOO--X', 7], ['COO-XOXXOX', 'none'], ['CO--O--X-X', 8], ['CO-XOO-X-X', 8], ['CXOX-O----', 8], ['CXOXXOO---', 7], ['C-O-OX---X', 1], ['C---OX-O-X', 1], ['C-OOX-X---', 5], ['CXOOX-X-O-', 7], ['C--XX-O--O', 7], ['CO-XXXO--O', 8], ['C-X---OOX-', 5], ['C-X-X-OOXO', 5], ['CXXOX-OOXO', 'none'], ['CX--OO-X--', 2], ['CX--OO-XOX', 6], ['CXX-OOOXOX', 'none'], ['COOX--X-XO', 5], ['COOXXOX-XO', 'none'], ['C---OXO--X', 7], ['C--XOXOO-X', 1], ['C-OXOXOOXX', 1], ['CXOXO---OX', 6], ['CXOXOO-XOX', 'none'], ['CO---OXXXO', 'none'], ['C--O---OXX', 5], ['C--OO-XOXX', 1], ['CXX--O-O--', 3], ['CXX--O-OOX', 3], ['CXOOX--OX-', 5], ['CXOOXOXOX-', 'none'], ['CO-O--X--X', 5], ['COXO--XO-X', 5], ['COXOX-XOOX', 5], ['CXX---OO--', 3], ['CXX-O-OOX-', 5], ['CO--X---OX', 6], ['CO-OXOXXOX', 2], ['C---XXOO--', 9], ['C---XXOOOX', 1], ['C--O-XXO--', 4], ['C--OOXXOX-', 2], ['CXOOOXXOX-', 9], ['CXOO--XOX-', 5], ['CXOOO-XOXX', 5], ['C-XOO-O-XX', 7], ['CO--XXO-XO', 3], ['C-OX----OX', 6], ['C-OX-XO-OX', 7], ['C-XXO----O', 1], ['C-X-OO---X', 6], ['CXX-OO-O-X', 3], ['C----OXX-O', 1], ['C-X-OOXX-O', 3], ['CXX-OOXXOO', 3], ['CX-OO----X', 5], ['CX-OOO--XX', 7], ['CXXOOOO-XX', 'none'], ['CO-XOX----', 7], ['COOXOX--X-', 7], ['COOOX--XX-', 'none'], ['COX--O---X', 6], ['COX-XO--OX', 6], ['COX-XOXOOX', 3], ['CX-X--O--O', 2], ['CX-X--OOXO', 2], ['CXX-OO----', 3], ['CXXOOO--X-', 9], ['C-OX-O-X--', 9], ['C-OXOO-XX-', 9], ['CXOXOO-XXO', 6], ['COXXOO-XOX', 6], ['CO----XX-O', 5], ['CO--XOXX-O', 'none'], ['C-X---OX-O', 3], ['C-XO-XOX-O', 'none'], ['C-XOXOX-O-', 1], ['C----OXOX-', 3], ['COO-XX-XO-', 6], ['C--OO-X-X-', 2], ['C-OXXXO--O', 7], ['C-XXOOXO--', 9], ['CXXOXOO---', 7], ['C--OX-O--X', 8], ['COXO----X-', 5], ['CO--X--X-O', 5], ['COO-X-XX-O', 5], ['CX-X---O-O', 2], ['CX-XXO-O-O', 2], ['CXOO-OX-X-', 7], ['C--X-XO--O', 7], ['CX-XXXOOOO', 'none'], ['C---O--XOX', 5], ['C-XOO--XOX', 5], ['C-XOOXOXOX', 1], ['CXO-OX-X-O', 3], ['CXXOXXOOO-', 9], ['C-O-XX-XOO', 6], ['COX--XOXO-', 3], ['COXOO-X-X-', 7], ['COXOOOX-XX', 7], ['CX-O--OX--', 4], ['CX-O-XOXO-', 9], ['CO--XXO---', 3], ['CO-OXXOX--', 9], ['CO---O-X-X', 8], ['CXOO-O--XX', 7], ['CX---XO--O', 3], ['CXXO-XO--O', 'none'], ['CO-X--OX--', 5], ['CO-X-OOXX-', 9], ['CO-XXOOXXO', 'none'], ['C-OO--XXOX', 1], ['CO-OOXXOXX', 'none'], ['C-XX-O-O--', 1], ['C---X--OXO', 5], ['C-O-XX-OXO', 6], ['CX----OOX-', 5], ['CXOX--OOX-', 9], ['CXOXO-OOXX', 5], ['C-----XOOX', 3], ['C-O-OX-XXO', 3], ['C--O-X-O-X', 1], ['C-OO-X-OXX', 1], ['C-OOXXOOXX', 1], ['C-X-X--O-O', 8], ['COXXX--O-O', 5], ['C---O--XXO', 5], ['C-OXO--XXO', 5], ['C---XOXXOO', 1], ['CO-XXOXXOO', 'none'], ['CX-X-O-OXO', 2], ['CX-XXOOOXO', 2], ['CO-OXX-O-X', 6], ['COOOXX-OXX', 'none'], ['CXX-O-O---', 3], ['CXXOO-OX--', 9], ['CXXOO-OXXO', 'none'], ['C-O-X--X-O', 1], ['COO-XX-X-O', 6], ['C-XX-O--O-', 1], ['COXX-O--OX', 6], ['COOX-XX-O-', 9], ['CO-O---XX-', 9], ['COXO--OXX-', 9], ['COXOX-OXXO', 'none'], ['COXOXX--O-', 6], ['C-X-XOX-OO', 1], ['C-O-OXOX-X', 8], ['C-OXO-XX-O', 5], ['COX---X-O-', 9], ['COXXO-X-O-', 9], ['C-O-X-XOXO', 5], ['CX---OX-O-', 3], ['CXOX-OX-O-', 'none'], ['C--XXOO---', 1], ['C-XX--O--O', 1], ['C-O-XXOO-X', 1], ['CXX--O--O-', 3], ['C--O---XOX', 1], ['C--OO-XXOX', 1], ['C-OOOXXXOX', 1], ['C----OX-OX', 3], ['C-XO-OX-OX', 7], ['CO-O-X-X--', 2], ['COO--X--X-', 3], ['COOX-X-OX-', 4], ['COOX-XOOXX', 4], ['COXOOX-X--', 8], ['C--OXX--O-', 6], ['CXO-OXX-O-', 9], ['CXO-OXXXOO', 3], ['CXOXO--XO-', 5], ['CXOXOOXXO-', 'none'], ['CO--X-O-X-', 5], ['CO-XX-OOX-', 2], ['CO---O-XX-', 9], ['COO--OXXX-', 9], ['COO-XOXXXO', 'none'], ['C--O-XX--O', 4], ['C-O-O---XX', 7], ['C-OXO--OXX', 6], ['CO-OX--X--', 2], ['COOOXX-X--', 'none'], ['C--XO-OX--', 5], ['C--XOOOX-X', 'none'], ['C-XX-OOXO-', 1], ['C-XXOOOXOX', 'none'], ['C----XXOO-', 4], ['CO---XXOOX', 4], ['CO----XXO-', 3], ['CO-O-XXXO-', 4], ['COXO-XXXOO', 4], ['C-XOXOXOXO', 'none'], ['C-XOXXOO--', 9], ['CO-XOX--XO', 7], ['CX---O-O-X', 3], ['CXOXOO-OXX', 6], ['CO--XX---O', 6], ['COO-XX--XO', 6], ['CO--X-X--O', 5], ['CO--X-XOXO', 5], ['COOXX-XOXO', 5], ['CX-XO----O', 2], ['CX-XO--OXO', 2], ['COX-O--OXX', 'none'], ['C---XO--OX', 2], ['CXXOOOX---', 9], ['CXXOOOXO-X', 'none'], ['C-XXOOOX--', 'none'], ['CO---OXX--', 9], ['COO--OXX-X', 8], ['CX--OX---O', 3], ['CXOXOX---O', 7], ['C-X-X--OO-', 9], ['C-XOXX-OO-', 9], ['COXOXX-OOX', 6], ['C-O-OX-X--', 3], ['CXOOOX-X--', 9], ['CXOOOX-XXO', 6], ['C-XOOXXXOO', 1], ['COO--XOX-X', 8], ['COOOXXOX-X', 'none'], ['C--X-X--OO', 7], ['CX-XOX--OO', 7], ['COXXXO-O--', 9], ['COO-X--X--', 3], ['COOXX--XO-', 5], ['CO--OXX-XO', 7], ['CXX-OOXO--', 3], ['CXOX-OXO--', 9], ['CXOX-OXOXO', 4], ['C-X-XOXO-O', 8], ['CXXOXO--O-', 7], ['CO-X-O---X', 6], ['COOX-O-X-X', 8], ['COOO-XXXOX', 'none'], ['CXOXOXXOO-', 9], ['CX----OXO-', 4], ['CXO---OXOX', 5], ['CO--O---XX', 7], ['C---XXOOXO', 2], ['COXXO-XO--', 'none'], ['CX--O-O-X-', 5], ['C-OXX-XOO-', 9], ['C-O-X---OX', 5], ['COO-X--XOX', 3], ['COOXX-OXOX', 5], ['C--OXOO-XX', 7], ['CX-OXOOOXX', 'none'], ['CXO-----XO', 7], ['CXO-XO--XO', 7], ['CX-OOXX--O', 2], ['C--XOXX-OO', 7], ['C-X-XO---O', 1], ['COXXXO---O', 'none'], ['COXX-O-X-O', 'none'], ['CX-X--OO--', 2], ['CX-X-OOOX-', 2], ['C---OXX-O-', 9], ['C--XOXXOO-', 9], ['C---X--OOX', 5], ['CX--O--XO-', 5], ['CX--O-XXOO', 3], ['CX---XOO--', 9], ['C-OX--OX--', 5], ['CO-XO-XX-O', 5], ['C-OXX--XOO', 5], ['C-OXXOXXOO', 'none'], ['CX-OOXXO--', 9], ['CXXOOXXO-O', 8], ['CX--XOXO-O', 8], ['C-OXOO--XX', 7], ['CO-XOXOOXX', 'none'], ['CO-X-O--X-', 9], ['CO-X-OX-XO', 'none'], ['CX--O---OX', 5], ['C-OO-OX-XX', 7], ['C-OOXOXOXX', 'none'], ['CXOO--X-XO', 4], ['C-X--OX-O-', 9], ['CXX--OX-OO', 7], ['CXXO-OXXOO', 4], ['CXO--X--O-', 9], ['CXOX-XO-O-', 9], ['C----XOXO-', 3], ['CX---XOXOO', 4], ['CXOO-O-X-X', 8], ['C-OXX-O---', 7], ['COOXXXO---', 7], ['C---O-XO-X', 3], ['C-O-O-XOXX', 3], ['CXOX-OOX--', 4], ['CXOX-OOXXO', 4], ['C-X--OOXOX', 1], ['CXXO-OOXOX', 4], ['CXX--O---O', 3], ['CXX-OO-X-O', 3], ['CXXOOO-XXO', 6], ['CXOO----X-', 7], ['C--XOXOOX-', 2], ['C-XX-OOOX-', 1], ['COX--OOXX-', 9], ['CXXOXXOO-O', 'none'], ['CXO-XO--OX', 'none'], ['CO---XO--X', 7], ['CO---XOOXX', 2], ['CXOOXOXO-X', 'none'], ['CX-O--XOXO', 5], ['CXXO-OXOXO', 'none'], ['COOX--X---', 9], ['COOXX-X-O-', 9], ['COOXXOXXO-', 'none'], ['C---O-OX-X', 8], ['CO-XO-OX-X', 8], ['COXXOOOX-X', 'none'], ['C-O--X--XO', 3], ['C-OO-X-XXO', 6], ['C-OOXXOXXO', 'none'], ['C-XXOOOXXO', 'none'], ['COOXX--O-X', 6], ['COOXXX-OOX', 6], ['CX-XO--O--', 2], ['CO-----XXO', 5], ['CO-X-O-XXO', 'none'], ['CO-OOXXXOX', 2], ['CO---XOX--', 3], ['CO-OXXO-X-', 2], ['COOOXXO-XX', 'none'], ['COO--XX---', 4], ['COO--XXX-O', 4], ['C--O-XXOOX', 4], ['CO-XOXX-O-', 9], ['COO---XXOX', 3], ['C-XXOO-OX-', 1], ['COX---OX--', 5], ['C--X-O--XO', 1], ['CX-XOO--XO', 2], ['C-X-O-XOOX', 3], ['CXXOO-X--O', 8], ['CO--OX---X', 7], ['COX-OX--OX', 3], ['COXOOX-XOX', 6], ['C-X-O--X-O', 5], ['COX-XX-O-O', 8], ['COXOXOX---', 9], ['CXO-X--O--', 5], ['COOXX-----', 5], ['COOXXOX---', 9], ['CX-XO-OX-O', 5], ['C-XOO---X-', 5], ['COO--OX-XX', 7], ['C--OOX-XOX', 1], ['CX---O-X-O', 4], ['CXX--O-XOO', 6], ['CXXO--O---', 9], ['CXO---O--X', 5], ['CXOOX-O--X', 8], ['COXOX-OOXX', 5], ['C-O-X-XXOO', 5], ['C---OX--OX', 1], ['CO-XOX--OX', 7], ['C-O-XO---X', 8], ['C-O--X--OX', 3], ['C-O-OXX-OX', 7], ['C--OX-OXXO', 'none'], ['C-XOX-OX-O', 'none'], ['C--XXO-O--', 2], ['CX-XXOOO--', 2], ['CX-XXOOOOX', 2], ['C-X-OX---O', 8], ['CXX-OX--OO', 3], ['CXXOOX-XOO', 6], ['CXOOX-X--O', 8], ['C-XO---OX-', 5], ['C-OOXX--XO', 6], ['CXOOXXO-XO', 'none'], ['CO--OX--X-', 2], ['CO--OX-OXX', 'none'], ['C-XO-O---X', 7], ['CXXOOO-XOX', 6], ['C-XOXO-X-O', 1], ['CXXOOX---O', 8], ['CXO-OXX--O', 3], ['CXOXOXX-OO', 7], ['CO-X--O--X', 7], ['COOX--OX-X', 8], ['C-XOX-XOO-', 5], ['CO--X-O--X', 7], ['COX-X-OO-X', 8], ['CXX-OX-OO-', 9], ['C-XOOX----', 8], ['C---OX-XO-', 3], ['C-X-OXOXO-', 9], ['C---X-OO-X', 1], ['C-X-OO--X-', 6], ['COX-OO--XX', 7], ['COX-XOX-O-', 9], ['C-OX----XO', 5], ['COOX-XXOXO', 4], ['C-X--OOOXX', 4], ['C-XXO-XOO-', 9], ['COXXO--X-O', 5], ['COXXO-XXOO', 5], ['C-OO-OXXX-', 9], ['C--XXXO-OO', 7], ['C-XXXXOOOO', 'none'], ['C-O-OXX---', 3], ['C-X--XO-O-', 3], ['CX-OOO-XX-', 9], ['CX-OOOXXXO', 2], ['C-OOX-XOX-', 5], ['CXOOX-XOXO', 5], ['CX-OOO-X-X', 8], ['C-XXO-O---', 1], ['C-XXO-OO-X', 1], ['COXXOXOO-X', 'none'], ['C----XX-OO', 4], ['CXX-OXXOOO', 'none'], ['C--X--XOO-', 9], ['C-XXOXXOOO', 'none'], ['C-X-O-O--X', 5], ['C-X-OXOO-X', 8], ['COXX--XO-O', 8], ['C-OXOX-O-X', 6], ['C-O-X--O-X', 5], ['C-O-X-XOOX', 5], ['C-X---O-XO', 5], ['CXX-O-O-XO', 5], ['CXX-OOOXXO', 'none'], ['C-O-X-X-O-', 5], ['CXO-X-XOO-', 5], ['C-XO-O-X--', 4], ['C---XXO--O', 3], ['CX-OXXO--O', 'none'], ['CO-----XOX', 3], ['C-X--OOXXO', 4], ['CO-OX-OX-X', 8], ['C--X-XOOXO', 2], ['CO-X-XO---', 7], ['COXX-XO--O', 8], ['C--OOX-X--', 8], ['CO-OOX-X-X', 8], ['COXO-XO--X', 8], ['CX-OOOXX--', 8], ['CXO-O--XXO', 5], ['CO-X-O-XOX', 6], ['COXX-OOXOX', 4], ['CXXOO-OOXX', 5], ['CX-O-O-XXO', 4], ['COOXXOOX-X', 8], ['C--X-O-X-O', 1], ['C-OX--XOXO', 4], ['C-OXOXXOXO', 1], ['COXOX-----', 5], ['COXOXO---X', 7], ['COXOXOOX-X', 8], ['CX--X-OO--', 9], ['CXX-X-OOO-', 9], ['CXX-XXOOOO', 'none'], ['COOXO---XX', 7], ['COOXOXO-XX', 7], ['COX-XOXO--', 9], ['CO-XXOOOXX', 2], ['CX-XX--OOO', 'none'], ['CXXOX--OO-', 9], ['COX-X-XOO-', 9], ['C--O--XOX-', 5], ['CX-OO-XOX-', 5], ['CXO-XX-OO-', 9], ['COXX-XOO--', 8], ['CO---XOXXO', 3], ['CX----OO-X', 5], ['CXX--OOO-X', 3], ['CXOX--X-OO', 5], ['CXO---XOXO', 5], ['C-X--O-XO-', 1], ['CXX--OOXO-', 4], ['CXO---X-O-', 5], ['CXO-XOX-O-', 'none'], ['C-X-OX--O-', 3], ['C--XO-OXXO', 5], ['COX-O--X--', 5], ['COX-OOXX--', 9], ['CXXO---O--', 5], ['CXXOO-XOOX', 5], ['CO-XOOX-X-', 9], ['COXXOOX-XO', 'none'], ['C-OXXO-OX-', 6], ['CX-XO-O-OX', 5], ['CX-XOOOXOX', 'none'], ['CX-O--X-O-', 5], ['CXX---O--O', 3], ['CXX-X-O-OO', 7], ['CXX--OXO-O', 3], ['COO-XXOX--', 3], ['COO-XXOXXO', 3], ['C--O--OXX-', 9], ['C--OOXOXX-', 9], ['C-XO-X--O-', 9], ['C-X-OXX-OO', 7], ['COOOXX-XOX', 'none'], ['C--OXO-OXX', 'none'], ['CX--OX-OXO', 2], ['CO-X-XXOO-', 9], ['CXOO-X----', 9], ['CXOOOXXX-O', 8], ['CO-OOXXX--', 2], ['C-O-OX--X-', 7], ['C-OOOXX-X-', 9], ['COOX---X--', 5], ['COOX---XXO', 5], ['CXX----O-O', 3], ['CXX-O--OXO', 6], ['CO-OXX--XO', 6], ['COOOXX-XXO', 'none'], ['CXO--XX-OO', 7], ['CXOX-XXOOO', 'none'], ['C-XOO----X', 5], ['COXOO---XX', 7], ['C-OX---OX-', 9], ['CO-X-X---O', 7], ['C-O-XXO-OX', 7], ['CX-O---XO-', 4], ['CXXOO--XO-', 5], ['C-X--X-OO-', 9], ['COX-XX-OO-', 6], ['C-OXXOXOXO', 1], ['CO--X---XO', 5], ['CO-OX-X-XO', 5], ['C-O--X-OX-', 1], ['C-O--XXOXO', 4], ['C-XXOOO-X-', 'none'], ['C--X--O-OX', 5], ['CO-X-XO-OX', 7], ['CO-XXXOOOX', 2], ['CX--XXO-OO', 7], ['CO---X-O-X', 4], ['COO--X-OXX', 6], ['COOO-XXOXX', 'none'], ['C-XOOX-O-X', 8], ['CXOOXO--X-', 7], ['C--X-OX--O', 2], ['CO---XXO--', 4], ['COO--XXOX-', 4], ['C-OXO--XOX', 6], ['CXO-X-XO-O', 5], ['C-O-OXXOX-', 9], ['C-XX-X-OOO', 'none'], ['C-XX---O-O', 1], ['C-XX--XOOO', 'none'], ['CX---O--XO', 4], ['C-X-OXO-OX', 7], ['CO-XXOO--X', 8], ['CO--XX--O-', 6], ['C-OOXX----', 6], ['COOOXX---X', 'none'], ['C-O-XX-O--', 6], ['COO--X---X', 3], ['COO-OX-X-X', 8], ['CX-O---O-X', 5], ['CXOO--XO-X', 5], ['COOXX---XO', 5], ['CXO-X--OOX', 5], ['C-OO-XX-OX', 4], ['CO-XO-O-XX', 7], ['C-XOX-O-XO', 'none'], ['CO-XXO--OX', 6], ['COO-----XX', 7], ['COO-X-O-XX', 7], ['C-XX-O---O', 1], ['COXXXO-XOO', 'none'], ['CXOOXOX---', 7], ['C--O-XX-O-', 4], ['CX-O-XXOO-', 9], ['C---X-XOO-', 5], ['CX-O---X-O', 4], ['CX-O--OXXO', 'none'], ['CO-O-XX-OX', 4], ['C-XOOXXO--', 8], ['C-XO-O-XXO', 6], ['C---XOOX--', 1], ['C---X-OXO-', 1], ['C--OXXOXO-', 1], ['C--XOXO-OX', 7], ['COX-OXX-O-', 3], ['C--O--XXO-', 4], ['C--OXOXXO-', 1], ['C-XOXOXXOO', 1], ['CXO--O--X-', 7], ['CO-OX---X-', 2], ['C-XO--OOXX', 5], ['CXXO-OOOXX', 'none'], ['C--XX-OOXO', 2], ['C-X-XOO-OX', 1], ['C-OOXOXX--', 1], ['CX---XO-O-', 9], ['CXX--XO-OO', 3], ['CXXOXO-O--', 'none'], ['CO--XXOO-X', 8], ['CXOXX-OO--', 9], ['COX-XO----', 7], ['COXOXO--X-', 7], ['COXOXOOXX-', 9], ['CXO--O-OXX', 6], ['C-O--XO-X-', 7], ['C-OX-XOOX-', 9], ['C--X-O--OX', 6], ['CX-XOO--OX', 6], ['COXOXOO-XX', 7], ['COO--XX-XO', 4], ['COOO-XXXXO', 'none'], ['CO-XX-OX-O', 5], ['CXOX--XO-O', 8], ['CX-OOOX--X', 7], ['C-OXOXX-O-', 9], ['COXO---XXO', 5], ['COXOO-XXXO', 5], ['CXX-XOO-O-', 9], ['COO--X-X--', 3], ['C-OXXOXO--', 9], ['CX-OX-O---', 7], ['CXXOXOOOX-', 'none'], ['C-OX-XO---', 7], ['C-OXOXO-X-', 9], ['CXOXOXO-XO', 7], ['C-O-OX-XOX', 6], ['COX--O-XOX', 3], ['COXO-OXXOX', 4], ['CX-OXOX-O-', 7], ['COX-X--O--', 5], ['C-OX--O-X-', 7], ['CXOXO-O-X-', 5], ['C-XOX-OXO-', 1], ['C--O-XOX--', 9], ['C-XX---OO-', 1], ['C-XXOX-OO-', 1], ['CO--XO-X--', 8], ['COX-XO-X-O', 'none'], ['COXX-----O', 5], ['COXX-OXOXO', 'none'], ['CO---XX--O', 4], ['COX--XXO-O', 8], ['COO-XXO-X-', 3], ['COXX-OX-O-', 9], ['COXXXOXOO-', 9], ['C---OXOX--', 9], ['CX-OOXOX--', 9], ['CO-OX-XO-X', 5], ['COOXXOOXX-', 9], ['C---XOXOOX', 3], ['CX-OXOXOOX', 'none'], ['C-OXXO-XO-', 'none'], ['CX--X-O--O', 7], ['CX--XXOO-O', 8], ['C--XOX--O-', 7], ['C--XOX-OOX', 6], ['COX-XO-XO-', 9], ['C----OX-XO', 1], ['C-X-OOX-XO', 3], ['COX-----OX', 6], ['COXO---XOX', 6], ['C-X-XOOOX-', 3], ['C--X---OOX', 6], ['C-XX-O-OOX', 6], ['C--X-XOO--', 1], ['C--XO--XO-', 5], ['COOO-XX-X-', 'none'], ['C---O-XOX-', 1], ['C-O-X-XO--', 5], ['COOOXOX-XX', 'none'], ['C---OO--XX', 7], ['CXXO-XO-O-', 9], ['CXXOOXOXO-', 9], ['CXOX-O-X-O', 4], ['CX-O--OOXX', 5], ['CXOX-X-OO-', 9], ['CX-X----OO', 2], ['C-O-XOO-XX', 7], ['C----XO-OX', 1], ['C-XO-XO-OX', 1], ['COX---XO--', 4], ['C---X--XOO', 1], ['C--OX-XXOO', 5], ['C-O-OXO-XX', 7], ['C-XXO-OOX-', 5], ['CXOO---XXO', 4], ['C-X-OX-O--', 8], ['C--XO-XOXO', 2], ['C----O-XXO', 4], ['CX---OOXXO', 4], ['CXX--XOO-O', 8], ['C-OOXOX--X', 8], ['COXXXO-OXO', 'none'], ['C-OXXO--OX', 'none'], ['C--OXOX-XO', 1], ['CX-OXOXOXO', 'none'], ['C--X-XXOOO', 'none'], ['CX-OXOO--X', 7], ['C-O---X-OX', 3], ['CXO-X-OO-X', 5], ['COOXXOXOX-', 9], ['CO---X-X-O', 3], ['COO--X-XXO', 3], ['CX--O---XO', 2], ['C-O-XO-OXX', 6], ['COXO---X--', 8], ['COXOXO-X--', 8], ['C-O-XXOX-O', 3], ['CXOX-XOO--', 9], ['C-X--X-O-O', 8], ['COO-X---X-', 3], ['COOOX-X-X-', 'none'], ['C-O--O-X-X', 8], ['CXO--OOX-X', 8], ['C-O-O-X-X-', 9], ['C-OXOOX-X-', 9], ['CXOXOOXOX-', 9], ['CXOO-XX-O-', 9], ['CX--XOO---', 7], ['CXO-XOO--X', 7], ['C-OX-X--O-', 9], ['COOX-X--OX', 7], ['CO-XXOOX--', 8], ['COXXXOOXO-', 9], ['C-O-XOX-XO', 1], ['C-OOXOXXXO', 1], ['C-X---X-OO', 7], ['C-X--OXXOO', 1], ['COX-XOXXOO', 'none'], ['CO-X-OXXO-', 9], ['CXO---OX--', 4], ['COOXX-OOXX', 5], ['C-XO---O-X', 5], ['C-XXOO-X-O', 1], ['CX--X---OO', 7], ['CXX-X--OOO', 'none'], ['C-X--O--OX', 3], ['C-XO-O-XOX', 1], ['C-XX-XOO-O', 8], ['C-X-OXOX-O', 8], ['COX-X-O---', 8], ['COX-X-OXO-', 5], ['C---OOX--X', 3], ['C--OOOX-XX', 7], ['CXOOOOX-XX', 7], ['CXO--OXOX-', 9], ['CO-X-X-OXO', 4], ['COXOX-X--O', 5], ['C-O--O--XX', 7], ['C-OX-O-OXX', 6], ['CO--OXO-XX', 7], ['COX--O-X--', 9], ['CO-XXX-OO-', 6], ['C-XOOOX--X', 8], ['CXO-O-XX-O', 3], ['COX-X---O-', 6], ['CX-XX-OO-O', 2], ['CO-OX--XXO', 6], ['COXOXO-XXO', 'none'], ['CO-X-O-X--', 9], ['CO-XX-O-OX', 7], ['CXXO-O-O-X', 'none'], ['C-XXXOO-O-', 1], ['COXXXOO-OX', 7], ['C-O-OXXXO-', 9], ['CXOOOXXXO-', 9], ['COO-XO-XX-', 9], ['C---OXXXOO', 3], ['CO-O---X-X', 8], ['CO--O-XXOX', 3], ['C-X-X---OO', 7], ['C-XOX--XOO', 6], ['COXOX-XXOO', 5], ['CO-XO---X-', 7], ['COXXOO--X-', 9], ['C--X-O-XO-', 2], ['C--XOO-XOX', 6], ['COXXOOXOX-', 'none'], ['COXX-X-OO-', 9], ['COXXOXXOO-', 'none'], ['C-XXOOXOXO', 1], ['C-XOO-XOX-', 5], ['C-XXO-OXO-', 5], ['C---OXXOOX', 3], ['C-X-OO-OXX', 6], ['C-XOXXO--O', 'none'], ['CXXOO---XO', 5], ['C--OX--X-O', 1], ['CX-O-X--O-', 9], ['C--XXOXO-O', 8], ['C-XXXOXOOO', 'none'], ['CO--XOXOX-', 3], ['C-XXO-X-OO', 7], ['C-XXOOXXOO', 1], ['COXXOX--O-', 7], ['COO-X--XXO', 5], ['COOXXO-XXO', 'none'], ['CXOXXO-OXO', 6], ['CO-X-XXO-O', 4], ['COXX-XXOOO', 'none'], ['CX-X-OO---', 2], ['CX-X-OO-OX', 2], ['CO-XO-X---', 9], ['CO-XO-XOX-', 'none'], ['C-OXX-O-XO', 7], ['COOXX-OXXO', 5], ['CXX--OOOX-', 3], ['CXOX-O-OX-', 6], ['CO-X-OXX-O', 'none'], ['C-X---XO-O', 8], ['C----XO-XO', 2], ['COOXXX-O--', 6], ['COOXXXOOX-', 9], ['CO--OOXXX-', 9], ['C-O-XXO-XO', 7], ['CX-X-XO-OO', 7], ['COXO--X-XO', 5], ['CXOX-----O', 7], ['CXOXO-X--O', 5], ['C-XOO-OX-X', 8], ['CX-X-OOO-X', 2], ['CO-OX----X', 2], ['COOOX---XX', 'none'], ['CX-X-OXOO-', 9], ['CXOXXOXOO-', 'none'], ['CXX-OOX--O', 3], ['CXX-XO-O-O', 3], ['CX--XO-O--', 3], ['CXX-XOOO--', 3], ['C-XXX-OOO-', 1], ['C-O--OX--X', 3], ['COO-XOXOXX', 3], ['C-OO----XX', 7], ['COOO-X--XX', 'none'], ['C-OOX---X-', 1], ['COOOXX--X-', 'none'], ['COX--X-OOX', 4], ['CO-X--XXOO', 5], ['C--XO---XO', 5], ['C--XOOX-XO', 2], ['C-----OXXO', 3], ['C---OXOXXO', 3], ['COXXO-OX--', 5], ['COXXOOOXX-', 'none'], ['COXO-----X', 8], ['COXO-OX--X', 8], ['COOXX-O-X-', 7], ['C-O-XOX---', 1], ['COO-XOXX--', 9], ['C-OX-OXOX-', 9], ['COO-XXOXOX', 3], ['COXXO-X--O', 5], ['C-XO-OX---', 7], ['CO--XO---X', 8], ['CO-OOXX--X', 8], ['CO-X--XOXO', 5], ['COOX-----X', 6], ['COOX-X-O-X', 6], ['CXXO-OO--X', 7], ['CX--O-X-O-', 3], ['CX--OOXXO-', 2], ['COX----XO-', 3], ['COXX---XOO', 5], ['C-X-OOX-OX', 3], ['CXXOOOX-OX', 7], ['CX-O--O--X', 5], ['C-XOOXXOOX', 1], ['CX-O---OX-', 5], ['CX-OXO-OX-', 'none'], ['CX-OXX--OO', 7], ['CX--XO-OOX', 2], ['C-XO-X-XOO', 6], ['CO--OOXX-X', 8], ['C--XOO-X--', 6], ['C----OXXO-', 2], ['CO--XOXXO-', 9], ['C--OX-O-X-', 9], ['C--XXX-OOO', 'none'], ['COX-OOX-X-', 7], ['C--O--O-XX', 7], ['CX-OO-O-XX', 7], ['CO-X--O-X-', 7], ['CO-XOXO--X', 7], ['CO-X-X--O-', 7], ['CXXO-O----', 7], ['COXX--O---', 5], ['COXX-XO-O-', 7], ['C-XOOO--XX', 7], ['CO-OX-O-XX', 7], ['CO--O-XX--', 3], ['COX-O-XX-O', 5], ['CO-OXOXXXO', 'none'], ['C-OXXOX--O', 8], ['C-XO--O-X-', 5], ['COXOX-O-X-', 9], ['C--OX-OXOX', 1], ['CXO-OXO-X-', 9], ['COX--XXOO-', 4], ['C--XX-OOOX', 1], ['C-OXXOOXXO', 1], ['C-XOOXO--X', 8], ['COXOOXOX-X', 8], ['C-XO-OO-XX', 7], ['COO-XX----', 6], ['C-OXOOXX--', 9], ['CO-X-OOX-X', 8], ['COX-X-O-XO', 5], ['COXXXOO-XO', 'none'], ['COXXX-OOOX', 5], ['CXO-XXO--O', 7], ['CO-XXO-XO-', 9], ['CXXO--X-OO', 7], ['CXXO-XXOOO', 'none'], ['CO-OXO--XX', 7], ['CO--OX-XXO', 6], ['CO-OOXXXXO', 2], ['C-XXXO-O-O', 1], ['C-XXXOOOXO', 1], ['COX-XO-OX-', 9], ['C-X-O-X--O', 5], ['COXXXOO---', 9], ['C-OXOXX--O', 7], ['C-XO---X-O', 6], ['CXXO---XOO', 4], ['C--XX-XOOO', 'none'], ['C--OOOXX-X', 8], ['C-XX-OO---', 1], ['C-XX-OO-OX', 1], ['C--XOO-OXX', 6], ['C-OOO-X-XX', 7], ['COXX-OXXOO', 'none'], ['CX--XOO-XO', 7], ['C-O--XOX--', 3], ['CX---OXOXO', 3], ['C-O---XX-O', 5], ['CXXO---OXO', 5], ['C--OO-XXXO', 5], ['C-XOOOXXXO', 1], ['C-O----OXX', 1], ['COOXX--X-O', 5], ['CX-O----OX', 5], ['CX-OO--XOX', 5], ['C--XO-OOXX', 5], ['C-XXOOOOXX', 'none'], ['C-XXO-XO-O', 1], ['C-O-X-OXXO', 3], ['CX---O--OX', 2], ['CX-XXOO-O-', 7], ['C---X-O-OX', 1], ['CO--XXO-OX', 7], ['C-XX-OX-OO', 1], ['COOXXO--X-', 9], ['CXO---XXOO', 5], ['COXO-X-XO-', 6], ['C--X--OO-X', 1], ['C-XOO-OXX-', 9], ['COOX--XOX-', 9], ['CXX----OO-', 3], ['CXX--O-OXO', 3], ['COXXO-OXOX', 5], ['COX-O-O-XX', 7], ['COXXOOO-XX', 'none'], ['C--XOO-XXO', 6], ['COX-O-XXO-', 3], ['CO-O-XOX-X', 8], ['COXO-O-X-X', 8], ['C-OOXX--OX', 6], ['CXOO--OXX-', 9], ['C-X-XOOO-X', 3], ['COX--OXO-X', 3], ['C--XXO-XOO', 1], ['CO--XO--X-', 9], ['CO--XOOXX-', 9], ['C-XO-O-OXX', 'none'], ['CO-O----XX', 7], ['CO-O--XXXO', 2], ['CO-OX--OXX', 2], ['COOX-O-XX-', 9], ['COOX---XOX', 6], ['C--OOXXXO-', 1], ['CO-X-XOO-X', 8], ['CXX-OOX-O-', 3], ['CXO--XO-XO', 7], ['CXO-O--OXX', 6], ['C-X--XOO--', 8], ['C-XOOXOX--', 9], ['C-OXO---X-', 9], ['COO---XX--', 3], ['COOO--XXX-', 'none'], ['CO-XXXOO--', 2], ['CO--O-X-X-', 7], ['COO-OXX-X-', 7], ['COOXOXXOX-', 'none'], ['C--OOXX-OX', 1], ['CO----OX-X', 8], ['CO--XOOX-X', 8], ['C-X-O--XO-', 3], ['C-X-O-XXOO', 3], ['CX-OOX----', 9], ['CX-OOX-X-O', 8], ['COO--XXXO-', 4], ['COOXOXX---', 9], ['CO-OO-XXX-', 9], ['COOOOXXXX-', 'none'], ['CX-OO--OXX', 5], ['COXO-OXOXX', 'none'], ['C-X-OO-XXO', 6], ['COXXOO-XXO', 'none'], ['C---XO--XO', 1], ['C--XXO-OXO', 2], ['C---XX-O-O', 6], ['CX----XO-O', 8], ['CXX-O-XO-O', 8], ['C----XOX-O', 3], ['CXXO-X-OO-', 9], ['COX-X----O', 5], ['COXOXX---O', 8], ['COXOXXOX-O', 'none'], ['CXXOXO---O', 7], ['CO---X--OX', 3], ['CO--OX-XOX', 3], ['COO-OXXX--', 3], ['CXO--OX---', 7], ['C--O-OXXXO', 1], ['CX-O-X-XOO', 4], ['CXOO-XXXOO', 4], ['C----X-XOO', 3], ['CXO--X-XOO', 6], ['CO-O-XXOX-', 4], ['COXO-X----', 8], ['COXO-X-O-X', 8], ['C--O-O-XX-', 9], ['CX-XOO----', 2], ['CXOXOO---X', 6], ['CO-O-XXO-X', 4], ['COXO--XOX-', 5], ['CX--X-XOOO', 'none'], ['C-XOO-X-XO', 5], ['COX--X-XOO', 6], ['CXXOOOOXX-', 'none'], ['C---OXXO--', 1], ['CX--O-XO--', 9], ['CXOXO-XO--', 9], ['C-OXXXOO--', 9], ['C--O-XOOXX', 4], ['C-XXXOO--O', 1], ['CXO--XOOX-', 9], ['CO--OXOXX-', 9], ['C-O---XO-X', 3], ['C-XO-XOXO-', 1], ['C-OXX--OOX', 6], ['C-OXOX--OX', 7], ['CXXO-OX-O-', 7], ['CXXOOOXXO-', 9], ['C--O-OXOXX', 'none'], ['C-XO----XO', 5], ['C-XOO--XXO', 5], ['COO-X-X-XO', 5], ['C-OX-OOXX-', 9], ['CXOOOX--X-', 9], ['CO-XO----X', 6], ['CO-XOX-O-X', 'none'], ['CO-X--XO--', 9], ['CO-XXOOXOX', 2], ['CX---OXOOX', 3], ['C-XXO-OX-O', 5], ['C-XXOX-O-O', 8], ['CX--OXXOO-', 9], ['CO--X--XO-', 5], ['CO----XOX-', 4], ['C-OO--XX--', 1], ['C-OO-XXXO-', 4], ['C---XOOXXO', 1], ['C--OO--X-X', 8], ['C-O--X-O-X', 1], ['COOX--O-XX', 7], ['C-OXX-XO-O', 5], ['CXX-OXO-O-', 9], ['COX-XO--XO', 'none'], ['COXOXOX-XO', 'none'], ['CX--X-OOOX', 5], ['CXO-X-O---', 7], ['CX-X--OOOX', 5], ['CXOX-XOOXO', 4], ['C-XXOO-O-X', 6], ['CX-O--XXOO', 4], ['COXXO-O--X', 7], ['C-X--XOXOO', 3], ['CX-XOOX--O', 2], ['C-XX-OOO-X', 1], ['C-O--XXXOO', 4], ['C--XO-X--O', 7], ['CX-OO-XX-O', 8], ['C-O--OX-X-', 9], ['C-OX-OX-XO', 7], ['CX-OX-X-OO', 7], ['CXXOX-XOOO', 'none'], ['COXO--XX-O', 5], ['COX---O-X-', 5], ['CX-XO-OXO-', 5], ['CXO--XO---', 9], ['C--OOX--X-', 2], ['COXOXXO---', 8], ['C-----OOXX', 5], ['C--OXOOXX-', 9], ['C-XOO-XO-X', 5], ['CXXOO-X-O-', 9], ['CO-XX---O-', 6], ['COXXXO--O-', 6], ['C-----OXOX', 5], ['C-X-O-OXOX', 5], ['C-O-XOXOX-', 9], ['C--XX--OO-', 9], ['CO-XX--OOX', 6], ['COXXXXO-OO', 7], ['COO-X-XXO-', 5], ['C-OX--OXOX', 5], ['COX--X---O', 8], ['CO-XX-O---', 5], ['COX-XXO--O', 8], ['COXXX-O-O-', 5], ['C-OOX-OXX-', 9], ['CO-OO-X-XX', 7], ['C---XOXOXO', 3], ['C-X-OX-XOO', 3], ['CX-X--OXOO', 5], ['CX-X-O--O-', 2], ['C-XOX-OO-X', 5], ['CX--O-X--O', 3], ['CXXOOOX-XO', 7], ['COOXX--OX-', 6], ['COOOXOXX-X', 'none'], ['CX--X-O-O-', 7], ['CXO-XXO-O-', 9], ['CO-OXX-OX-', 6], ['C-XXXO-OO-', 9], ['COOXXOXX-O', 'none'], ['COOOX-XX--', 'none'], ['C-OOX--OXX', 1], ['CXOXOO--X-', 9], ['CO-XOX-OX-', 'none'], ['CX--OOX-XO', 3], ['C-XOXO-OX-', 'none'], ['C-OX-O-XOX', 'none'], ['CO-XX-O-XO', 5], ['CXX--OO-XO', 3], ['CO-OOX-XX-', 9], ['CXOO-XO-X-', 9], ['CXOOXXOOX-', 9], ['CXOXX---OO', 7], ['CXOXXOX-OO', 'none'], ['COX-X-O-OX', 7], ['CO-XX--O--', 6], ['COOXX-XO--', 9], ['COXX-O-OX-', 9], ['COXOOOXX-X', 8], ['CO-OXO-X-X', 8], ['CO--XXOOX-', 2], ['CXO-XOX--O', 7], ['CXXOO-O--X', 5], ['CXO-X-O-OX', 7], ['CO--O-XOXX', 'none'], ['CXOX---OXO', 6], ['CO--XO-OXX', 3], ['COX--XOX-O', 8], ['CXOO---XOX', 5], ['C--XO-OXOX', 5], ['CX-OOXO-X-', 9], ['C-OOOXXX--', 1], ['C----XOO-X', 1], ['COX---XXOO', 5], ['COX--XO-OX', 7], ['CX-O-OXX-O', 4], ['CO-XXO----', 9], ['C--OXXOX-O', 'none'], ['COX-OOX--X', 7], ['CXO-OO-XX-', 9], ['CX-O-XO---', 9], ['CX-O-XOX-O', 'none'], ['C-X-XX-OOO', 'none'], ['COOX-O--XX', 7], ['C--XXOX-OO', 7], ['C---OOXX--', 9], ['CO-X---O-X', 6], ['C-OX-XXO-O', 4], ['C-X-OXXO-O', 8], ['C-XOOX-XO-', 9], ['COX--OOX-X', 8], ['CO--X-OXXO', 5], ['CX--XOOO-X', 3], ['CXOX-O-XO-', 'none'], ['CXOO-XOX--', 9], ['COXXO-O-X-', 5], ['COX-X--OXO', 5], ['CX-X-OOX-O', 4], ['C--OXX-OXO', 6], ['COXX-OXO--', 9], ['C-O-OXOXX-', 9], ['CO-OO-XX-X', 8], ['CXXO-XOXOO', 'none'], ['CXOX--O-XO', 7], ['CXOXO-OXXO', 5], ['COOXO--XX-', 9], ['C--XO--O-X', 6], ['CXOXO--O-X', 8], ['CX--OOXO-X', 3], ['C-OXOX----', 7], ['COXOX-OX--', 9], ['CXX-O--OOX', 6], ['CXOX----O-', 5], ['CXOX--OXO-', 5], ['C--O-OX--X', 7], ['C-XOX---O-', 6], ['CO--X-OOXX', 5], ['CXXO--OXO-', 9], ['CX---X-OO-', 9], ['CXO--XXOO-', 9], ['C-XX--OOOX', 1], ['C-XXOX--OO', 7], ['C-XX-XO-OO', 7], ['CXXOOXXOO-', 9], ['CX-XO-XO-O', 2], ['CXOXO-XOXO', 5], ['CXOOX-XO--', 5], ['C--X-OOXXO', 1], ['CXXO--XOO-', 9], ['CX---OO--X', 7], ['COOOX-X--X', 'none'], ['C-XOXX-O-O', 8], ['CX-O-XX-OO', 4], ['CX-OO--XXO', 6], ['CXO-OOXXOX', 'none'], ['C-OOXX-O-X', 6], ['COO-XOX--X', 3], ['C-XX--OXOO', 5], ['C-XO-OXO-X', 'none'], ['CO-OXX-XO-', 6], ['CX--OX-XOO', 3], ['COO---X-X-', 3], ['COO-O-XXX-', 9], ['COOXOOXXX-', 9], ['C-O-OXXO-X', 3], ['CXXO-OOX--', 4], ['COO-OX-XX-', 9], ['CO--XXOX-O', 3], ['CX-OXXOO--', 9], ['CO-X-X-OOX', 6], ['CXO--OX-XO', 4], ['C-XO--OXOX', 1], ['C-XOXOO-X-', 9], ['CO-OXOXOXX', 'none'], ['CXXOO-XOXO', 5], ['CXOX-OOXOX', 'none'], ['CO---X-OX-', 2], ['C-OOXOX-X-', 1], ['C-OXXOO-X-', 7], ['CO-X--OXOX', 5], ['CO--OXOX-X', 8], ['CXOO-X-OX-', 9], ['C-X----XOO', 3], ['CX-XO--OOX', 6], ['C-OX--OOXX', 1], ['CO-O-OX-XX', 7], ['COXOX---OX', 6], ['CX--XOXOO-', 9], ['COX-O--XXO', 5], ['COX-OXXXOO', 3], ['CX-X-O-XOO', 4], ['CX-X-OO-XO', 4], ['C-XO-OOXX-', 9], ['COOX-OXX--', 9], ['C----OOX-X', 8], ['COX--XX-OO', 7], ['CXOO-XX--O', 4], ['COXOX-OXOX', 5], ['COXX-OO-X-', 9], ['COXX-OOX--', 9], ['CXO-XXOO--', 9], ['C-OX-OXX-O', 8], ['CO-OX-XXO-', 5], ['C-X--OXOOX', 3], ['C-OOX-OX-X', 8], ['CO-O-XOXX-', 9], ['C-X----OXO', 5], ['C-XX-O-OXO', 1], ['CO-O-OXXX-', 9], ['COOXOX-OXX', 'none'], ['COXOX--O-X', 5], ['CX--XX-OOO', 'none'], ['CXO---OXXO', 4], ['C-OXO-OX-X', 8], ['CXO-O-O-XX', 7], ['C-XO--XOOX', 5], ['COX-O-XO-X', 'none'], ['C-O-X-O-X-', 7], ['CO-OX--XOX', 6], ['C-OX-OX---', 9], ['C-O--XOOXX', 1], ['C---OX-X-O', 3], ['CXOOO--X-X', 8], ['CX-XX-O-OO', 7], ['CO--XOX-OX', 3], ['COX-OXOX--', 9], ['C--XX---OO', 7], ['CXX-OX-O-O', 8], ['CXOOXX-O--', 9], ['C---X-OOX-', 2], ['C--OOXXO-X', 1], ['CXX-O-X-OO', 3], ['C-OOXO--XX', 7], ['CO-XX-XOO-', 9], ['C-OX-XO-XO', 7], ['C---XOOXOX', 1], ['C--XX--O-O', 8], ['CX-OX-OOX-', 5], ['CXX---XOOO', 'none'], ['CX-X-XOOO-', 9], ['CX-XOOX-O-', 9], ['C-XOXO--OX', 1], ['CXX-O---O-', 3], ['CXX-OO-XO-', 3], ['C-X--O-X-O', 1], ['CXOXO---XO', 5], ['CX-O-OX-OX', 7], ['CO-O-X-XXO', 2], ['CO-X-XOOX-', 2], ['C-XO-OXOX-', 'none'], ['C-X--OO--X', 4], ['C-O--OXX--', 8], ['C-O--XOXXO', 3], ['CXOO-XOXXO', 'none'], ['COOX---OXX', 6], ['CXX--XOOO-', 9], ['CXXOOOOX-X', 'none'], ['C-OXXX--OO', 7], ['CXXOXOXOO-', 'none'], ['CXX-XOO--O', 7], ['CXXO--O-XO', 'none'], ['C-X-OOOX-X', 'none'], ['CXOO-X--XO', 4], ['COO--X-XOX', 3], ['C----XOOX-', 2], ['C-O-XXOOX-', 1], ['COXXX--OO-', 6], ['CO-X-OXOX-', 9], ['CXX-OXOO--', 9], ['CX-OXOX--O', 7], ['C-OO-OXX-X', 8], ['C---O-OXX-', 9], ['CXO-O-X-OX', 5], ['C--OOXO-XX', 7], ['CX--X-OOXO', 2], ['CXXOOO-X--', 9], ['CO-O--X-X-', 5], ['COOO--X-XX', 'none'], ['C--XOO--X-', 6], ['COOO-X-XX-', 'none'], ['CO-XOO--XX', 7], ['CX-O-O-OXX', 'none'], ['CO--OXXO-X', 'none'], ['C-OO-X---X', 1], ['CX--XXOOO-', 9], ['C-OXXO-X-O', 1], ['C-X-X-XOOO', 'none'], ['C-XOOXX--O', 8], ['C-XOX--OXO', 5], ['COXX---OOX', 6], ['CXO--O-XXO', 4], ['C-O--X-XO-', 3], ['CX-X-O-O--', 2], ['C--XXOXOO-', 9], ['COX--OXOX-', 9], ['CXOO-O-XX-', 9], ['CXOOXX---O', 7], ['COOX-OX-X-', 9], ['COX-O-X-XO', 5], ['C-XXOO-XO-', 6], ['COXXOXO---', 8], ['CX-OX----O', 7], ['C-X-X-OOOX', 1], ['C--O-XOXXO', 'none'], ['COXXX-OO--', 8], ['CXOX--OO-X', 5], ['CX---OXXOO', 4], ['CX-XOOO-X-', 'none'], ['CXO--X---O', 7], ['COO-OXXXXO', 3], ['COXXOX---O', 8], ['CX-OO-OXX-', 9], ['CX-OX-XO-O', 5], ['CXO---XO--', 9], ['COX-OX-X-O', 8], ['C-O--X-X-O', 3], ['C-O-XO-XXO', 1], ['C-OX-OOX-X', 8], ['CXO-OOX-X-', 9], ['CXO-OOXXXO', 3], ['CX-XX-OOO-', 9], ['C---OOXOXX', 3], ['CXO-X-O-XO', 7], ['CXXO--OOX-', 5], ['C-X-XO-XOO', 1], ['COXOO-XXOX', 5], ['COXXO---OX', 7], ['C-O---XXO-', 5], ['CX---XXOOO', 'none'], ['CXX-OOO-X-', 'none'], ['COXO-X-X-O', 8], ['COX-X-X-OO', 5], ['CO-XX-XO-O', 5], ['C-XO-OOX-X', 8], ['C-OOX-XO-X', 5], ['CXOO-X-X-O', 4], ['CX--O-OXOX', 5], ['C-X-O-OXXO', 5], ['C-OX-OXXO-', 'none'], ['C-XO-OXXO-', 1], ['COX-O--XOX', 3], ['C-OX-XX-OO', 7], ['CXOX--XOO-', 9], ['COXXOOX---', 9], ['COOX-XO--X', 7], ['CO-XX--XOO', 5], ['CX-----XOO', 4], ['CXX-O--XOO', 3], ['COXX-O-XO-', 9], ['C-XOOX-X-O', 8], ['C-X-XXOOO-', 1], ['C-XOXOX--O', 1], ['C-XOOX--OX', 1], ['C-OXX--OXO', 6], ['C-O---X-XO', 5], ['CX-XO---O-', 2], ['C-OX-O-XXO', 1], ['C--OXXOOX-', 9], ['CX--XOO-OX', 7], ['CO-O-XX-XO', 4], ['CO-XX----O', 5], ['COXOX--X-O', 5], ['CX-XOO-X-O', 2], ['COO-X-XO-X', 5], ['CX-OXXO-O-', 9], ['C-O-OOXXX-', 9], ['C-X-OOXO-X', 3], ['CXOX-O--OX', 'none'], ['C-OOXO-XX-', 9], ['C---OXXOXO', 2], ['CX----O-OX', 5], ['CX---OOXOX', 4], ['C-OOX-X-OX', 5], ['C-OXX-OX-O', 8], ['C-XXX-OO-O', 8], ['CXXO-OO-X-', 9], ['CXOXX-O--O', 7], ['C--XOOOXX-', 'none'], ['CX-XO-OO-X', 5], ['C-O-OX-OXX', 1], ['CX--X--OO-', 9], ['CO---X--XO', 2], ['C--OOXX-XO', 2], ['COXX-O-O-X', 6], ['CXXO--XO-O', 5], ['C--OX--XO-', 1], ['C-OOXX-XO-', 6], ['CXO-O-XO-X', 8], ['C--X-OOXOX', 4], ['C--XXO---O', 1], ['CX-XXOO--O', 8], ['C--XOOXX-O', 2], ['CX-OX--OOX', 5], ['C-XO-XX-OO', 4], ['COXXX-O--O', 5], ['C-XXOO--OX', 6], ['C--X--OOX-', 2], ['C-OOOX--XX', 7], ['COXOOX---X', 8], ['C--O-XXOXO', 4], ['C-O-O-XXXO', 5], ['COO-XX--OX', 6], ['CO--OXXOX-', 'none'], ['CO-OXO-XX-', 9], ['CXO-OOXX--', 8], ['CO-XXO-X-O', 'none'], ['C-XX--OOXO', 5], ['CXOO--XX-O', 4], ['CO-OXOXX--', 9], ['C-O-XX-OOX', 6], ['CX-OOX--XO', 2], ['CO--XOO-XX', 7], ['COX-XOOOXX', 3], ['CXOOXXO---', 9], ['COXOOXXO-X', 'none'], ['COXXOO-X--', 9], ['C-XOXO----', 7], ['C-XO-OXX-O', 4], ['COXO-OXXXO', 'none'], ['CX--O-OOXX', 5], ['CXOXX--OO-', 5], ['CXXOO-----', 5], ['CO---XOXOX', 3], ['CX-XOO-XO-', 2], ['CO-XXXO-O-', 7], ['CO-O--XXOX', 5], ['CX-OX-OO-X', 5], ['C---X-OX-O', 1], ['C-XO---XO-', 4], ['C-OX-X-OOX', 6], ['COXOO--X-X', 8], ['C--OOXXX-O', 2], ['COXOXX-O--', 9], ['C-XX-OXOO-', 9], ['C-XX-XOOO-', 1], ['COO-X-OXX-', 9], ['C-XO--XXOO', 4], ['CXOX-X--OO', 7], ['COX--OO-XX', 7], ['CX-X-OX-OO', 2], ['COOXO-XX--', 9], ['COOXOX---X', 7], ['C-OOX--XXO', 1], ['COXO-O--XX', 7], ['COXXOOXX-O', 'none'], ['C--O-O--XX', 7], ['COXOXX-XOO', 6], ['C-OOX-XXO-', 5], ['CX-O-OX---', 7], ['COX-O-OX-X', 8], ['CO-O-XO-XX', 7], ['COOOX--X-X', 'none'], ['CO-X--OXXO', 5], ['CX-X-O-OOX', 6], ['COO-OXXOXX', 'none'], ['CXO-OOX--X', 8], ['COX---OXOX', 5], ['C-OX--XXOO', 5], ['COO-XX-O-X', 6], ['C-OO-XOXX-', 9], ['COO-X-OX-X', 8], ['C-O-XO-X--', 1], ['C-OXXOOX--', 8], ['COX---OXXO', 5], ['CXO--XOXO-', 9], ['COXO-O-XX-', 9], ['CO-XO--X--', 5], ['CO-XO-XXO-', 9], ['CXXOO-O-X-', 5], ['C-X-XOO-XO', 1], ['COOXXO-OXX', 6], ['COO---XXXO', 3], ['CXXOO---OX', 5], ['COX--OXXO-', 9], ['CX-XOO-O-X', 6], ['COXX--XOO-', 9], ['C---OXOXOX', 3], ['COX-OXOXOX', 3], ['COX-OX-XO-', 3], ['CXXOOX--O-', 9], ['C-OXOXO--X', 8], ['CXXO--OX-O', 'none'], ['COX---OOXX', 5], ['CX--OOXX-O', 2], ['CXO-OO-X-X', 8], ['CX-X-XOO-O', 2], ['COX-XXO-O-', 7], ['C-X-XXO-OO', 3], ['CXO-XO-OX-', 9], ['CO--O-X--X', 3], ['CXXO-O-XO-', 4], ['C-XXO-O-XO', 5], ['CXX--OOX-O', 4], ['CO-O--XOXX', 5], ['COXX-X--OO', 7], ['CX-O-OOXX-', 9], ['COXOX--OX-', 5], ['CX--OO-XXO', 6], ['C-XOXO-XO-', 1], ['C-O-XOXX-O', 1], ['CX-OO-X-XO', 2], ['C-OOX-XX-O', 5], ['COXX--X-OO', 7], ['COXOX-X-O-', 5], ['C-OOOXX--X', 1], ['C--OXX-O--', 6], ['COXXO--OX-', 'none'], ['C-OXOX-OX-', 1], ['CX-XXO-OO-', 2], ['C--XOXO-XO', 7], ['C-XOXOOXOX', 1], ['COOXO-X-X-', 9], ['COOXOXX-XO', 7], ['COX-OXXO--', 'none'], ['CXXOOXOX-O', 'none'], ['CX-OX-O-OX', 7], ['C--XOXXO-O', 8], ['C-O-XOX-OX', 'none'], ['CO-XXOX--O', 'none'], ['C-OXXOX-O-', 'none'], ['CXX---OOOX', 5], ['CO-X----XO', 5], ['CX--OOOXX-', 'none'], ['CX-XOXO--O', 8], ['C-OOXXO-X-', 1], ['C-OX-O---X', 6], ['C-X---O-OX', 1], ['CO--X-OXOX', 5], ['C-XOXXOOOX', 1], ['C-X-OXXOO-', 1], ['COXOX--XO-', 5], ['CXO-O-XXO-', 5], ['CO--XX-OXO', 6], ['CXO-OXOX--', 9], ['COOX-XXO--', 9], ['C-OXO-O-XX', 7], ['CO---XXXOO', 4], ['CXO-OX-XO-', 9], ['CX-OO-OX-X', 8], ['CX----OX-O', 4], ['C--OX-OOXX', 5], ['C-X-XXOO-O', 8], ['CO-XOXO-X-', 7], ['CO-XXX-O-O', 8], ['CXOX--OX-O', 8], ['CX-XO--XOO', 6], ['CXOOXX--O-', 9], ['CXX-O-O-OX', 5], ['CX--XOOOX-', 3], ['CXO-X---O-', 7], ['CXO--OXX-O', 4], ['COO-XOX-X-', 3], ['C-XOXX--OO', 6], ['CX-XOOXO--', 9], ['CXOXO-O--X', 5], ['CXOXOOOX-X', 'none'], ['CXO-OX--XO', 7], ['CX-XOO-OX-', 6], ['CXOX-XO--O', 7], ['COO--XXO-X', 4], ['CX-X--XOOO', 'none'], ['CO-XOO-XX-', 9], ['C-OOX-X-XO', 5], ['C-O-O-XXOX', 5], ['C---XXOXOO', 3], ['COOO-XX--X', 'none'], ['C-XOOO-XX-', 9], ['CX---XOOXO', 2], ['CX--XO-OXO', 2], ['COXX-OOXXO', 'none'], ['COOXX-X--O', 5], ['COO-X-XOX-', 5], ['C-O--OXXOX', 'none'], ['CX-O-XOOX-', 9], ['CXOOX---XO', 7], ['CXXOX-O-O-', 9], ['C-X-OOXOX-', 1], ['COXO-XX--O', 8], ['CXX-XOOOXO', 3], ['CO--OOX-XX', 7], ['COX-XXOXOO', 3], ['CXXOOXO---', 9], ['CO---O--XX', 7], ['COO-OX--XX', 7], ['COO--XO-XX', 7], ['CX----XOO-', 9], ['CO-X--OOXX', 5], ['CXXOOO---X', 8], ['CXOX---OOX', 6], ['C-XOXOOX--', 9], ['C-O--XOXOX', 4], ['CX---O-OX-', 3], ['CX-O-OOX-X', 8], ['CXX-OO--XO', 3], ['C-OOXX-X-O', 6], ['CX--OXOOX-', 9], ['C-X-X-OXOO', 3], ['C-XO-XOO-X', 8], ['C---XXO-O-', 7], ['CO-OXX--OX', 6], ['CXO-XOXO--', 9], ['C-XO--XOXO', 5], ['C-O-X-OXOX', 5], ['C-OOOX-XX-', 9], ['C-X-OOO-XX', 'none'], ['CO-XX-OXO-', 5], ['CX-O--OXOX', 5], ['CO--XO-XXO', 'none'], ['C-X-XO-OXO', 3], ['CO--X-XOOX', 5], ['C-XX-O-XOO', 1], ['CXO-O--XOX', 5], ['C-X-OO-XOX', 6], ['CXXOO--OX-', 5], ['C-OOX-O-XX', 7], ['CXOX-O--XO', 7], ['C-OOXO-X-X', 8], ['CO-X-O-OXX', 6], ['C-OO-XXO-X', 4], ['CXOOX---OX', 7], ['C-XXOO--XO', 1], ['CO-OXX-X-O', 6], ['C-----XXOO', 1], ['CXX---OXOO', 4], ['CX-XOXOO--', 9], ['CXXOO--X-O', 8], ['CX--OXO-XO', 3], ['C-XXOOX--O', 1], ['COXX--OX-O', 5], ['CX--OOX-OX', 3], ['COX-OX-O-X', 'none'], ['CXXO-OXO--', 'none'], ['C--OXXO-XO', 'none'], ['C-OXOO-X-X', 8], ['COO---XOXX', 3], ['CXX-OOO--X', 'none'], ['C--X-XOOOX', 1], ['CXX-O-OO-X', 5], ['C-O-XO-XOX', 'none'], ['CXO--OX-OX', 'none'], ['C--XXOO-XO', 1], ['COO-XXO--X', 7], ['CO-XXOO-X-', 9], ['CXX-X-OO-O', 3], ['CO-O-X--X-', 2], ['COOO-X-X-X', 'none'], ['C-XX-OO-XO', 1], ['CO-XX-OO-X', 8], ['C-OO--XOXX', 1], ['CXXOOX-O--', 9], ['C--XX-OXOO', 5], ['COOXXO-X--', 9], ['COXX--O-OX', 7], ['CO-OXOX--X', 8], ['COX-X--XOO', 5], ['C-OXXX-O-O', 6], ['CXOX-O-O-X', 6], ['C-XO-OX-XO', 7], ['COXOX-XO--', 5], ['C-XX-OXO-O', 1], ['COXXO--XO-', 9], ['COXO-OXX--', 8], ['C-OXOX--XO', 7], ['CX-OXX-OO-', 9], ['COX-XOO--X', 7], ['CO-O-XXX-O', 4], ['COX-X-OX-O', 5], ['C-OX--OXXO', 5], ['COX-X-XO-O', 5], ['C-X--XXOOO', 'none'], ['C-OOXX-OX-', 6], ['C--OXX-XOO', 6], ['CX-XO-OOX-', 5], ['CXOXOXO---', 9], ['C-XOX--OOX', 5], ['CXOO-OX--X', 7], ['CO--XX-XOO', 6], ['C--XXOOX-O', 1], ['C-O-OXXX-O', 3], ['COX-XO-O-X', 3], ['CXO-O-X-XO', 7], ['C-O--XXOOX', 4], ['CXO-OX-OX-', 9], ['C---XOO-X-', 1], ['CXOXO--X-O', 5], ['CXO--XXO-O', 4], ['CXOXOXXO-O', 8], ['CO-XXO--XO', 'none'], ['C-O-OOX-XX', 7], ['CO-XXO-O-X', 6], ['C-OXX-OXO-', 5], ['COO-O-X-XX', 7], ['C-XOO-XXO-', 9], ['C-OOXXO--X', 1], ['CXXOO-XO--', 5], ['CXOX-X-O-O', 8], ['C-XO-XXO-O', 8], ['C-OXO-XOX-', 9], ['CO-XX--OXO', 5], ['C-XOO-X-OX', 1], ['CO-OOXX-X-', 2], ['C--OXOXX-O', 1], ['COX--XOO-X', 8], ['COOX-XO-X-', 7], ['COOX--XXO-', 9], ['COX-XOX--O', 'none'], ['CO-XOOXX--', 9], ['CXOXO-X-O-', 9], ['C-XO-X-OOX', 6], ['COOXXO---X', 8], ['C-XXX--OOO', 'none'], ['CX-O-O-XOX', 4], ['COX-XXOO--', 8], ['CO-O-X-OXX', 2], ['COX-XX--OO', 7], ['C-OO-XXX-O', 4], ['CXOO--OX-X', 8], ['C--OXX-OOX', 6], ['C-XXO--OXO', 5], ['CXXO-X--OO', 7], ['CXX-XO-OO-', 3], ['C-O-X-OOXX', 1]]
2739Итак, БИНГО (!)
Гипотеза подтверждена: робот, сыграв за несколько секунд 100 000 партий случайным перебором, собрал себе базу всех возможных комбинаций и определил «лучшие» ходы для каждой комбинации.
Теперь во время игры робот ничего не обдумывает, а просто вытаскивает из памяти «лучший» ход для текущей ситуации.
Неоптимизированный код игры за «Крестики» на python
# робот играет за крестики
def board():
print()
print(current_combination_code[1],'',current_combination_code[2],'',current_combination_code[3])
print(current_combination_code[4],'',current_combination_code[5],'',current_combination_code[6])
print(current_combination_code[7],'',current_combination_code[8],'',current_combination_code[9])
print()
available_list = list(range(1,10))
win_list = ['123','456','789', '147', '258', '369', '159', '357']
current_combination_code = 'C---------'
current_status = ''
best_step = ''
win_combination_code = ''
print('started...','\n')
while not current_status:
for index, value in enumerate(tableO_for_best_step_for_X):
current_side = 'X'
best_step = ''
if value[0] == current_combination_code:
best_step = value[1]
print('step_X:',best_step)
available_list.remove(best_step)
current_combination_code = current_combination_code[:best_step] + current_side + current_combination_code[best_step + 1:]
break
board()
if len(available_list) == 0: current_status = 'draw'
for key_win in win_list:
if current_combination_code[int(key_win[0])] == current_side and current_combination_code[int(key_win[1])] == current_side and current_combination_code[int(key_win[2])] == current_side:
current_status = 'win' + current_side
win_combination_code = key_win
break
if current_status: break
current_side = 'O'
print('available_list:',available_list)
try:
input_step = int(input('Enter your step in integer: '))
except ValueError:
print('Enter in integer')
else:
if input_step in available_list:
available_list.remove(int(input_step))
current_combination_code = current_combination_code[:int(input_step)] + current_side + current_combination_code[int(input_step) + 1:]
board()
else: print('Enter in integer from available_list')
print('current_status:',current_status)
print('win_combination_code:',win_combination_code)
print()Пример игры за «Крестики»
started...
step_X: 5
- - -
- X -
- - -
available_list: [1, 2, 3, 4, 6, 7, 8, 9]
Enter your step in integer: 4
- - -
O X -
- - -
step_X: 9
- - -
O X -
- - X
available_list: [1, 2, 3, 6, 7, 8]
Enter your step in integer: 1
O - -
O X -
- - X
step_X: 7
O - -
O X -
X - X
available_list: [2, 3, 6, 8]
Enter your step in integer: 3
O - O
O X -
X - X
step_X: 8
O - O
O X -
X X X
current_status: winX
win_combination_code: 789
Комментарии (2)
Siberianice
17.01.2023 13:21+3Мне кажется, что все-таки это не ИИ, а перебор вариантов. С таким подходом можно пройти первый уровень Марио, но потом база ходов вырастет до громадных размеров и время поиска до бесконечности. Лучше искать не статистически удачные ходы , а функцию для них. Так должен работать ИИ. В идеале, конечно)
shasoftX
Как-то писал ИИ для крестиков-ноликов. И столкнулся с ситуацией, когда компьютер делает тупой ход. Т.е. у меня два крестика, а он нолик ставит не в оставшуюся третью клетку, а просто куда попало. Только минут через 30 до меня дошло, что компьютер просто понимает что он уже проиграл при любом ходе и поэтому ходит куда попало. Пришлось дописывать чтобы он не просто ходил куда попало в случае проигрышной ситуации, а чтобы выбирал "наилучший" ход. И вот тут была заморочка в том чтобы выбирать этот "наилучший" ход, потому что с точки зрения компьютера наилучшего хода не было, он в любом случае проигрывал. В качестве параметра взял количество ходов через которое он проиграет. Т.е. есть ход при котором он проиграет через 2 хода лучше чем ход когда он проиграет через 1 ход. В этом случае была вероятность что человек ошибется и игра сведется к ничьей.