"Computer Go: An AI Oriented Survey"

Тема в разделе "Машинное отделение", создана пользователем WinPooh, 8 мар 2006.

  1. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    WinPooh, 8 мар 2006
    #1
  2. Kirr
    Оффлайн

    Kirr Команда форума Команда форума

    Репутация:
    8
    Спасибо, очень интересная статья!
     
    Kirr, 8 мар 2006
    #2
  3. atoku
    Оффлайн

    atoku Модератор

    Репутация:
    0
    А может просто занимались не те?
     
    atoku, 8 мар 2006
    #3
  4. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    Вопрос упирается в теорему о существовании "тех" :)
     
    WinPooh, 8 мар 2006
    #4
  5. atoku
    Оффлайн

    atoku Модератор

    Репутация:
    0
    Хочу играть в Го! Давно. Даже книжку купил. Но партия длится очень долго. А когда заниматься чем-то полезным для общества и самолюбия? :)
     
    atoku, 8 мар 2006
    #5
  6. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    Вот некоторые простые оценки сложности Го:

    There is no particular evidence that an increase in computing power is sufficient to make the current programs into world class champions, almost without regard to the computing power available. Given current program skill, the programs would need to look dozens of moves ahead (let's say 30) and try all potentially remotely reasonable moves (lets say 50 moves). Standard alpha-beta routines put that at 50 ^ 15 moves tried and carefully evaluated; that's about 10 ^ 25 or 2 ^ 84. Say a modern computer can evaluate 10 moves a second; further suppose that your future supercomputer is 100 billion times faster (10 ^ 11). This means you can generate a good move in only 10 ^ 13 seconds, or only 300,000 years! Now, relatively standard pruning algorithms for selective searching will significantly cut down the number of nodes tried; to get it down to 1 day per move would require a pruning factor of about 10 ^ 8, which is probably doable. So, if Moore's Law holds for the next 55 years (doubtful), then maybe the standard techniques would produce a professional grade player; I doubt even that would produce a world champion, though. In short, we need more intelligent programming; the go programs are getting better as a result of a lot more than just faster CPUs. A professional quality program within 50 years would not really surprise me; a world champion would.

    http://senseis.xmp.net/?SomePhilosophicalQuestionsAboutComputersAndGo
     
    WinPooh, 9 мар 2006
    #6
  7. mr Life
    Оффлайн

    mr Life баннер

    Репутация:
    1
    Разве в го фигуры не однотипны? Если да, то огромное число последовательностей ходов ведет к одинаковым позициям: оценка ветвления 50 это учитывает?

    Если есть проблема формализации оценки позиции, почему не используются методы распознавания образов?
     
    mr Life, 11 мар 2006
    #7
  8. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    1. учитывает. Я бы даже сказал, что 50 - это ОЧЕНЬ мягкая оценка СНИЗУ...
    2. иногда используются
    3. увы, не работают... то есть работают, но их эффективность для сколь-нибудь сильной игры недостаточна...
     
    WinPooh, 11 мар 2006
    #8
  9. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Мягкая оценка снизу - 2-3....
    Оценка сверху - (Коэфициент ветвления в шахматах)^(1.5) (согласно количеству возможных ходов в каждой позиции) У Рыбки и Шреддера - Коэффициент немногим больше двух...
    Хистори прунинг и метод пустого хода для Го еще никто не отменял.
    Кстати, при такой оценке как приведена в статье - в шахматах при чистой Альфа-бете должен быть коээфициент 20... А он не такой... С хешем перекрестных таблиц чистый негаскаут без иных методов сокращений/отсечений дает максимум 7... (Корень из 50...)
    Сортировать ходы надобно!!!!

    Так откуда ж всё-таки взялась цифра 50? Или в ГО в каждой позиции 2500 возможных ходов?
     
    NS, 7 май 2006
    #9
  10. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    And my program Aya won 9x9 tournament luckily.
    But in 19x19 result was 4 wins and 6 losses.
    I think deep full board search might work well in small Go board.

    Aya search 4-5 plies in 19x19, and 6-7 plies in 9x9.
    Nodes per second is 200-300 nps in 19x19 and 500-600 nps in 9x9
    (Pentium3M 1.13GHz).
    Evaluation function includes strings capture and some connections search.
    Life and death, eye-shape recognition are static.

    Moves are generated from simple stone shape pattern.
    Life and death, eye-shape and connection points from evaluation function
    are also generated.

    The moves around weaker and bigger stones get higher temporary value.

    Number of moves limit each 1,2,3,4,5,6,7 depth are 50,20,10,10,10,10,10.
    In first depth(root) and two depth all moves are generated.
    And over 3 depth, Aya generates only nearby last moves and around getting
    weak stones by last opponent move.

    These idea are mainly from Haruka, Japanese strong Go program's
    explanation.
    There is its PDF (in Japanese)
    http://www.cs.ualberta.ca/~games/go/index.html
    And you can see Mr. Kishimoto's translation.
    http://www.cs.ualberta.ca/~games/go/index.html

    Regards,
    Hiroshi Yamashita

    А Это чтоб не быть совсем голословным.
     
    NS, 7 май 2006
    #10
  11. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    Это понятно, что надо. Вопрос только, как в том анекдоте: "But... how?"

    В шахматах - в простейшем случае - взятия можно отсортировать по стоимости съеденных фигур, по прогнозируемому размену и т.д. В Го это невозможно. Если вы сыграли хотя бы десяток партий в своей жизни, вы понимаете причину. Без счёта разумная сортировка невозможна... Без сортировки невозможен эффективный счёт. Замкнутый круг.

    Теперь насчёт коэффициента. В миттельшпиле в Го возможно сделать 200-300 ходов возможных ходов. Альфа-бета даёт корень из этого числа, он будет в районе 15-18. Вот такой степени ветвистости дерево предстоит усекать. Но! Учтите, что для альфа-беты порядок рассмотрения ходов - критическая величина. А как сортировать ходы - совершенно неясно...
     
    WinPooh, 8 май 2006
    #11
  12. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Хеш лучших ходов + IID...;)
    Ходы, так-же как и в шахматах предварительно можно сортировать по оценке хода без перебора.
     
    NS, 11 май 2006
    #12
  13. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    И кстати, киллер и его вариации (Хистори) тоже должны нормально работать...
     
    NS, 11 май 2006
    #13
  14. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    Вот ещё одна интересная статья по теме:
    http://www.smart-games.com/knowpap.txt - "Knowledge representation in Many Faces of Go"
    Правда, тринадцатилетней давности. Но классику надо знать :)
     
    WinPooh, 11 май 2006
    #14
  15. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    Вот о чём я всё время не устаю повторять. Цитата:

    An accurate evaluation of a Go position must do
    life and death analysis     and assign a value for relative thickness and territory. Just
    Determining the location of secure territory is a difficult problem. A chess
    evaluation is dominated by the values of the pieces remaining on the board,
    which is easy to get right. If a go program misreads a life and death fight
    there would be a large error in the evaluation score. This leads to an
    evaluation function for a go program that is orders of magnitude slower than
    the chess evaluation function. Where a PC chess program can examine 100,000
    positions each move, Many Faces examines less than 100 positions before
    deciding on a move.
     
    WinPooh, 11 май 2006
    #15
  16. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    У меня есть опыт написания шахматных программ на языках в 3000 раз более медленных, чем "нормальные". (150 узлов в секунду получается)
    Я понимаю, что оценочная функция в ГО намного сложнее по написанию, чем в шахматах - но у меня очень приличные знания в теории графов, и у меня есть опыт написания оценочной функции для Гекс-а - а поверь - она тоже очень непроста, и также включает в себя множество алгоритмов по графам.

    И очень устаревшая статья. Тогда не было очень многих методов и эвристик применяемых сейчас, и шахматные программы сейчас смотрят не 100 000 позиций, а миллионы, десятки и сотни миллионов;)))
     
    NS, 11 май 2006
    #16
  17. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    А как применить в Го теорию графов?
    Мне всегда казалось, что она больше заточена на задачи вроде поиска оптимального пути. Для Гекса вот как раз подходит. А что представлять графом в Го?
     
    WinPooh, 11 май 2006
    #17
  18. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Задача поиска наикратчайшего пути, и алгоритмы поиска пути - Это задачи и алгоритмы теории графов;))))
    В гексе - только кратчайшие пути и ищем (цель соединить своими шашками (построить путь) две стороны доски)
     
    NS, 11 май 2006
    #18
  19. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    Да, а в Го?
     
    WinPooh, 11 май 2006
    #19
  20. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    В Го - и конечный подсчет очков (наличие пути к свободной клетке), и простейшая оценочная функция (по расстоянию от поля до камней и края доски) - тоже задачи теории графов. Но в ГО так-же, насколько я понимаю - используют и оценку по положению - аналог SET таблиц. Особенно на краю и в углу доски.
    У меня, например в Anechka - почти вся оценка идёт аналогами Set таблиц. Но есно не вся, а почти вся;)))
     
    NS, 11 май 2006
    #20
  21. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    Set-таблицы = piece-square values?
     
    WinPooh, 11 май 2006
    #21
  22. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Нет, Set таблицы это более широкое понятие. Это нахождение в определенном месте набора фигур/пешек/пустых полей, возможно включение в таблицы битых полей/ битых определенной фигурой/фигурами полей, и задаваться может не конкретное положение на доске, а применяться комбинация фигур относительно некоторого, произвольно взятого поля.
     
    NS, 11 май 2006
    #22
  23. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    Да, в Го без них никуда. Дело в том, что многие стандартные формы - например, "автомобиль" - убиваются стандартным ходом в одну и ту же точку, и каждый раз доходить до этого счётом - только время тратить.
    Базы типовых паттернов должны быть в несколько тысяч конфигураций, как минимум...
     
    WinPooh, 11 май 2006
    #23
  24. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Сейчас я о них пока не думаю - первые варианты будут с простейшей, уже опробованной оценкой.
     
    NS, 11 май 2006
    #24
  25. WinPooh
    Оффлайн

    WinPooh В.М. Команда форума

    Репутация:
    95
    С нетерпением жду работающего прототипа :)
     
    WinPooh, 11 май 2006
    #25
  26. NS
    Оффлайн

    NS Нефёдов Сергей баннер

    Репутация:
    3
    Сейчас идут только наброски и обдумывание - я в основном готовлю версию 0.06 к началу WBEC.
    Как только её закончу - сразу плотно займусь ГО.
     
    NS, 11 май 2006
    #26