StarCraft=Lemmings=PacMac
avatar

LimYoHwan

flag race

9014

min

|

217

sup

|

0

gas
1126
30




Итальянец Джованни Вильетта из Пизанского университета подсчитал вычислительную сложность известных компьютерных игр.
... <бла-бла-бла что-то умное от итальянца>
Полный список результатов выглядит следующим образом:
1 Boulder Dash (1984) - сложность NP
2Deflektor (1987) - сложность L
3Doom (1993) - сложность PSPACE
4Lemmings (1991) - сложность NP
5Lode Runner (1983) - сложность NP
6 Mindbender (1989) - сложность NL
7 Pac-Man (1980) - сложность NP
8 Pipe Mania (1989) - NP-полная игра
9 Prince of Persia (1989) - PSPACE-полная игра
10Puzzle Bobble 3 (1996) - NP-полная игра
11 Skweek (1989) - NP-полная игра
12 Starcraft (1998) - сложность NP
13 Tron (1982) - сложность NP
Источник

Я чесскать не понял ни жуя, но ведь среди Кузян есть честные информатики-математики с красными дипломами. Мож разрулите, что итальянец доказал-то? оО

Комментарии

avatar Tрехглозый flag race

17546

min

|

589

sup

|

0

gas
16:45 31.01.2012
avatar Tрехглозый flag race

17546

min

|

589

sup

|

0

gas
16:46 31.01.2012

Полагаю, он всё же имел ввиду сингл режим, где враг действует шаблонно--
avatar Clockware flag race

5162

min

|

145

sup

|

0

gas
16:48 31.01.2012

интересно, если бы 5 лет назад я начал писать AI для BW, я бы уже закончил? :s15:
впрочем, сам AI я бы с удовольствие попробовал бы реализовать. мне больше неясен вопрос с интеграцией этого самого AI
avatar rрант в кране flag race

24962

min

|

495

sup

|

0

gas
17:44 31.01.2012

Obseg пишет:
интересно, если бы 5 лет назад я начал писать AI для BW, я бы уже закончил?
впрочем, сам AI я бы с удовольствие попробовал бы реализовать. мне больше неясен вопрос с интеграцией этого самого AI


http://reps.ru/forum.php?topic=31943&page=1
avatar Clockware flag race

5162

min

|

145

sup

|

0

gas
17:58 31.01.2012

theleo_ua пишет:
http://reps.ru/forum.php?topic=3...943&page=1
вот и я о том же. вопрос интеграции решён к 2011му :s14:
да и это микро только. хоть и интеллект, но он хуйня.
нужен такой AI, который может прогнозировать сам по себе результат от встречи группировок войск без самого процесса.
просто вспомнилось время, когда я в качестве упражнения думал над тем, как это вообще можно сделать, если бы передо мной стояла такая задача.
avatar Viktor flag race

41000

min

|

1443

sup

|

0

gas
18:14 31.01.2012


avatar Navern flag race

12822

min

|

419

sup

|

0

gas
18:38 31.01.2012

Obseg пишет:
интересно, если бы 5 лет назад я начал писать AI для BW, я бы уже закончил?
впрочем, сам AI я бы с удовольствие попробовал бы реализовать. мне больше неясен вопрос с интеграцией этого самого AI

Недавно видел бота реализованного для старкрафт 2, который работает от перехвата графики. Он использует разницу в цветах и анализирует текущие текстуры, способен развивать высокий апм и т.д. и т.п. Прикольная штука, хотя стратегию в него автор не заложил.
avatar Navern flag race

12822

min

|

419

sup

|

0

gas
18:47 31.01.2012

Obseg пишет:
вот и я о том же. вопрос интеграции решён к 2011му
да и это микро только. хоть и интеллект, но он хуйня.
нужен такой AI, который может прогнозировать сам по себе результат от встречи группировок войск без самого процесса.
просто вспомнилось время, когда я в качестве упражнения думал над тем, как это вообще можно сделать, если бы передо мной стояла такая задача

