Автор оригинала: Alessandro Flati.
В этом посте я собираюсь построить пример искусственного интеллекта в виде Проблемы удовлетворения ограничений (или CSP ), показывая, насколько математические, логические навыки и знания в области компьютерных наук могут помочь в этом процессе.
Для этой цели я взял игру-головоломку под названием Hitori на популярном сайте логических головоломок Nikoli . Я выбрал Историю не потому, что это было удобно , Я буквально выбрал случайную игру именно потому, что не имело значения, какая игра была для того, что я хотел показать.
Что такое CSP
Давайте начнем с изучения того, что такое CSP на самом деле. Как следует из названия (и Википедии):
CSP-это математические задачи, определяемые как набор объектов, состояние которых должно удовлетворять ряду ограничений или ограничений.
Ладно, это было довольно загадочно. Я бы сказал, более неформально, что мы можем рассматривать CSP как состоящие из трех компонентов:
- Переменные : что-то, что нам нужно выяснить, чтобы решить проблему.
- Домены : какие значения мы можем присвоить переменным.
- Ограничения : это ясно.
Нам также необходимо уточнить термины состояние , завершено , решено и законно или, более формально, последовательный . Вы можете представить состояние CSP как моментальный снимок одного из шагов , участвующих в решении. Состояние считается последовательным или законным, если оно не нарушает никаких ограничений. Считается, что он завершен, если он определяет значение для каждой задействованной переменной, и считается решением, если он одновременно согласован и полон.
Однако не позволяйте этой формулировке вводить вас в заблуждение: вы можете думать о переменных, доменах и ограничениях действительно в общих чертах. Например, одним из ограничений может быть то, что вы можете назвать (несколько наивно) поиском решения самой проблемы.
Подумайте о шахматах: любой обычный матч формально является решением проблемы шахматного матча, потому что он удовлетворяет ограничениям, связанным с игрой, и приходит к выводу (либо белые выигрывают , либо черные выигрывают , либо есть ничья) с помощью серии законных ходов , но я собираюсь поспорить, что вы хотите включить в число ограничений, которые вы хотите выиграть или, по крайней мере, сыграть вничью против своего противника.
Итак, другими словами, мы будем искать те параметры, которые позволят нам решить проблему, в которой доминируют логика и интуиция, проблему, с которой человек может справиться после нескольких попыток, но (не обученная должным образом) машина будет бороться даже с самого начала.
Вам это не кажется знакомым?
В некотором смысле, это именно то, чего все пытаются достичь, прибегая к машинному обучению ( ML отныне) для решения всевозможных проблем.
Я собираюсь показать вам, через мгновение, что существует альтернатива, которую вы на самом деле должны предпочесть “стандартному” подходу ML, и я объясню, почему в последнем разделе. Просто потерпи со мной еще немного.
Хитори — правила
Это начальное состояние головоломки Hitori.
Около Dan1980 – Собственная работа, основанная на File:Hitori.jpg , CC НА 1,0 , Ссылка
Мы скажем, что два квадрата (также называемые ячейками ) являются смежными если они имеют общую сторону (например, две ячейки по диагонали друг к другу не смежны ). Цель игры состоит в том, чтобы очернить некоторые клетки, чтобы получить состояние, в котором выполняются эти три условия:
- Любое заданное число может отображаться не более одного раза в каждой строке или столбце.
- Черные клетки не соседствуют.
- Все остальные пронумерованные ячейки должны быть соединены друг с другом путем, состоящим из соседних пронумерованных ячеек.
Первые два условия в значительной степени объясняются сами собой, но третье условие на самом деле является хорошо известным топологическим свойством, называемым связностью путей , который вы прагматично можете представить как соединение любых двух ячеек ручкой, которая не может двигаться по диагонали и может проходить только через пронумерованные ячейки .
Вы можете легко увидеть, что все эти условия проверены в решении предыдущей головоломки Hitori.
Около Dan1980 – Собственная работа, основанная на File:Hitori_completed.jpg , CC НА 1,0 , Ссылка
Базовая структура и наивный подход
В дальнейшем я буду считать, что языком программирования является Java 8 , хотя я пытался написать код наиболее переносимым способом, и я не буду сосредотачиваться на тривиальных деталях, таких как геттеры, сеттеры и импорт
Итак, давайте перейдем к коду. Нам, конечно, понадобится базовый Ячейка класс и игра класс, который я буду называть Состояние игры , так как мы перейдем из одного состояния игры в другое, и мы можем рассматривать частично решенную игру как саму новую игру.
В классе Ячейка я решил отслеживать число, которое появляется в этой ячейке ( значение ), и его положение в сетке ( x и y ). Я также счел полезным сохранить ссылку на состояние игры , к которому принадлежит ячейка, вместе с набором ее соседей , которые являются просто его соседними ячейками.
Наконец, черный является истинным если ячейка черная (да?) и белая является истинной всякий раз, когда мы уверены, что ячейка не может быть черной : На самом деле я буду называть эти клетки белыми клетками.
Я знаю, о чем ты сейчас думаешь. Является ли нечерная клетка обязательно белой, и наоборот? Ответ отрицательный: в данном состоянии (на самом деле, часто) ячейка может находиться в неопределенном состоянии, когда мы просто не знаем, черная она или белая даже если, в конце концов, это будет один из этих двух. Что верно, так это то, что клетка не может быть черно-белой одновременно , очевидно.
public class Cell {
private final int value;
private final int x;
private final int y;
private final GameState gameState;
private final Set| neighbors = new HashSet<>();
private boolean black = false;
private boolean white = false;
}
| В классе GameState вместо этого я просто поместил ячейку сетку (реализованную в виде простого 2D-массива) и размер головоломки Hitori.
public class GameState {
private final Cell[][] grid;
private final int size;
}
Теперь/| действительно наивным подходом было бы использовать Поиск по глубине (или DNS), или Поиск по ширине (или АВТОБУС), или любой метод, который просто пробует все возможные комбинации.
Делая вид, что проверка того, является ли состояние законным и/или решенным – это операция, которая не требует много времени, с помощью элементарной математики мы знаем, что любой из этих алгоритмов будет чрезвычайно медленным по мере увеличения размера.
Каждая возможная комбинация означает, что для каждой ячейки мы должны выбрать, будет ли она черной или нет, и если
Существует также другая проблема: проверка того, является ли состояние законным и/или решенным , не является простой операцией. На самом деле, есть несколько вещей, которые нам нужно проверить в обоих случаях. Давайте добавим метод является законным в класс GameState : мы можем сказать, что состояние является законным, если у него нет соседних черных ячеек и если оно связано с путем. Нарушение любого из них нарушило бы второе или третье правило, указанное ранее.
public class GameState {
private final Cell[][] grid;
private final int size;
private boolean isLegit() {
return !connectedBlacksInRows() && !connectedBlacksInColumns() && this.isConnected();
}
private boolean connectedBlacksInRows() {
for (int i = 0; i < size; i++) {
for (int j = 0; j < size - 1; j++) {
if (grid[i][j].isBlack() && grid[i][j + 1].isBlack()) return true;
}
}
return false;
}
private boolean connectedBlacksInColumns() {
/* similar */
}
boolean isConnected() {
Set nonBlackCells = getNonBlackCells();
/* This takes the cells that result to be path connected to the
first non black cell we take into consideration */
Set| reachableCells = nonBlackCells.iterator().next().getReachableCells();
/* If I can reach all non-black cells from any of the other ones,
then they are all path connected. Otherwise, the grid isn't connected. */
return nonBlackCells.equals(reachableCells);
}
}
| | Если мы хотим знать, является ли состояние решением проблемы, то мы просто должны проверить, является ли оно законным и есть ли какие-либо повторения в строках и столбцах (помните? Состояние-это решение, если оно законное и полное ), поэтому мы также добавляем метод растворенный .
public class GameState {
...
private boolean isLegit() {
return !connectedBlacksInRows() && !connectedBlacksInColumns() && this.isConnected();
}
...
boolean isSolved() {
return this.isLegit() && !this.repetitionsInRows() && !this.repetitionsInColumns();
}
private boolean repetitionsInRows() {
Set numbers;
for (int i = 0; i < size; i++) {
numbers = new HashSet<>();
for (int j = 0; j < size; j++) {
if (grid[i][j].isBlack()) continue;
Integer number = grid[i][j].getValue();
if (numbers.contains(number)) return true;
else numbers.add(number);
}
}
return false;
}
private boolean repetitionsInColumns() {
/* similar */
}
Были там, сделали это — мы не тратим время на медленные методы, такие как DFS или BFS.
Уточнение структуры с целью введения обратного хода
Стандартный способ использования Обратного отслеживания заключается в выполнении DFS , во время которого вы обрезаете дерево возможных решений, отбрасывая на лету ветви, которые не соответствуют ограничениям, определенным проблемой. На самом деле, я нахожу гораздо более читаемым поместить обрезку непосредственно в метод, который дает вам следующих возможных кандидатов для решения.
public class GameState {
...
Set getNextStepOptions() {
Set options = new HashSet<>();
Set| cellOptions = getNonColoredCells(); // Neither black nor white
for (Cell c : cellOptions) {
try {
GameState g = c.setBlackAndGetState();
options.add(g);
} catch (ImpossibleStateException ignored) {}
}
return options;
}
}
| Здесь, конечно, дело в блоке try-catch и, в частности, в методе setBlackAndGetState класса Cell , который вызывает исключение ImpossibleStateException всякий раз, когда затемнение этой ячейки приведет к явному невозможному состоянию (например, две соседние черные ячейки или ячейка, которая приводит как к черному, так и к белому).
Конечно, одно это сделало бы все намного быстрее, но, учитывая ограничения, вы сами можете ясно понять, что все еще существует слишком много кандидатов, хотя бы для ограничения связности пути|/.
Я больше не буду ходить вокруг да около по этому вопросу.
Ожидание закончилось. Вот математика.
Что я на самом деле собираюсь здесь сделать , так это вывести и распространить ограничения топологии , но давайте не будем слишком вдаваться в технические подробности. Я просто укажу на пять простых фактов, которые я назову правилами , чтобы отличить их от ограничений игры, которые мне удалось обнаружить и доказать примерно за час. Это значительно повысит скорость.
- Если ячейка черная, все соседние ячейки должны быть белыми. На самом деле это тривиально: не может быть двух соседних черных ячеек.
- Если ячейка белая, все ячейки с одинаковым номером в одной строке или одном столбце должны быть черными. Это следует непосредственно из первого ограничения игры: никаких повторений!
- Если есть шаблон XYX, то Y должен быть белым. Я имею в виду, что если у вас есть три соседние ячейки (например
8 2 8 828 8 2 8 на изображении ниже) тот, что посередине (например,2 2 2 ) должен быть белым. Если бы он был черным в конце игры, основываясь на правиле1 1 1 что мы только что обнаружили, оба “X” (например,8 8 8 ) должно быть белым, но это противоречит первому ограничению игры.
Узор XYX
- Если есть шаблон XX…X…X, то все Xs, не входящие в первую пару, должны быть черными. Аналогично предыдущему пункту. Если один из Xs не входит в первую пару (например, один из синих квадратов
7 7 7 на изображении ниже) были белыми, то, по правилу2 2 2 , два X в паре (например, красный квадрат7 7 7 ) должно быть черным, но (еще раз) не может быть двух соседних черных ячеек.
XX… Х…Х узор
- Если все соседи ячейки, кроме одного, черные, то ячейка белая, и последний сосед тоже белый. Здесь доказательство немного более утомительно из-за углов и боковых квадратов, поэтому я оставлю его читателю. Дело в том, что вы бы отключили вызов от остальной сети.
Если вы хотите, найдите время, чтобы попытаться решить Хитори самостоятельно, и посмотрите, насколько это просто теперь, когда вы знаете эти пять правил.
И вот здесь наступает поворотный момент.
Что мы собираемся сделать, так это просто добавить эти новые фрагменты информации (на самом деле, ограничения) в код, но сначала давайте погрузимся в таинственный метод setBlackAndGetState , который, похоже, выполняет большую часть работы.
public class Cell {
...
GameState setBlackAndGetState() throws GameState.ImpossibleStateException {
if (neighbors.stream().anyMatch(Cell::isBlack))
throw new GameState.ImpossibleStateException(); // Constraint 2
try {
GameState g = new GameState(this.gameState);
g.getGrid()[x][y].setBlack();
/* Constraint 3 */
if (!g.isConnected()) throw new GameState.ImpossibleStateException();
return g;
} catch (AlreadyColoredException e) {
throw new GameState.ImpossibleStateException();
}
}
void setBlack() throws AlreadyColoredException {
if (this.black) return; // Nothing to do here
if (this.white) throw new AlreadyColoredException(); // Both white and black?
else {
this.black = true;
/* Rule 1. */
for (Cell c : neighbors) {
c.setWhite();
}
}
}
void setWhite() throws AlreadyColoredException {
if (this.white) return; // Nothing to do here
if (this.black) throw new AlreadyColoredException(); // Both white and black?
else {
this.white = true;
/* Rule 2. */
for (Cell c : this.getRow()) {
if (c.getValue() == this.value && !c.equals(this)) c.setBlack();
}
for (Cell c : this.getColumn()) {
if (c.getValue() == this.value && !c.equals(this)) c.setBlack();
}
}
}
}
Видишь, что я там делаю? Я применяю первое и второе правила немедленно (и рекурсивно ) каждый раз, когда пытаюсь очернить новый квадрат. Как отмечалось ранее, если это приведет к несогласованному состоянию, я добавлю новый Исключение невозможного состояния . А теперь заключительная часть:
public class GameState {
...
void infer() throws ImpossibleStateException {
GameState original = new GameState(this);
this.inferSurroundedCell(); // Rule 5.
this.inferXYXPattern(); // Rule 3.
this.inferXXYZXPattern(); // Rule 4.
/* If I did change the state, I try to do that again because there could
be that new rules can be applied */
if (!this.equals(original)) this.infer();
}
}
Сам метод BEST (Дерево поиска с обратным отслеживанием) на самом деле находится в Main , это просто сделать как можно больше выводов, прежде чем даже пытаться пойти по новой дороге.
private static GameState BST(GameState state) {
Stack stack = new Stack<>();
stack.push(state);
while (stack.size() != 0) {
GameState element = stack.pop();
/* Note that, apart from this try-catch block, this is the standard BST */
try {
element.infer();
} catch (GameState.ImpossibleStateException e) {
return null;
}
if (element.isSolved()) {
return element;
}
for (GameState g : element.getNextStepOptions()) {
stack.push(g);
}
}
return null;
}
Я поместил ниже три снимка (просто в качестве примера) головоломок Hitori размером 5, 6 и 7 соответственно, чтобы показать, насколько быстро они решаются по сравнению с созданием случайных разрешимых головоломок (что похоже на то, сколько времени займет наивный подход).
Кроме того, обратите внимание, что время для их решения не увеличивается экспоненциально, в отличие от наивного подхода. На самом деле, кажется, что время решения вообще не увеличивается. Из любопытства, вычислить точную сложность алгоритмов, подобных описанному, чрезвычайно сложно.
Размер 5
Размер 6
Размер 7
Я намеревался также разместить снимок размера 8 для наивного подхода, но (по иронии судьбы) он не был завершен вовремя, так что вот только время для решения.
Размер 8
Ладно, звучит неплохо. Но почему я не могу просто использовать машинное/глубокое обучение, Tensorflow или что-то подобное для решения подобных задач?
Дело не в том, что вы не можете, но таким образом вы действительно можете сэкономить много времени, ресурсов и (в конечном счете) денег.
Машинное обучение (почти) любого рода, на самом деле, требует набора данных. А для не популярной темы, такой как история, вам придется создать ее самостоятельно.
Это заняло бы много времени без процесса, который мы только что объяснили (который, в свою очередь , вы действительно можете использовать, чтобы позволить машине узнать о свойстве связности пути, о котором на самом деле заботятся).
Так что, если вы дочитали до этого и все еще задаетесь вопросом, о чем был этот пост, короткий ответ: всегда спрашивайте себя, какие есть варианты, и выбирайте правильный подход . И немного математики(математика) всегда помогает в этом.
О, да. Я также научил вас, как решить головоломку Hitori, изучив некоторые довольно продвинутые концепции и методы искусственного интеллекта. Неплохо.
Вы можете найти полный исходный код (обновленный и обновленный ) здесь .
Оригинал: “https://www.codementor.io/@alessandroflati/why-you-shouldn-t-rely-entirely-on-machine-learning-htgrbk1vu”