Интеллектуальные системы. Алгоритм поиска оптимального хода в игре Крестики-нолики

Уверен, многие успели насладиться великолепным квестом  Machinarium. Вы наверняка помните того робота, которого надо было обыграть в баре, чтобы получить необходимые болтики. Так вот, игра, в которую его надо было обыграть, очень похожа на  крестики-нолики, но имеет поле 10 на 10 и продолжается, пока один из игроков не выстроит ряд из пяти фигурок. Продолжая тему интеллектуальных систем, предлагаю написать алгоритм для игры в крестики-нолики по правилам, предложенным в Machinarium. Сыграть!

Как построить дерево в виде графа

Древовидный граф - распространенная структура данных в программировании и часто применяемая в алгоритмах. Содержимое этой структуры тяжело поддается исследованию во время отладки, в силу того, что практически всегда описывается одним узлом ссылающимся на своих потомков. Т.е. чтобы получить значение некоторого узла, приходится выполнять нетривиальный обход дерева. И тут на помощь может придти визуальное представление такого графа. Построение графа в виде компактного и легко воспринимаемого дерева, задача нетривиальная и имеет безусловно множество решений. В статье хотелось бы поделиться собственным "колесом" для решения этой задачи.

Как в Java сравнить содержимое двух директорий

Возникла необходимость сравнить две директории по содержимому. Готового решения гугл не подсказал, пришлось городить собственное решение. Исходный код boolean compareDirectories(File dir1, File dir2) throws FileNotFoundException { /* Папок нет, разговора нет */ if (!dir1.exists()) throw new FileNotFoundException(dir1.getAbsolutePath()); if (!dir2.exists()) throw new FileNotFoundException(dir2.getAbsolutePath()); /* Аргументы либо оба директории, либо оба файлы. Иначе не схожи. */ if (dir1.isDirectory() != dir2.isDirectory()) { return false; } /* * Если первый аргумент файл, а предыдущая проверка метод не завершила, * то сравниваем аргументы как файлы. */ if (dir1.isFile()) { return compareFilesByName(dir1, dir2); } File[] files1 = dir1.listFiles(); // Здесь жду подвоха. Не факт, что массивы File[] files2 = dir2.listFiles(); // сформируются в одинаковом порядке. // Возможно нужна предварительная сортировка. if (files1.length != files2.length) { return false; } for (int i = 0; i < files1.length; i++) { File f1 = files1[i]; File f2 = files2[i]; /* Рекурсивный вызов */ if (!compareDirectories(f1, f2)) { return false; } } return true; } /* * Критерий совпадения файлов может быть разным. * Например, совпадение имен. */ boolean compareFilesByName(File file1, File file2) { return file1.getName().toLowerCase() .equals(file2.getName().toLowerCase()); }

Интеллектуальные системы. Алгоритм A* и игра "Пятнашки"

Повседневная работа современного программиста редко открывает простор для развития творческого мышления. Чаще всего, для решения задач нам достаточно применить проверенное временем решение: паттерн или библиотеку. Знание общепризнанных подходов и практик, библиотек и фреймворков, вот что сегодня является признаком квалификации программиста. Между тем, красота и волшебство программирования для многих (я уверен, что не одинок в этом) в полной мере раскрывается в решении сложных алгоритмических задач, так редко встречающихся в повседневной практике. И раз уж "гора не идет к Магомету", то Магомет придумает себе задачку самостоятельно!