OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Понедельник, 23 Сентябрь, 2019 04:31

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 13 ] 
Автор Сообщение
 Заголовок сообщения: Игра "Точки"
СообщениеДобавлено: Суббота, 29 Август, 2009 02:02 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9141
Откуда: Россия, Орёл
Собственно:
http://oberoncore.ru/wiki/blackbox/ex/points_game

Инициирующим обсуждением было вот это:
viewtopic.php?f=27&t=1750


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Игра "Точки"
СообщениеДобавлено: Среда, 02 Сентябрь, 2009 14:15 

Зарегистрирован: Суббота, 09 Декабрь, 2006 08:56
Сообщения: 35
Откуда: Беларусь
А выбор игрока? Компьютер-пользователь?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Игра "Точки"
СообщениеДобавлено: Среда, 02 Сентябрь, 2009 19:07 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9141
Откуда: Россия, Орёл
Ууу, батенька :)

Поставили задачку :)

Это позиционная игра. Упрощение японской Го.

Они традиционными методами перебора по дереву вообще не обсчитываются. Даже с отсечениями-эвристиками. Просто дикий комбинаторный взрыв (посчитайте число возможных вариантов первого-второго-третьего хода - и прикиньте порядок факториала).
За программу, играющую в Го на уровне любителя (японского школьника) обещана нефиговая премия.

Кстати, автор программы будет заниматься (в качестве студенческой НИР и диплома) системой принятия решений для таких игр. Очень интересная тема :) Переборы перестают работать, нужно учиться формулировать явные правила позиционного поведения. Общего способа "считать позиционно" быть просто не может; а вот подход к анализу и построению логики под каждую конкретную задачу наработать бы хотелось.

