Программирование Го

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

Страница 1 из 14
  1. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Решил сделать отдельный топик по программированию Го. А то соседние топики переполняются оффтопиком :)

    Мои планы:

    - сделать оболочку для двух движков с минимальной поддержкой GTP (1 - 2 недели)
    - посмотреть как играют движки
    - сделать свой движок (думаю будет через месяц)
    - постараться усилить движок, чтобы обыгрывал движок NS
    - попробовать замочить буржуйские движки :)

    WinPooh!
    В шахматы проги тоже плохо играют. Ну и что, что люди еще хуже?
    Я, вообще, соревнования человек-машина не особо люблю. Машины должны играть с машинами, а люди с людьми. С этой точки зрения программирование Го вполне интересно.

    Современный подход к Го напоминает 60-ые годы в программировании шахмат:
    - ОФ не сделать (обошлись же как то без нормальной ОФ).
    - полный перебор вообще не стоит и пытаться сделать (все получилось наоборот)

    Все современные Го-программы это что-то похожее на Ботвинниковский Пионер. Может быть в Го существует более продуктивный подход?
    WildCat, 11 май 2006
    #1
  2. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Основные идеи ОФ я придумал. Осталось очень большая проблема: определение мертвых камней. Без решения этой проблемы ОФ будет тупить и перебор не поможет.
    Тут надо что-то по типу шахматного ФВ.
    WildCat, 11 май 2006
    #2

  3. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Я уже писал каким образом строю ФВ;)).
    в ФВ разрешены ходы - присоединение камня к группе имеющей только одну степень свободы, таким образом что количество степеней увеличивается (становится не меньше двух), ход Убивающий камень/группу соперника, и ход ставящий камень/группу соперника в Атари (остается только одна степень свободы)
    Определение мертвых групп есно перебором.
    После пустого хода в ФВ - группы имеющие только одну степень свободы снимаются с доски (за обе строны), и только после этого производится оценка позиции.
    В Го очень большое значение имеет очередь хода - поэтому нужно думать подходит ли симметричная, чисто статистическая оценка.
    Камень на поле - всегда дает одно очко. Пустая клетка - в интервале [-1..1]
    ЗЫ. Группа - есно горизонтальное/вертикальное соединение камней, степени свободы - есно тоже горизонтальные/вертикальные.
    NS, 11 май 2006
    #3
  4. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    >Определение мертвых групп есно перебором.
    Глобальным?
    WildCat, 12 май 2006
    #4

  5. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.490
    Симпатии:
    3.108
    Репутация:
    95
    Адрес:
    Москва
    Оффлайн
    :)

    Конечно, придётся глобальным :lol:

    Ведь на статус локальной группы может влиять каждый из свободных пунктов доски. Через лестницы и/или ко-борьбу. Впрочем, если демонстративно отказываться от изучения хотя бы основ теории Го, то понять это непросто...
    WinPooh, 12 май 2006
    #5

  6. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    "Современный подход к Го напоминает 60-ые годы в программировании шахмат:"

    Это судя по статьям десятилетней давности, и описанию алгоритмов не самых сильных программ.
    Думаю, что ситуация с первым эшелоном несколько лучше.

    "Ведь на статус локальной группы может влиять каждый из свободных пунктов доски. Через лестницы и/или ко-борьбу. Впрочем, если демонстративно отказываться от изучения хотя бы основ теории Го, то понять это непросто..."

    Я перед тем как начать писать новую игру - обычно читаю теорию (не программирования игры, а теорию самой игры), потом наигрываю партии с программами, потом играю несколько партий/турниров на игровых серверах, а затем уже бросаюсь на амбразуры;)))
    NS, 12 май 2006
    #6
  7. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Забавный ответ :)

    В том то вся и трудность заключается, что нужно локальным. Нужно просто уметь локализовать. Имейте в виду, что локализация может быть не только в пространственном смысле.

    Глобальный найдет максимум пару мертвых груп, а если их 5? Получим непонятно что.
    WildCat, 12 май 2006
    #7

  8. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Вот так существующие программы непонятно что и получают, если борьба ведется по всей доске...
    NS, 12 май 2006
    #8

  9. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Методы локализации есть - есть такая игра - Амазон, Где ферзи по доске бегают и преграды ставят - там пытаются локализовать и считать отдельно.
    NS, 12 май 2006
    #9

  10. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.490
    Симпатии:
    3.108
    Репутация:
    95
    Адрес:
    Москва
    Оффлайн
    Вспомнилось шутливое объяснение из недавних разговоров на гошных форумах:
    "Почему корейцы сейчас играют в Го сильнее всех?" — "Просто они рассматривают всю доску как одну большую локальную группу" :)
    WinPooh, 12 май 2006
    #10

  11. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Можно попытаться оценкой оценить степень живучести группы. Надо подумать....
    Но тут сложнее. Непонятно даже как определить саму группу.
    NS, 12 май 2006
    #11

  12. atoku Модератор

    • Команда форума
    Рег.:
    05.02.2006
    Сообщения:
    2.949
    Симпатии:
    9
    Репутация:
    0
    Адрес:
    USA
    Оффлайн
    Очень интересно...

    А разве, кстати, не китайцы сейчас всех сильнее?
    atoku, 12 май 2006
    #12
  13. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    NS!
    Как у тебя продвигается написание движка? Хотелось бы его уже увидеть.

    Я уже сделал оболочку для игры (пока только одной партии) между двумя движками по протоколу GTP. Завтра выложу.

    У меня есть два движка GNU Go 3.6 и WallyPlus. Жалко, что один играет по японским, а другой по китайским правилам. Можно как-то заставить GNU Go играть по-китайски?
    Кто-нибудь знает где можно скачать бинарники еще каких-нибудь движков?
    WildCat, 17 май 2006
    #13

  14. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Я вечером тебе пришлю MFGO. Она играет по четырем правилам, причем достаточно сильно.
    У меня с программой сейчас как с шахматами - этап обдумывания и марания бумаги;)))
    Но тестовую версию могу набросать. Давай скину на неделе после 21-го. Сейчас НДС в Холдинге - меня на работе просто на части разрывают. А еще надо успеть 0.06 к началу WBEC выпустить. То есть к выходным просто не успеть.
    Как с Каиссой? Получилось? У меня процесс потихоньку идёт. Благо текст не кривой.;)))
    NS, 17 май 2006
    #14
  15. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    За Каиссу решил не браться. Т.к. много надо менять и получиться ли в результате именно Каисса не понятно.

    Есть проблемы с GNU. Оно после какого-то (125-ого?) хода ничинает пургу гнать, о которой его не просили.

    Попросили показать доску и сделать ход.

    Вот доска:

    =
    A B C D E F G H J K L M N O P Q R S T
    19 . X . . . . . . X O . O X X X O . . . 19
    18 . X O O . . . . X O . O X . X O . . . 18
    17 X X X O . . . O X O O O X X O O . . . 17
    16 O X O O . O . O X X O X X X X O O . . 16
    15 O O O O . . . O X O X . X X O X X O . 15
    14 X X O O X . . O O O X X X . O . . . . 14
    13 . X O X . X . X X X O X . X O O O . . 13
    12 X O O X . . . . . . O . O O . . O O . 12
    11 X O X O O . . O . O . O . . O O X X . 11 WHITE (O) has captured 10 stones
    10 X O X X . O . . . + O X . O X X X . X 10 BLACK (X) has captured 17 stones
    9 X X O X . . . O . . . . . O O O X X . 9
    8 . O O X . . O . O O O O O . O X O O . 8
    7 . . O X O . O X X O X X O O X X O . O 7
    6 . . . X . . O X X X . X O O . X X O . 6
    5 . . X . X . O O X . X . X O X X O O . 5
    4 . . O X . X O X X X X X X X . X . O . 4
    3 . . O . O O X X X X . X X . X O O . X 3
    2 . . . O . O X X X . X . . X . X O O . 2
    1 . . . . X O X . . X X X X . X . . . . 1
    A B C D E F G H J K L M N O P Q R S T

    А тут начинается пурга, которая обычно выводится после получения команды "quit":

    New level 10 (1 white 1 299 119)
    New level 10 (2 white 1 299 118)
    New level 10 (3 white 1 299 117)
    New level 10 (4 white 1 299 116)
    New level 10 (5 white 1 299 115)
    New level 10 (6 white 1 298 114)
    New level 10 (7 white 1 298 113)
    New level 10 (8 white 1 297 112)
    New level 10 (9 white 1 297 111)
    New level 10 (10 white 1 297 110)
    New level 10 (11 white 1 296 109)
    New level 10 (12 white 1 295 108)
    New level 10 (13 white 1 295 107)
    New level 10 (14 white 1 294 106)
    New level 10 (15 white 2 292 105)
    New level 10 (16 white 2 290 104)
    New level 10 (17 white 2 288 103)
    New level 8 (18 white 3 285 102)
    New level 6 (19 white 3 282 101)
    New level 7 (20 white 2 280 100)
    New level 9 (21 white 1 279 99)
    New level 7 (22 white 3 276 98)
    New level 8 (23 white 2 274 97)
    New level 9 (24 white 2 272 96)
    New level 7 (25 white 3 269 95)
    New level 9 (26 white 1 268 94)
    New level 10 (27 white 2 266 93)
    New level 8 (28 white 4 262 92)
    New level 10 (29 white 1 261 91)
    New level 10 (30 white 2 259 90)
    New level 10 (31 white 1 258 89)
    New level 10 (32 white 2 256 88)
    New level 10 (33 white 1 255 87)
    New level 10 (34 white 1 254 86)
    New level 10 (35 white 1 253 85)
    New level 10 (36 white 1 252 84)
    New level 10 (37 white 2 250 83)
    New level 10 (38 white 1 249 82)
    New level 10 (39 white 1 249 81)
    New level 10 (40 white 2 247 80)
    New level 10 (41 white 1 246 79)
    New level 10 (42 white 2 244 78)
    New level 10 (43 white 1 243 77)
    New level 10 (44 white 1 242 76)
    New level 10 (45 white 1 241 75)
    New level 10 (46 white 1 240 74)
    New level 10 (47 white 1 239 73)
    New level 10 (48 white 1 238 72)
    New level 10 (49 white 2 236 71)
    New level 10 (50 white 3 233 70)
    New level 10 (51 white 1 232 69)
    New level 10 (52 white 1 231 68)
    New level 10 (53 white 1 230 67)
    New level 10 (54 white 1 229 66)
    New level 10 (55 white 2 227 65)
    New level 10 (56 white 1 226 64)
    New level 10 (57 white 2 224 63)
    New level 10 (58 white 1 223 62)
    New level 10 (59 white 1 222 61)
    New level 10 (60 white 3 219 60)
    New level 8 (61 white 5 214 59)
    New level 10 (62 white 1 213 58)
    New level 10 (63 white 2 211 57)
    New level 10 (64 white 1 210 56)
    New level 10 (65 white 1 209 55)
    New level 10 (66 white 1 208 54)
    New level 10 (67 white 1 207 53)
    New level 10 (68 white 1 206 52)
    New level 8 (69 white 4 202 51)
    New level 10 (70 white 1 201 50)
    New level 9 (71 white 4 197 49)
    New level 10 (72 white 2 195 48)
    New level 8 (73 white 5 190 48)
    New level 9 (74 white 2 188 48)
    New level 10 (75 white 1 187 48)
    New level 7 (76 white 7 180 48)
    New level 9 (77 white 1 179 48)
    New level 10 (78 white 1 178 48)
    New level 10 (79 white 2 176 48)
    New level 10 (80 white 1 175 48)
    New level 7 (81 white 6 169 48)
    New level 9 (82 white 1 168 48)
    New level 10 (83 white 1 167 48)
    New level 7 (84 white 6 161 48)
    New level 9 (85 white 1 160 48)
    New level 10 (86 white 1 159 48)
    New level 7 (87 white 5 154 48)
    New level 9 (88 white 1 153 48)
    New level 10 (89 white 1 153 48)
    New level 7 (90 white 5 148 48)
    New level 9 (91 white 1 148 48)
    New level 10 (92 white 1 148 48)
    New level 6 (93 white 7 141 48)
    New level 8 (94 white 1 141 48)
    New level 10 (95 white 1 140 48)
    New level 8 (96 white 4 136 48)
    New level 10 (97 white 1 136 48)
    New level 10 (98 white 2 134 48)
    New level 10 (99 white 2 132 48)
    New level 10 (100 white 2 130 48)
    New level 8 (101 white 3 127 48)
    New level 10 (102 white 1 126 48)
    New level 10 (103 white 1 125 48)
    New level 10 (104 white 1 124 48)
    New level 10 (105 white 1 124 48)
    New level 10 (106 white 2 122 48)
    New level 10 (107 white 1 121 48)
    New level 8 (108 white 3 118 48)
    New level 10 (109 white 1 117 48)
    New level 10 (110 white 1 116 48)
    New level 10 (111 white 1 116 48)
    New level 10 (112 white 1 116 48)
    New level 10 (113 white 1 115 48)
    New level 10 (114 white 1 115 48)
    New level 10 (115 white 1 114 48)
    New level 10 (116 white 1 114 48)
    New level 10 (117 white 1 113 48)
    New level 10 (118 white 1 113 48)
    New level 10 (119 white 1 113 48)
    New level 10 (120 white 1 112 48)
    New level 10 (121 white 2 110 48)
    New level 10 (122 white 1 109 48)
    New level 10 (123 white 1 109 48)
    New level 10 (124 white 1 108 48= H18


    Причем в конце все-таки виден ход "= H18", но он должен быть на новой строке.
    WildCat, 17 май 2006
    #15

  16. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Колбасит их. Говорил я об этом.
    NS, 17 май 2006
    #16
  17. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Первая версия готова: www.igorkorshunov.narod.ru/gotm.rar

    Коротко о том как пользоваться.

    В GoTM.ini нужно указать 5 строк:

    1. размер доски
    2. путь к движку, который будет ходить первым, т.е. играть черными камнями. Они выглядят как красные :)
    3. командная строка для первого движка
    4. путь ко второму движку, играющего белыми (синими)
    5. командная строка для второго движка

    Затем идут три числа определяющие контроль времени:
    Main time
    Byo yomi time
    Byo yomi stones

    Чтобы играть самому, необходимо для одного из движков указать неправильный путь. Т.е. если оболочка не может запустить движок, то играет человек. Чтобы сделать пас, нужно тыкнуть в сегмент в левом верхнем углу, показывающий чей сейчас ход.

    Оболочка знает только одно правило: как снимать мертвые камни с доски. Все остальное возложено на движки.
    WildCat, 18 май 2006
    #17
  18. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    WildCat, 18 май 2006
    #18

  19. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Go++ отослал, а что делать с MFGO? 25 метров...
    ЗЫ. у Fritz Grau, автора Ферштейна, который спрашивает на WBEC про Ponder
    Программа написана на Делфи, и читает он обычным Read().
    http://people.freenet.de/FritzSchach/Feuerstein.dpr
    Надо наверно выложить нормальный пример под Делфи.
    NS, 18 май 2006
    #19
  20. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    А отодрать движок от всего остального в MFGO нельзя?

    Я по Дельфи не специалист :) Сам бы и посоветовал.
    WildCat, 18 май 2006
    #20

  21. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Выдрать попробую. но не факт, что выйдет.
    А чего тут советовать?
    PeekNamedPipe(), ReadFile()
    NS, 18 май 2006
    #21

  22. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.490
    Симпатии:
    3.108
    Репутация:
    95
    Адрес:
    Москва
    Оффлайн
    Игорь, взгляните.
    Я прорекламировал оболочку на Го-форуме, народ тестирует - уже есть первые отзывы и bug reports.
    http://forum.kido.com.ru//read.php?3,24959
    WinPooh, 19 май 2006
    #22

  23. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Там уже пытаются доказать, что за месяц невозможно написать играющую программу;))
    NS, 19 май 2006
    #23
  24. TopicStarter Overlay

    WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    4
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Я играющую программу обычно пишу день-два (Так было с WildCat и Каллисто).
    Но это если все понятно с алгоритмами.

    В Го для начала нужна идея нормальной ОФ. Пока у меня все еще проблемы с мертвыми камнями. Глобальный перебор тут никак не поможет, т.к. на последнем ply можно поставить мертвый камень (и как ОФ потом угадает, что это труп?). Тут нужен ФВ, который пока непонятно как делать.

    Появилась даже идея вычеслять степень мертвости чисто из позиционных соображений :)
    WildCat, 19 май 2006
    #24

  25. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    У меня те-же сроки. Анечка 0.01 была написана за выходные. За два дня.
    причем все оновные переборные алгоритмы в ней уже были.
    На счет мертвого камня. Существующий программы имеют порядка 1000 NPS.
    Вычислить что камень мертвый не так уж и трудоемко (одна степень свободы, или нет степеней свободы у камня, или группы).
    Насколько я понял - ты пытаешься добиться скоростей намного больше этой 1000?
    в ОФ не так уж и трудоемко определить все трупы...
    NS, 19 май 2006
    #25

  26. dees Учаcтник

    • Участник
    Рег.:
    09.05.2006
    Сообщения:
    17
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Камень ведь может быть мертвым, даже если имеет много степеней свобод.

    Если его доедать (что по китайским правилам не влечет потерю очков), то
    1) если доедание будет проводиться в середине игры это будет равносильно пасу, т.е. противник фактически получит один или несколько ходов подряд
    2) если доедать в конце, то проблема возникает уже у владельца доедаемой группы: он должен решить, стоит ли пытаться спасти эту группу или она уже мертва.
    dees, 19 май 2006
    #26

  27. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Текст исполнения хода на встроенном языке 1С...
    Оказалось пол-часа достаточно на написание;)))
    //*******************************************
    Процедура Сформировать()
    перем поле[442];
    перем стекКамней[361]; // Для определения мертвых камней/групп
    перем СписокОбследованных[361];
    перем СписокСтепеней[361];
    // Заполним поле
    Для а=0 по 20 цикл
    Для в=0 по 20 цикл
    коорд=а*21+в+1;
    // пустое поле
    поле[коорд]=0;
    Если (в=0) или (а=0) или (в=20) или (а=20) Тогда
    // Край доски
    поле[коорд]=-1;
    КонецЕсли;
    КонецЦикла;
    КонецЦикла;
    // поставим наш камень
    НашКамень=110;
    поле[НашКамень]=2;
    // определим есть ли степени свободы
    // у камня или содержащей его группы
    Камней=1; // На данный момент в группе один
    СтекКамней[1]=НашКамень; // необследованный камень
    КолОбследованных= 0; // количество обследованных камней
    колСтепеней = 0; // количество степеней свободы
    Пока Камней>0 Цикл
    ТекущийКамень=СтекКамней[Камней];
    // Затрем камень на поле
    // чтоб не обойти второй раз
    поле[ТекущийКамень]=10;
    Камней=Камней-1;
    // добавим затертый камень в список для восстановления
    КолОбследованных=КолОбследованных+1;
    СписокОбследованных[КолОбследованных]=ТекущийКамень;

    Коорд=ТекущийКамень+1;
    Если поле[коорд]=2 тогда
    // наш камень, принадлежащий группе
    Камней=Камней+1;
    СтекКамней[Камней]=коорд;
    Иначеесли поле[коорд]=0 тогда
    // добавим степень свободы
    КолСтепеней=КолСтепеней+1;
    СписокСтепеней[КолСтепеней]=Коорд;
    // и затрем её на поле
    // чтоб не посчитать второй раз
    поле[коорд]=10;
    КонецЕсли;

    Коорд=ТекущийКамень-1;
    Если поле[коорд]=2 тогда
    // наш камень, принадлежащий группе
    Камней=Камней+1;
    СтекКамней[Камней]=коорд;
    Иначеесли поле[коорд]=0 тогда
    // добавим степень свободы
    КолСтепеней=КолСтепеней+1;
    СписокСтепеней[КолСтепеней]=Коорд;
    // и затрем её на поле
    поле[коорд]=10;
    КонецЕсли;

    Коорд=ТекущийКамень+21;
    Если поле[коорд]=2 тогда
    // наш камень, принадлежащий группе
    Камней=Камней+1;
    СтекКамней[Камней]=коорд;
    Иначеесли поле[коорд]=0 тогда
    // добавим степень свободы
    КолСтепеней=КолСтепеней+1;
    СписокСтепеней[КолСтепеней]=Коорд;
    // и затрем её на поле
    поле[коорд]=10;
    КонецЕсли;

    Коорд=ТекущийКамень-21;
    Если поле[коорд]=2 тогда
    // наш камень, принадлежащий группе
    Камней=Камней+1;
    СтекКамней[Камней]=коорд;
    Иначеесли поле[коорд]=0 тогда
    // добавим степень свободы
    КолСтепеней=КолСтепеней+1;
    СписокСтепеней[КолСтепеней]=Коорд;
    // и затрем её на поле
    поле[коорд]=10;
    КонецЕсли;
    КонецЦикла;
    // После завершения
    // КолОбследованных - количество камней в группе
    // КолСтепеней - Количество степеней свободы у группы
    // СписокСтепеней[] - массив содержаший все степени свободы
    // списокОбследованных[] - массив содержащий все камни в группе

    // восстановим позицию (восстановим затертые поля)
    Для а=1 по КолСтепеней Цикл
    поле[СписокСтепеней[а]]=0;
    КонецЦикла;
    Для а=1 по КолОбследованных Цикл
    поле[списокОбследованных[а]]=2;
    КонецЦикла;
    КонецПроцедуры
    NS, 19 май 2006
    #27

  28. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    "Камень ведь может быть мертвым, даже если имеет много степеней свобод."
    Угу, а в шахматах нам в заключительной позиции может грозить мат в один ход от которого нет защиты... И никто почему-то на это не обращает внимание.
    Алгоритм ФВ как я его вижу сейчас я уже описывал. В ФВ включаются ходы, приводящие группу соперника в состоянии Атари. То есть если у группы только две степени свободы, то в ФВ будет предпринята попытка её убить.
    NS, 19 май 2006
    #28

  29. dees Учаcтник

    • Участник
    Рег.:
    09.05.2006
    Сообщения:
    17
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Не понял аналогии, если честно
    dees, 19 май 2006
    #29

  30. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.490
    Симпатии:
    3.108
    Репутация:
    95
    Адрес:
    Москва
    Оффлайн
    Не "почему-то". По вполне конкретной причине: практика показала, что в шахматах это работает.
    Насколько такой подход будет работать в Го - увидите сами, через обещанный месяц :)
    WinPooh, 19 май 2006
    #30

  31. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    У вас есть играющая программа? Если есть - поймете.
    В шахматах, если у нас лишний Ферзь в конечной позиции будет присвоена соответствующая оценка, несмотря на то, что нам может грозить мат в один ход от которого нет защиты.
    Так же и в ГО - если у нас 10 камней на доске - то нам они будут приписаны в оценку (Но только в случае если у них больше двух степеней свободы при ходе соперника, либо больше одной при нашем ходе). Несмотря на то, что они могут быть убиты в течении ближайших трех ходов...
    NS, 19 май 2006
    #31

  32. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Неважно насколько - важно что хоть как-то, но работать будет.
    NS, 19 май 2006
    #32

  33. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.490
    Симпатии:
    3.108
    Репутация:
    95
    Адрес:
    Москва
    Оффлайн
    Понимаете, дело-то в чём... Есть оценка и оценка. В смысле, абсолютная, теоретико-игровая оценка - 0 или 1. И модельная оценка, в сантипешках или каких других попугаях. В шахматах научились строить модельную оценку, которая хорошо коррелирует с абсолютной. И поэтому поиск даже на смешные 10-20 полуходов даёт хорошее приближение к полному решению игры.

    Я, конечно, не Го-бог, чтобы делать такие громкие заявления, но у меня есть подозрение что в Го модельная оценка, равная числу камней на доске, очень далека от абсолютной. С коэффициентом корреляции близким к нулю... И с такой оценкой считать придётся ходов на 150-200 вперёд, чтобы программа начала чего-то понимать в позиции.

    Впрочем, повторюсь - сами всё увидите. Больше не буду ни в чём разубеждать.
    Обещайте только через месяц плоды трудов предъявить :)
    WinPooh, 19 май 2006
    #33

  34. WinPooh В.М.

    • Команда форума
    Рег.:
    13.02.2006
    Сообщения:
    9.490
    Симпатии:
    3.108
    Репутация:
    95
    Адрес:
    Москва
    Оффлайн
    Будет. Но ненамного лучше генератора случайных ходов.
    WinPooh, 19 май 2006
    #34

  35. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    У вас есть соответсвующие тесты, чтоб это подтвердить?

    ЗЫ. Первоначальный вариант будет на следующей неделе.
    NS, 19 май 2006
    #35
Страница 1 из 14

Поделиться этой страницей