найди недавно прошедший конкурс Google AI challenge там была похожая задача с муравьями. Там очень всё на стратегию смахивало, но не было разнородных войск. То есть все войска одного типа, карту видят только твои войска(типо туман войны). Нужо бороться за еду(захватывать её) , защищать свои муравейники и уничтожать чужие. Там очень интеерсно почитать как это реализовывали другие люди, особенно победители.
avatar rрант в кране flag race

24962

min

|

495

sup

|

0

gas
19:45 31.01.2012

Obseg пишет:
нужен такой AI, который может прогнозировать сам по себе результат от встречи группировок войск без самого процесса.
просто вспомнилось время, когда я в качестве упражнения думал над тем, как это вообще можно сделать, если бы передо мной стояла такая задача.


ты имеешь в виду, что нет таких инструментов, которые позволяли бы "прогонять текущую BW игру на лету до конца" по аналогии с "рекурсивным рассчетом шахматного дерева ходов" ?
avatar Navern flag race

12822

min

|

419

sup

|

0

gas
20:40 31.01.2012

theleo_ua пишет:


ты имеешь в виду, что нет таких инструментов, которые позволяли бы "прогонять текущую BW игру на лету до конца" по аналогии с "рекурсивным рассчетом шахматного дерева ходов" ?

даже шахматы в самом начале нельзя нормально рекурсивно просчитать до конца. В начале вроде используется база всех ходов(ну типо там французский дебют и прочая фигня название которой я не знаю).
avatar LimYoHwan flag race

9014

min

|

217

sup

|

0

gas
20:47 31.01.2012

theleo_ua пишет:
ты имеешь в виду, что нет таких инструментов, которые позволяли бы "прогонять текущую BW игру на лету до конца" по аналогии с "рекурсивным рассчетом шахматного дерева ходов" ?

я хоть и не спец в информатике и математике, но уверен на 1000%, что любой современной вычислительной системы, как то "супер-компьютер" НЕ хватит, чтобы просчитать все вероятные последовательности событий и конечный результат в Старкрафте. И вот почему. Есть такое понятие в физике, как "степень свободы". Так вот если применить его к играм, то старкрафт в этом несравнимо сложнее, к примеру, шахмат.
Поэтому, врят ли Грубая Сила подойдет вообще для AI.
avatar Navern flag race

12822

min

|

419

sup

|

0

gas
20:49 31.01.2012

LimYoHwan пишет:
я хоть и не спец в информатике и математике, но уверен на 1000%, что любой современной вычислительной системы, как то "супер-компьютер" НЕ хватит, чтобы просчитать все вероятные последовательности событий и конечный результат в Старкрафте

Кстати в этом основное отличие шахмат и старкрафта. Как известно в Го(японский аналог шахмат) компьютер может победить максимум среднего игрока, но хороших никогда. В шахматах сразу дан весь набор фигур и к концу партии он только уменьшается, в Го же выставляются камни на доску(19х19 что в сумме 361 поле, если кто не знал), а в старкрафте появляются новые войска. Так что по идее нужно еще хорошие оценочные функции сделать, чтобы отсекать ненужные пути рекурсивного решения. Так что сомневаюсь я в этом деле.
avatar Navern flag race

12822

min

|

419

sup

|

0

gas
21:19 31.01.2012

http://brunneng.blogspot.com/

блог второго места Google AI challenge.
avatar rрант в кране flag race

24962

min

|

495

sup

|

0

gas
21:22 31.01.2012

LimYoHwan пишет:
я хоть и не спец в информатике и математике, но уверен на 1000%, что любой современной вычислительной системы, как то "супер-компьютер" НЕ хватит, чтобы просчитать все вероятные последовательности событий и конечный результат в Старкрафте.


здесь да - согласен

пока только через нейронные сети вариант имхо


avatar KT Champions! flag race

4071

min

|

68

sup

|

0

gas
21:22 31.01.2012

Не сомневайтесь в этих делах :s4:
Если кто не в курсе - шашки уже посчитаны.
Шахматы на несколько порядков сложнее шашек, но в связи с геометрической скоростью роста вычислительных мощностей их посчитают в ближайшие годы.
Го сложнее шахмат на несколько порядков, но их тоже посчитают. Это неизбежно.
avatar KT Champions! flag race

4071

min

|

68

sup

|

0

gas
21:23 31.01.2012

LimYoHwan пишет:
И вот почему. Есть такое понятие в физике, как "степень свободы". Так вот если применить его к играм, то старкрафт в этом несравнимо сложнее, к примеру, шахмат.

Все упирается в конечность вариантов, так что один хрен посчитают. И кстати вряд ли старкрафт сложнее шахмат.
avatar rрант в кране flag race

24962

min

|

495

sup

|

0

gas
21:24 31.01.2012

Navern пишет:
Так что по идее нужно еще хорошие оценочные функции сделать, чтобы отсекать ненужные пути рекурсивного решения.


даже в шахматах непросто эту функцию сделать (хоть и реально)
avatar Navern flag race

12822

min

|

419

sup

|

0

gas
21:31 31.01.2012

theleo_ua пишет:


даже в шахматах непросто эту функцию сделать (хоть и реально)

Да самый прикол в том, что их можно еще с расчетом на разные вещи делать. С расчетом на стопроцентную уверенность или на ошибки противника. Предсказание вообще вещь сложная. И получается, что бот чаще будет выбирать 100% решения, даже если бы рискованное дало ему гарантированную победу но в 25% случаев.

KT Champions! пишет:
Го сложнее шахмат на несколько порядков, но их тоже посчитают. Это неизбежно.

почему ты так думаешь? Учитывая, что шахматы нормалньо не посчитали до сих пор. Го во много раз имеет больше фигур и они появляются, а они пропадают. То есть тут работа даже другого характера на мой взгляд.
avatar KT Champions! flag race

4071

min

|

68

sup

|

0

gas
21:39 31.01.2012

Navern пишет:
почему ты так думаешь?

Я не думаю в данном случае. Это факт.
В шашках 5х10^20 возможных ходов - полностью посчитаны.
В шахматах 10^46
В го 10^100

Это вопрос лишь вычислительных мощностей.
avatar rрант в кране flag race

24962

min

|

495

sup

|

0

gas
21:50 31.01.2012

KT Champions! пишет:
Не сомневайтесь в этих делах
Если кто не в курсе - шашки уже посчитаны.
Шахматы на несколько порядков сложнее шашек, но в связи с геометрической скоростью роста вычислительных мощностей их посчитают в ближайшие годы.
Го сложнее шахмат на несколько порядков, но их тоже посчитают. Это неизбежно.


вопрос: когда посчитают старкрафт?
avatar rрант в кране flag race

24962

min

|

495

sup

|

0

gas
21:51 31.01.2012

Navern пишет:
Го во много раз имеет больше фигур и они появляются, а они пропадают.


не понял фразы
avatar Navern flag race

12822

min

|

419

sup

|

0

gas
23:24 31.01.2012

theleo_ua пишет:

не понял фразы

бля хера я ахинею написал :s3: :s3: :s3:

Короче. В шахматах все фигуры сразу на столе. Новых появиться не может(редкую ситуацию с превращением пешки не считаем, тут меняется ценность фигуры). В Го изначально доска пустая и с каждым ходом заполняется. В конце партии Го доска будет полностью заполнена. Такие ситуации сложнее считать.
avatar Navern flag race

12822

min

|

419

sup

|

0

gas
23:28 31.01.2012

KT Champions! пишет:

Это вопрос лишь вычислительных мощностей.

http://ru.wikipedia.org/wiki/%D0%98%D0%B3%D1%80%D0%B0_%D1%81_%D0%BF%D0%BE%D0%BB%D0%BD%D0%BE%D0%B9_%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D0%B8%D0%B5%D0%B9

всё почитал статью про игры с полной информацией(если это не ты её написал конечно). Согласен, только не понял откуда взялись числа :s10:
avatar Clockware flag race

5162

min

|

145

sup

|

0

gas
03:31 01.02.2012

Navern пишет:
http://brunneng.blogspot.com/
оке.
в шахматах рыбка, например, считает примерно с глубиной в 50 ходов, хотя в коммандной версии AI это всё настраивается. в среднем битва двух комп. титанов(опять же, рыбок) длиться от 70-120ходов(те, которые вообще привели к массивным разменам)
тяжело представить себе AI без каких-либо графов.
поэтому я представлял себе 2 разделения:
- AI "реального времени"
- AI стратегический, общего назначения.
суть:
противники оцениваются набором групп. AI общего назначения просто направляет развитие дерева исходя из имеющихся о себе и развед данных. а если развед. данных - нет, то на общей основе(т.е. от локации до локации)
суть расчёта:
разведка показала, что на юге у противника стоит 12 маринчиков с медиками. у этой группировки есть возможности передвижения. если представить группу статически, то со временем у неё как бы расширяется "область покрытия" т.е. площадь вообще всех тех мест, где они могли быть через 5, 10, 20 секунд и т.д.
при расширении этого покрытия группировка рано или поздно достигнет юнитов AI. тут-то он фиксирует стычку(событие). и передаёт данные в AI реального времени. AI реального времени считает исход битвы(он же её и ведёт в реальной стычке) и возвращает результаты обратно(время, потери, и т.д.) стратегический в свою очередь производит оценку этих действий и продолжает дерево событий.

а теперь представим, что над 12 маринами на север есть 4 люркера, закопанные горизонтально(ждут). и допустим, что расположение этих маринов интеллектом зафиксировано единожды.
AI будет считать, что марины могут сразу двинуть на север, но тогда проиграют. поэтому не выкапывает люров. но проходит немного времени - и AI высчитает, что за это время люров можно обойти с краю, и стычка будет проиграна. поэтому он выкапывает их и отступает(хотя марины мб воще ушли нахуй и не знали ничего)

как-то так.
надо учесть то, что в шахматах используются мощные продвинутые системы по чистке ходов от заведомо не нужных, как своих, так и соперника. за счёт этого и достигается производительность.
в старкрафте самое сложное это произвести оценку любого события. это вообще хуй знает и пиздец. в SC понятия мата расплывчато. наверное, как ни крути - уничтожение единиц.
опыт на шахматах показал, что AI, контрящий худший для себя случай - мощный. проблема в этом разворачивается в том, что ходы против себя он может также посчитать только сам(и оценить их). а иначе придётся считать все.
avatar Rus_Brain flag race

15060

min

|

700

sup

|

0

gas
06:41 01.02.2012

Бро, так твой пример это машинная логика в чистом виде, и она не неправильная.

Варианты:
1) если AI оставит люру и марины пропушат эксп в обход - вероятность проебать увеличивается на 25%
2) если AI перекопает люру, вероятность ее перехвата и окружения, и как следствие проеба 5%
3) если марики будут пойманы люрой, это увеличит шанс победы на 25%
Сравниваются варианты 1 и 3, шанс что произойдет первый - 67%, шанс третьего 33%
решение - вариант 2, для уменьшения вероятности проебать
avatar Clockware flag race

5162

min

|

145

sup

|

0

gas
06:56 01.02.2012

я понимаю, что ты цифры условные привёл, но чем вариант 2 плох? мой граф не призывает ни к каким конкретным действиям без гарантии победы.
растёшь, выживаешь, делаешь беспроигрышные ходы, а при обнаружении инвариантного пути к победе - идёшь и убиваешь. так и надо по-моему.
avatar Rus_Brain flag race

15060

min

|

700

sup

|

0

gas
07:10 01.02.2012

Так же. Тоже выбираю те ходы, где шанс лося минимальный; а не где есть маленький шанс 100% победы. Поэтому выбор - вариант 2 :)
avatar CocoK flag race

17313

min

|

541

sup

|

0

gas
09:42 01.02.2012

Navern пишет:
найди недавно прошедший конкурс Google AI challenge там была похожая задача с муравьями. Там очень всё на стратегию смахивало,

найс... билни

http://aichallenge.org/visualizer.php?game=346264&turn=150


кстате второе место занял чел или команда из Ю.Корее .. совпадение ?
avatar Navern flag race

12822

min

|

419

sup

|

0

gas
00:03 02.02.2012

Rus_Brain пишет:
Так же. Тоже выбираю те ходы, где шанс лося минимальный; а не где есть маленький шанс 100% победы. Поэтому выбор - вариант 2 :)

стратегия минимакса кажись называется.

Добавить комментарий

Авторизуйтесь чтобы отправить комментарий