Введение
Я — студент Томского Политехнического Университета, первый курс. По предмету нам задали сделать бота для игры, которая полностью повторяет игру Hexxagon, за исключением поля. Поле у нас квадратное, а не гексагональное. В статье будет описан самый простой алгоритм, который с легкостью победит рандомного бота. Если тема будет интересна, то я буду продолжать.
Что мы имеем?
Визуализатор, написанный на C# для того, чтобы можно было устраивать битву ботов, ведь групп по этому заданию много. Визуализатор представляет собой саму игру, которая читает output.txt (туда мы будем делать ходы), а так же переписывает input.txt (переписывает поле, далее подробнее).
input.txt
В этом текстовом файле будет храниться расположение вражеских фишек, своих фишек, а так же пустых и недоступных клеток. На начало игры он представляет собой квадратное поле размером 12х12:
Где,
. — свободная клетка
# — неиспользуемая клетка
1 — наша фишка
2 — вражеская фишка
К концу игры, ситуация, очевидно, меняется и выглядит это примерно так:
Output.txt
Сюда мы записываем ходы наших ботов в таком формате:
2 2
2 3
Четыре числа, разделенные любыми пробельным символами. Первые два отвечают за координату i,j откуда мы собираемся делать ход, последующие два отвечают за координату куда мы собираемся походить. Все просто до боли.
По какому принципу будет работать наш бот?
Тут все просто. Бегая по полю, мы ищем все наши фишки, как только находим первую, тут же проверяем всевозможные ходы, а их может быть максимально 24, по окончанию проверки, задаем вес хода, согласно количеству фишек, которые могут быть «съедены». После оценки и записи этого всего в массив ходов, перебираем этот массив и выбираем ход с наибольшим весом.
Реализация
Так как нам отведено довольно таки большое количество памяти и времени на выполнение (256 мб, 10 секунд) мы не гонимся за быстродействием (пока), по этому я принял решение взять самый простой язык — C#.
Шаг 1
Нам нужно знать какие клетки заняты, а какие нет, для этого создадим массив boolan размерностью 144 (12 x 12), перебирая все поле, выставляем true там, где на поле стоит точка, а где стоит любой другой символ, соответственно, false. Так же нам необходимо знать где располагаются наши фишки, ведь нам нужно принимать решения, исходя из положения наших фишек относительно других, вражеских. Я реализовал это вот так:
static void initialization()
{
field = System.IO.File.ReadAllLines("input.txt");
for (int i = 0; i < 12; i++)
{
for (int j = 0; j < 12; j++)
{
if (field[i][j].Equals('.'))
{ cleanTurns[i, j] = true; }
else
{
cleanTurns[i, j] = false;
if (field[i][j].Equals('1'))
{ myChip[count] = i + ";" + j; count++; }
}
}
}
}
Шаг 2
Проверяем все свободные клетки в зоне досягаемости, если место пустое, то оцениваем его по количеству фишек, которые мы можем съесть. Проверка свободных ходов:
static void isVoid()
{
string[] data;
for (int i = -2; i <= 2; i++)
{
for (int j = -2; j <= 2; j++)
{
for (int k = 0; k < count; k++)
{
data = myChip[k].Split(';');
try
{
if (cleanTurns[int.Parse(data[0]) + i, int.Parse(data[1]) + j].Equals(true))
{
rateTurn(int.Parse(data[0]) + i, int.Parse(data[1]) + j, int.Parse(data[0]), int.Parse(data[1]));
}
}
catch { }
}
}
}
}
Оценка хода по количеству потенциальных жертв:
static void rateTurn(int i, int j, int f, int g)
{
double weight = 0;
for (int q = -1; q <= 1; q++)
{
for (int w = -1; w <= 1; w++)
{
try
{ if (field[i + q][j + w].Equals('2'))
{
weight++;
turnProp[countt] = (i + 1) + ";" + (j + 1) + ";" + weight + ";" + (f + 1) + ";" + (g + 1);
}
}
catch { }
}
}
countt++;
}
Шаг 3
Нам осталось лишь найти максимальный вес хода и сделать ход. Сделаем это так:
static void makeTurn()
{
double maxweight = 0;
int maxweightNum = 0;
for (int i = 0; i < countt; i++)
{
try
{
if (double.Parse(turnProp[i].Split(';')[2]) > maxweight)
{
maxweight = double.Parse(turnProp[i].Split(';')[2]);
maxweightNum = i;
}
}
catch { }
}
System.IO.File.WriteAllText("output.txt", turnProp[maxweightNum].Split(';')[3] + " " + turnProp[maxweightNum].Split(';')[4] + "rn" + turnProp[maxweightNum].Split(';')[0] + " " + turnProp[maxweightNum].Split(';')[1] + "rn");
}
Итог
В конце концов у нас получается бот, который прыгает туда, где он больше всего может отхватить. На данном этапе бот слишком глуп, чтобы побеждать какое-либо решение хотя бы с маломальской логикой, зато он прекрасно расправляется с рандомным ботом. На самом деле у меня уже есть решение, которое действительно как-то думает, но пока выкладывать его я не вижу смысла по двум причинам: 1. возможно этот материал никому не будет интересен; 2. так как задание дано на данный момент времени, то мои «противники» могут прочитать эту самую статью, тем самым они узнают алгоритм нашей команды. Но если тема действительно интересна, то ближе к маю я напишу еще одну статью о том как будет лучше реализовать логику, а так же как оптимизировать процесс.
Спасибо за внимание.
Автор: Pjeroo
