Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Алгоритмы
Перезагрузить страницу Как реализовать алгоритм игры?
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
VladStarostenko VladStarostenko вне форума
Новичок
 
Сообщений: 1
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.12.2018
По умолчанию Как реализовать алгоритм игры? - 03.12.2018, 02:54

Добрый день!

Возникла проблема с описанием алгоритма игры при помощи кода.

Если в двух словах, игра такая. Есть поле nxn, где n - четное и в приделе от 11 до 51.
Два игрока по очереди ставят фигурки размером 2х1. Кто не может поставить фигуру - тот и проиграл.
Нужно написать алгоритм для игрока(бота) в этой игре.

Я пришел к такому алгоритму, что нужно контролировать количество клеток на поле. То есть смотреть на четность того, сколько еще фигур можно поставить на поле в данных момент. Если например на поле осталось 10 клеток, это значит что можно поставить 5 фигур, а значит что тот игрок, чей ход - выигрывает в данный момент времени. В случае если игрок проигрывает в данных момент времени, он должен пытаться отделить клетки , чтобы не было возможности их использовать и поменять собственно четность количества клеток на доске.
Надеюсь понятно объяснил свою логику

Дальше я решил найти ситуация (раскладки фигур) на каком-то конкретном участке доски, при которых на сто процентов за 1-2 хода игрок может отделить хотя бы 1 клетку. Ну например если есть клетка и с трех ее сторон уже стоят фигуры, то он может поставить фигурку и с четвертой стороны и она будет отделена.

Собственно в этом моменте возникла проблема с описанием этого алгоритма при помощи кода. Не имею ни малейшего представления как можно запихнуть все эти ситуация в код и как можно сканировать поле на наличие таких участков, где можно отделать клетку.

Даже если сделать например список массивов которые будут хранить в себе эти ситуации, при которых есть возможность отделить клетку, как просканировать все поле на наличие в нем таких ситуаций?

С радостью послушаю вас, если у вас есть в корне другие идеи для решения.

Спасибо!

P.S. Бот должен делать свой ход за пол секунды.
Ответить с цитированием
  (#2 (permalink)) Старый
lomi lomi вне форума
Новичок
 
Сообщений: 2
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 02.12.2018
По умолчанию 03.12.2018, 04:47

Есть аналогичная игра с монетками на круглом столе. Там нужно класть первую монетку в центр, а дальше зеркально отображать каждый ход второго игрока. Если он может положить монетку, то и ты сможешь.
Но это - выигрыш за одну из сторон. Как написать выигрышную стратегию на случай ошибки противника - отдельный вопрос.

Попробуйте написать алгоритм полного перебора для поля 4x4 (легко влезет в оперативную память) и собрать два Set<Integer> winningIDs и Set<Integer> losingIDs. Здесь unsigned int iD - это зашифрованное побитно поле, где занятые биты - это единицы, а незанятые - это нули. Можете проделать то же самое с полем 4x8. 4x4 точно влезет в память, если использовать depth first search. Я так решал мини шашки 6x6. дальше поиграйте с компом и посмотрите на закономерности. Наверняка заметите какие-то паттерны.
Ответить с цитированием
  (#3 (permalink)) Старый
Alexiski Alexiski вне форума
Любитель давать советы
 
Сообщений: 4,280
Сказал(а) спасибо: 27
Поблагодарили 54 раз(а) в 54 сообщениях
Регистрация: 16.10.2005
По умолчанию 03.12.2018, 13:14

Если n таки чётное, то для второго игрока выигрышная стратегия - повтор ходов симметрично от центра поля.
Ответить с цитированием
Ads
Ответ

Метки
java , алгоритм , игра

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как реализовать алгоритм модулярного умножения SvetofoRik Вопросы начинающих программистов 0 13.09.2010 22:40
Требуется реализовать алгоритм Брезенхема для окружности vakso Lisp 2 03.06.2010 12:46
Люди, нужно реализовать Алгоритм Дейкстры bar7 Задания за деньги 1 14.12.2009 20:30
Реализовать на Lisp алгоритм Маркова xmtgx Lisp 16 01.06.2009 19:54
реализовать алгоритм на с++ Kishara С/С++ 0 24.02.2009 22:07
Помогите реализовать алгоритм vilza Pascal 1 27.01.2007 14:16
Алгоритм получения целевой расстановки для игры 15 Anonymous Алгоритмы 20 18.08.2006 12:22
Пятнашки как найти алгоритм создания игры wwwslavan Игры разума 16 18.07.2006 20:44
Как реализовать алгоритм сжатия Кэлен Delphi 0 21.05.2006 00:32
Как реализовать алгоритм RSA АЛЬБИНА Pascal 11 20.03.2006 21:37
Алгоритм фамилия1-фамилия2 как реализовать tokito Алгоритмы 0 01.10.2004 11:33
Как написать алгоритм игры Anonymous Алгоритмы 0 10.06.2003 21:36



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов