По ходу игры необходимо опасаться вилок, избегая, по возможности, ходов, способных к ним привести. Примем за аксиому, что вас возможно подвести к вилке только после второго или третьего вашего хода (напоминаю, вы играете вторым номером, "ноликами"), и никак иначе. Будем считать, что к вилке привел именно последний ваш ход; такое допущение, ввиду крайней простоты Tic Tac Toe, приемлемо. Как быть с этим?
Примечание. Статья содержит лишь очень небольшие фрагменты кода. Тем, кто считает, что для лучшего понимания материала нужно рассмотреть всю кодовую базу (или просто поиграть), оптимально выполнить:
git clone https://github.com/cmirnow/Tic-Tac-Toe-AI-with-Neural-Network-Resurrections.git
В настоящий момент я остановился на следующей логике, которая, вполне может статься, изменится в дальнейшем. Но пока что результат устраивает. Определяем (и замораживаем) константу (первоначально используется для определения того, что партия завершена чьим-то выигрышем, к слову. Форки - побочное):
WINNING_TRIADS = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8],
[0, 3, 6],
[1, 4, 7],
[2, 5, 8],
[6, 4, 2],
[0, 4, 8]
].freeze
И далее, при формировании csv-лога ходов, ищем вилки:
def fork?
WINNING_TRIADS.select do |x|
@board[x[0]] == @board[x[1]] && @board[x[2]].class != @board[x[0]].class &&
place_x?(x[0]) ||
@board[x[1]] == @board[x[2]] && @board[x[0]].class != @board[x[2]].class &&
place_x?(x[1]) ||
@board[x[0]] == @board[x[2]] && @board[x[1]].class != @board[x[2]].class &&
place_x?(x[0])
end
end
Соответственно, если комбинация найдена два раза...
if @game.fork?.size > 1
- вилка найдена.
Ок, работает. Хотя данный способ не учитывает следующего обстоятельства: вполне возможно, ваш ход приводит к возможности вилки лишь условно, а на практике противник вынужден сделать совсем иной ход, дабы не позволить вам следующим ходом выиграть. Что же, это решаемо.
Смоделируем и определим ряд потенциально опасных ситуаций:
DANGEROUS_SITUATIONS_1 = [
[6, 4, 2],
[0, 4, 8]
].freeze
DANGEROUS_SITUATIONS_2 = [
[0, 4, 7],
[0, 4, 5],
[2, 4, 3],
[2, 4, 7],
[3, 4, 8],
[1, 4, 8],
[1, 4, 6],
[5, 4, 6]
].freeze
def fork_danger_1?
DANGEROUS_SITUATIONS_1.detect do |x|
@board[x[0]] == @board[x[2]] &&
@board[x[0]] != @board[x[1]] #&&
#@board[x[0]].class == @board[x[1]].class
end
end
def fork_danger_2?
DANGEROUS_SITUATIONS_2.detect do |x|
@board[x[0]] == @board[x[2]] &&
@board[x[0]] != @board[x[1]] #&&
#@board[x[0]].class == @board[x[1]].class
end
end
def fork_danger_3?
DANGEROUS_SITUATIONS_1.detect do |x|
@board[x[0]] != @board[x[2]] &&
@board[x[1]] == @board[x[2]] #&&
#@board[x[0]].class == @board[x[1]].class
end
end
И, соответственно, создадим три массива, в которые, при каждом очередном анализе ситуации на доске, станем помещать удовлетворяющие условиям ходы: 1. однозначно неприемлемые, 2. потенциально приводящие к вилке и 3. атакующие (т.е. те, в силу которых противник вынужден, во избежание немедленного проигрыша, реализовать единственно возможный для него ход). Разумеется, массивы будут иногда пересекаться, учтем это при построении логики игры. Кроме того, последнее слово остается за neural network.
Хм, ну вот, например, как-то так:
array_of_games.each do |row|
row.each do |e|
next unless e == current_position
if row[6].to_i - row[3].to_i == 2 && row[4] == 'O' && row[2].to_f != 0.2
unacceptable_moves_array << row[0]
# Find moves that inevitably lead to a fork:
elsif fork_danger_1 && row[3].to_i == 3 && row[0].to_i.odd?
unacceptable_moves_array << row[0]
elsif (fork_danger_2 || fork_danger_3) && row[3].to_i == 3 && row[0].to_i.even?
unacceptable_moves_array << row[0]
end
next if row[5].nil?
# Find moves that may lead to a fork:
array_of_moves_to_fork << row[0] if row[3].to_i == row[5].to_i
# Find attacking moves:
attack_moves_array << row[0] if row[3].to_i == row[5].to_i && row[6].to_i < 7
end
endЭто происходит во время первого прохода по общему массиву игр; во время же второго прохода - примеряем каждый из потенциально возможных (иных в логе нет) ходов к полученным трем массивам, отбрасывая заведомо ненужное и переопределяя, при необходимости, изначально присвоенные веса. Поскольку содержимое csv-файла преобразовано в самом начале игры (т.е. серии игр) в массив:
CSV::WithProgressBar.read('ss.csv').each.to_a
, пауз нет, наш Artificial Intelligence работает практически мгновенно:
array_of_games.each do |row|
row.each do |e|
next unless e == current_position
next if arrays[0].include?(row[0])
unless arrays[1].include?(row[0]) && !arrays[2].include?(row[0])
if row[6].to_i - row[3].to_i == 1
x_data.push([row[0].to_i])
y_data.push([1])
elsif row[6].to_i - row[3].to_i == 3
if arrays[2].include?(row[0])
x_data.push([row[0].to_i])
y_data.push([0.9])
elsif arrays[1].include?(row[0])
x_data.push([row[0].to_i])
y_data.push([0.3])
end
else
x_data.push([row[0].to_i])
y_data.push([row[2].to_f])
end
end
end
Повторюсь, удалось бы обойтись без костылей, если бы массив игр, используемый AI для анализа, не формировался практически полностью рандомно. Иной подход несложно реализовать, но не хочется отказываться от найденного эффектного решения: репозиторий гитхаба, содержащий код AI - не содержит csv-файла, который генерируется пользователем автоматически при первом запуске.
То, что в итоге, скармливаем нейронке:
Отмечу, что в одной и той же игровой ситуации на доске (и с одним и тем же csv-файлом) этот Neural Network способен выдавать различные решения ходов.
data = nn_data(board, fork_danger_1, fork_danger_2, fork_danger_3, array_of_games)
fann_results_array = []
train = RubyFann::TrainData.new(inputs: data[0], desired_outputs: data[1])
model = RubyFann::Standard.new(
num_inputs: 1,
hidden_neurons: [4],
num_outputs: 1
)
model.train_on_data(train, 5000, 500, 0.01)
data[0].flatten.each do |i|
fann_results_array << model.run([i])
end
result = data[0][fann_results_array.index(fann_results_array.max)]
В результате - у вас максимум ничья, минимум - проигрыш, выиграть не получится. Разве что подведет рандомно сгенерированный csv-файл (такое случается, но очень нечасто), который в этом случае оптимально пересоздать. Впрочем, описанная ревизия кода, может статься, вовсе не окончательная, итоги подводить рано.
