Comments 30
Имхо ваш алгоритм неэффективен. Вместо того чтобы перебирать всё поле, достаточно проходиться по всем позициям, на которых стоит крестик или нолик, и для каждой такой позиции проверять, не стоит ли она в ряду из 5 таких же символов, вертикальном горизонтальном или диагональном. (прямой проверкой индексов во все стороны). Символы, провалившие проверку, можно помечать, чтобы не проверять много раз. На пометки нужна доп. память и нужны 4 вида пометок тк позиция, помеченная например "не в вертикальном ряду из 5", может находиться в горизонтальном ряду из 5). Это решение в лоб, думаю есть ещё эффективнее
Если задача стоит в проверке наличия выигрышной позиции после хода, то достаточно все эти проверки производить относительно последнего поставленного крестика/нолика
Условности задания, там к боту приходит конкретно вся доска, а он отвечает новой доской с новой фигурой
Вопрос будет ли это быстрее побитового умножения и по загруженности памяти, не совсем уверен
Нахрена хранить позицию в виде битовой карты? Я понимаю, если бы вы играли на поле мегабайт на мегабайт. Но поле 19 на 19 - это всего лишь ~400 байт в виде двумерного массива.
Игра на поле 19x19, где надо поставить пять в ряд, называется гомоку.
Она же рэндзю, и теория говорит, что без дополнительных ограничений (правил) выигрывает тот, кто ходит первым ("чëрные", в оригинале). Я, к тому, что теория игры достаточно разработана. Про "Алгоритм лучшего хода" пока -- ни слова. По-мне, так с него и нужно начинать серию статей, а танцы с битами оставить на финал потому как это давно известное дело. Хотя, наверное, от командного мировоззрения зависит.
Ваши битовые оптимизации - нифига не оптимизации.
Если немного быть знакомыми с динамическим программированием, то гораздо эффективнее было бы хранить поле в виде матрицы 19x19 и считать наибольшую длину горизонтального/вертикального/диагонального куска из заданного символа, заканчивающегося в каждой клетке.
Например, для горизонтальных проверок:
for (int i = 0; i < 19; ++i) {
int cur_len = board[i][0] == cur_char;
for (int j = 1; j < 19; ++j) {
cur_len = (board[i][j] == cur_char) ? cur_len+1 : 0;
if (cur_len == 5) {
// нашли пять в ряд.
}
}
}Если вместо переменной cur_len завести матрицу и хранить значения в каждой клетке, то вообще один и тот же код проверяет по всем трем направлениям:
const int dx[3] = {1, 0, 1};
const int dy[3] = {0, 1, 1};
for (int k = 0; k < 3; ++k) {
for (int i = 0; i < 19; ++i) {
cur_len[i][0] = (board[i][0] == cur_char);
cur_len[0][i] = (board[0][i] == cur_char);
}
for (int i = 1; i < 19; ++i) {
for (int j = 1; j < 19; ++j) {
cur_len[i][j] = (board[i][j] == cur_char) ? cur_len[i-dx[k]][j-dy[k]]+1 : 0;
if (cur_len[i][j] == 5) {
// нашли пять в ряд 'cur_char'.
}
}
}
}Если еще перевести поле в 2 булевых матрицы для X и O, то точно будет быстрее вашего подхода. Особенно для диагональных проверок. И не надо десятков шаблонов.
Не думаю, что то,что вы написали - верно, напишите такого же бота вашим методом - проверим)
А вам советую больше про битовые операции почитать над bitboards почитать
Нет, это вам стоит почитать про динамическое программирование.
Про битовые трюки я отлично знаю. Вы их, кстати, тоже неправильно применяете. Вы заменяете 5 сравнений на одно за счет прикладывания маски с 5-ю единичными битами. Динамическое программирование, что я написал, тоже заменяет 5 сравнений одним, но за счет переиспользования предыдущих результатов сравнения.
А битовыми трюками можно ускорить не в 5, а в 19 раз. И не надо никаких масок. Если у вас каждая строка хранится в битах одного uint, то взяв board[i]&board[i+1]&board[i+2]&board[i+3]&board[i+4] вы получите единичные биты в тех столбцах, где в первых 5 строках есть символы. Если получили не 0 - то любой единичный бит - это искомое начало 5 элементов вертикально в ряд.
Соответственно, вам надо транспанировать матрицу для проверки горизонтальных пятерок, а не вертикальных. Для диагональных проверок вам надо брать board[i] & (board[i+1]<<1) & (board[i+2] << 2)...
Для другого наклона диагонали - сдвигайте вправо, а не влево.
как мне кажется, я делаю нечто подобное что вы написали, но может я не до конца вас понял
Подобного у вас только то, что вы битовые операции используете. У меня циклы 14*5 и всего 14 проверок. У вас же циклы 19*15 и столько же проверок. А в диагональных случаях у вас вообще циклы 19*5*3 (кстати, как у вас там вообще работает? Вы к board обращаетесь только к строкам count, кратным 5 - вообще не проверяя все, кроме трех строк).
Главная ваша проблема, что вы пытаетесь прикладывать жесткие маски. Это имеет смысл делать, только когда вам важны символы, скажем именно в 4-ом ряду. Нет, в этой задаче 5 в ряд могут быть где угодно. Поэтому ваш подход заставляет прикладывать одну и ту же маску ко всем позициям. Хотя можно наоборот, для всех позиций сразу проверить, а проходит ли через них пять в ряд.
Вот код для проверки вертикальных 5-в-ряд:
bool CheckVertical (int board[19]) {
for (int i = 0; i < 14; ++i) {
int acc = board[i];
for (int j = 1; j < 5; ++j) {
acc &= board[i+j];
}
if (acc != 0) return true;
}
return false;
}Это работает, потому что если где-то есть 5 в ряд, то там board[i], board[i+1]... board[i+4] все будут иметь 1 в одном и том же разряде. И мы получим 1 в acc в этом разряде. И наоборот, если мы получили где-то 1 в acc, то значит на доске в 5 строках в этом столбце есть 1.
Вот диагонали. Вместо диагональной маски, мы сдвигаем строки поля и потом ищем тут вертикальные 5-в-ряд:
bool CheckDiagLeft (int board[19]) {
for (int i = 0; i < 14; ++i) {
int acc = board[i];
for (int j = 1; j < 5; ++j) {
acc &= board[i+j] << j;
}
if (acc != 0) return true;
}
return false;
}
bool CheckDiagRight (int board[19]) {
for (int i = 0; i < 14; ++i) {
int acc = board[i];
for (int j = 1; j < 5; ++j) {
acc &= board[i+j] >> j;
}
if (acc != 0) return true;
}
return false;
}Вот с горизонтальными чуть сложнее, но можно и без транспанирования, основываясь на той же идее. Опять же, не надо никаких масок прикладывать к каждой позиции, а надо лишь проверить сдвинутые строки. Вроде как взять 5 копий строк: eсли там есть диагональ, то в строке есть 5-в-ряд:
bool CheckHorizontal (int board[19]) {
for (int i = 0; i < 19; ++i) {
int acc = board[i];
for (int j = 1; j < 5; ++j) {
acc &= board[i] << j;
}
if (acc != 0) return true;
}
return false;
}
Когда-то писал подобное для игры в крестики-нолики "по 5" на бесконечном поле, ещё для ЕС .. деталей уже не помню к сожалению. Но, как-бы там памяти с гулькин нос было, хранить пустые клетки вообще незачем (поле безрамерно) и оценивать надо далеко не всю массу крестиков и ноликов, а только "краевые", которые могут участвовать в возможных вариантах.
Так, на вскидку что вспомнилось..
Возможно стоит добавить какие-то эвристические алгоритмы. Роевой интеллект или генетические алгоритмы. Я знаю, что в задачах которые слабо поддаются перебору, хорошо заходит такого рода варианты.
да, это отложил на вторую статью, но вы правы на 100%
Смутно вспоминаю, что алгоритм был тупым как палка: ищем куда можно воткнуть 5-й элемент, если такого места нет, то ищем .. где можно воткнуть третий, но так чтобы получилось 2 тройки, открытых с обоих концов, если нет то ищем 3+4 или просто 4. Если нет ничего "подходящего выше", то ищем подобное в других элементах и затыкаем возможный проигрыш своим. как-то так..
Есть очень простой алгоритм основанный на оценках: Для каждого множества из 5-в-ряд на доске проверим, состоит ли оно лишь из 'O' или лишь из 'X'. Если там есть и те и другие, то это множество никогда не станет победным ни для одного из игроков. В противном случае, добавим всем пустым клеткам в этом множестве очков, в зависимости от количества стоящих заполненных символов. Самая большая оценка должна быть у множества из 4 'X' (если мы за крестики играем). Тогда одним ходом мы можем закрыть пятерку и победить. Допустим 10^9. Потом идет 4 'O'. Надо обязательно закрыть эту клетку, ведь иначе враг следующим ходом выиграет. Можно тут назначить 10^8 Потом должны идти те клетки, которые лежат на пересечении двух множеств из троек. Ведь поставив сюда, мы получим 2 пересекающиеся четверки, что даст нам "вилку": что бы враг следующим ходом не закрыл - мы победим на следующем ходу. Поэтому тройке 'O' назначим 10^7. И так далее, чередуем символ и уменьшаем количество и назначаем ситуации какую-то степень 10. Просуммировав эти оценки повсем пятеркам на поле для всех клеток останется только выбрать максимум.
Тут, конечно, много пространства для эвристик. Например, можно пустым пятеркам тоже назначать какие-то очки. Чтобы, первый ход был подальше от границы. Надо сильнее оценивать 2 пересекающиеся тройки, если они не параллельны, чем если они параллельны... Т.е. для каждой клетки надо не сумму очков считать, а сколько там горизонтальных, вертикальных и т.д. единиц-двоек-троек-четверок каждого типа и как-то на основе этого комбинировать итоговую оценку.
Да проще делается. Создаём нейросетку, которая дубасит сама себя, играет с собой. И записываем состояние весов в удачной партии для следующего поколения сети. Рандомно чуть чуть видо изменяем состояние весов, и запускаем игру по циклу. Повторить 1000500 раз ))). Легко. ?
Очень сложные Крестики-Нолики