Ситуация, кстати, чем-то напоминает комп. лингвистику (с задачей точного извлечения содержания текста; а не поиска "широким неводом" типа поисковиков). Сначала "ИТ-партизанам" казалось (и до сих пор кажется), что не надо думать о языке, а надо накладывать стат. методы, нейронные сети и прочую хрень, что "оно само считало методом бубна". А оказалось, что надо просто становится лингвистом и закладывать, закладывать в машину уйму точной явно прописанной логики. И хошь бы одна нейронная сеть пригодилась... :)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Игра "Точки"
СообщениеДобавлено: Четверг, 03 Сентябрь, 2009 15:40 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3067
Откуда: Астрахань
А не посмотреть ли вам Ботвинника с его Пионером. Помнится у него было такое понятие как "траектория". ИМХО, весьма близко.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Игра "Точки"
СообщениеДобавлено: Четверг, 03 Сентябрь, 2009 17:39 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9141
Откуда: Россия, Орёл
Спасибо, надо будет глянуть.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Игра "Точки"
СообщениеДобавлено: Вторник, 08 Сентябрь, 2009 16:47 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
По тексту программы видно, что студент не знает законов де Моргана или не умеет ими пользоваться. Это большой минус руководителю :wink:
Код:
WHILE (y < LEN(поле, 1)-1) & ~( ~Волна_рядом(волна, x, y) & (поле[x, y].область = NIL) ) DO
WHILE (y < LEN(поле, 1)) & ~( (поле[x, y].точка_игрока # -1) & (поле[x, y].поставлена_на_ходе = номер_хода) ) DO
WHILE  усп & ~( (sc.type = Tm.char) & (sc.char = '#') OR (sc.type = Tm.eot) )  DO
WHILE (w # NIL) & ~ ( Графика.Эта_игра(w.doc.ThisView()) # NIL ) DO
WHILE ~rd.eot & ~ ( (rd.char # " ") & (rd.char # TextModels.tab) ) DO
WHILE ~rd.eot & ~ ( (rd.char = " ") OR (rd.char = TextModels.tab) ) DO
WHILE (w # NIL) & ~ ( Графика.Эта_игра(w.doc.ThisView()) # NIL ) DO
Советую в воспитательных целях предложить раскрыть все отрицания.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Игра "Точки"
СообщениеДобавлено: Вторник, 08 Сентябрь, 2009 17:29 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2311
Откуда: Россия, Томск
Peter Almazov писал(а):
По тексту программы видно, что студент не знает законов де Моргана или не умеет ими пользоваться.
Хе-хе. : ) Всё правильно написал студент. Настолько правильно, что непривычно. Илье +1 за руководство.

Подсказка: вспомните линейный поиск.
WHILE A & ~B DO
...
END;
IF A THEN (* B = TRUE, найдено *)
ELSE (* не найдено, B не определено *)
END;

Пример:
WHILE (i < LEN(str)) & ~(str[i] = 0X) DO
INC(i);
END;
IF i < LEN(str) THEN (* str[i] = 0X *)
ELSE (* символ 0X не найден *)
END;

Конъюнкт B в условии цикла пишется с явным отрицанием, чтобы было сразу видно, что ищется (т.е. какое условие должно выполниться при успешном завершении поиска).


Последний раз редактировалось Александр Ильин Вторник, 08 Сентябрь, 2009 20:53, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Игра "Точки"
СообщениеДобавлено: Вторник, 08 Сентябрь, 2009 17:53 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Александр Ильин писал(а):
Peter Almazov писал(а):
Подсказка: вспомните линейный поиск Дейкстры.
На этом форуме много говорится про т.н. "Линейный поиск", это верно. Но дело в том, что к Дейкстре (и Грису тоже) это не имеет никакого отношения. Возьмите книги и вспомните сами.
Вот Вам в помощь: viewtopic.php?p=29531#p29531 и viewtopic.php?p=29586#p29586
Верю, что Вам нравится выделять коньюнкты с отрицанием. Но Дейкстру сюда приплетать не надо.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Игра "Точки"
СообщениеДобавлено: Вторник, 08 Сентябрь, 2009 19:46 

Зарегистрирован: Суббота, 26 Ноябрь, 2005 18:38
Сообщения: 1857
Александр Ильин писал(а):
Конъюнкт B в условии цикла пишется с явным отрицанием, чтобы было сразу видно, что ищется (т.е. какое условие должно выполниться при успешном завершении поиска).


Чтобы было сразу видно, что ищется, используется не WHILE с необозримым условием, а что-нибудь более выразительное. Впрочем ладно, не обращайте внимания... ;)


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Игра "Точки"
СообщениеДобавлено: Вторник, 08 Сентябрь, 2009 20:06 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9141
Откуда: Россия, Орёл
Peter Almazov писал(а):
На этом форуме много говорится про т.н. "Линейный поиск", это верно. Но дело в том, что к Дейкстре (и Грису тоже) это не имеет никакого отношения.


Да, это так.

Линейный поиск у Дейкстры - это поиск с гарантированным исходом, т.е. без двух вариантов окончания.

И вообще, как я уже говорил - теория Дейкстры так же соотносится с паттернами "полный проход" и "линейный поиск", как, к примеру, общий аппарат исследования поведения функций с частным аппаратом линейного программирования.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Игра "Точки"
СообщениеДобавлено: Вторник, 08 Сентябрь, 2009 21:09 
Аватара пользователя

Зарегистрирован: Вторник, 19 Сентябрь, 2006 21:54
Сообщения: 2311
Откуда: Россия, Томск
Peter Almazov писал(а):
дело в том, что к Дейкстре... это не имеет никакого отношения.
Поправил своё сообщение выше.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Игра "Точки"
СообщениеДобавлено: Вторник, 08 Сентябрь, 2009 21:35 

Зарегистрирован: Пятница, 24 Апрель, 2009 16:28
Сообщения: 530
Откуда: Москва
Илья Ермаков писал(а):
Да, это так.
...
И вообще, как я уже говорил - теория Дейкстры так же соотносится с паттернами "полный проход" и "линейный поиск", как, к примеру, общий аппарат исследования поведения функций с частным аппаратом линейного программирования.
А URL есть? Интересно почитать, даже не ожидал, что здесь у нас полный консенсус.
А все-таки интересно, чем вызваны нераскрытые отрицания - подгонкой под некий шаблон или чем-то другим.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Игра "Точки"
СообщениеДобавлено: Вторник, 08 Сентябрь, 2009 22:11 
Модератор
Аватара пользователя

Зарегистрирован: Понедельник, 14 Ноябрь, 2005 18:39
Сообщения: 9141
Откуда: Россия, Орёл
Про паттерны - здесь: http://oberoncore.ru/wiki/%D0%BF%D0%B0% ... 0%BE%D0%B2 - и изначально у Ткачёва (там внизу ссылка на PDF с И-21 есть).

Отрицание вызвано следованием схеме WHILE не_конец & ~( условие поиска), а схема вызвана тем, что построение такого цикла логично начинать с формулировки условия на искомую ситуацию, а условие обычно вытекает прямо из мат. постановки - утверждения о существовании (квантор E), которое должно быть подтверждено или опровергнуто линейным поиском.


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1


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

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2019, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB