Доработка Алгоритма.

1 Января 2005 года закончился конкурс "Определение результата партии"

И только 4 Марта 2005 года
Алгоритму DAN версия 1.02v удалось наконец решить все партии из конкурсной базы данных.

Дата: 4 Марта, 2005 года:
Место Имя_____________ Автор_________ Всего Правильно Ошибочно Процент Время
_____ DAN_1.02v_______ Melnikov A.___ 3078_ 3078______ 0______ 100.00% 359 Сек

В 231 партии из 3078 алгоритму пришлось использовать перебор вариантов.
Самый длительный перебор состоял из 177672 ходов.
Самый глубокий перебор был в 72 полухода.

Теперь распределение законченных вариантов по глубине:

То есть просуммированы все глубины на которых заканчивался перебор варианта.
Получилась такая гистограмма:
Глубина (в полуходах)| Вариант закончен Ходом | Вариант закончен Пасом

_1. N= ___3, NP= 0
_2. N= _100, NP= 145
_3. N= _156, NP= 68
_4. N= _383, NP= 94
_5. N= _184, NP= 102
_6. N= _615, NP= 175
_7. N= _576, NP= 380
_8. N= _890, NP= 859
_9. N= _739, NP= 1249
10. N= 2662, NP= 1347
11. N= 1332, NP= 1003
12. N= 5634, NP= 477
13. N= 3811, NP= 277
14. N= 8332, NP= 374
15. N= 6095, NP= 495
16. N=10077, NP= 1016
17. N= 7100, NP= 2921
18. N=16164, NP= 4843
19. N= 7551, NP= 11571
20. N=18653, NP= 14139
21. N=10627, NP= 26513
22. N=15846, NP= 24923
23. N=14311, NP= 35282
24. N=18595, NP= 32345
25. N=18299, NP= 32175
26. N=26616, NP= 26225
27. N= 6308, NP= 25119
28. N=16142, NP= 17546
29. N= 4314, NP= 13873
30. N=18180, NP= 12934
31. N= 6283, NP= 10196
32. N=18905, NP= 12927
33. N= 6903, NP= 8634
34. N=13654, NP= 11807
35. N=10708, NP= 6664
36. N= 7106, NP= 10841
37. N=25049, NP= 4528
38. N= 6399, NP= 8185
39. N=23146, NP= 2966
40. N= 6339, NP= 6264
41. N=30206, NP= 2110
42. N= 9618, NP= 7057
43. N=16796, NP= 2168
44. N=13877, NP= 12553
45. N=16581, NP= 2915
46. N=10125, NP= 15546
47. N=10762, NP= 2427
48. N= 4388, NP= 9291
49. N= 5039, NP= 902
50. N= 1891, NP= 2021
51. N= 2431, NP= 241
52. N= _645, NP= 116
53. N= _940, NP= 149
54. N= _351, NP= 101
55. N= _817, NP= 173
56. N= 1101, NP= 362
57. N= 1671, NP= 430
58. N= 4468, NP= 1252
59. N= 2289, NP= 953
60. N=12617, NP= 2924
61. N= 2084, NP= 1354
62. N=21536, NP= 3832
63. N= 1640, NP= 1636
64. N=24629, NP= 2512
65. N= 1392, NP= 775
66. N=13621, NP= 718
67. N= _270, NP= 64
68. N= 3353, NP= 74
69. N= __33, NP= 2
70. N= _364, NP= 4
71. N= __15, NP= 1
72. N= ___8, NP= 0


Ссылка на конкурс:
Конкурс: "Вычисление результата партии".

Хотелось бы более тщательно проверить алгоритм,

поэтому если кто-нибудь увидит законченную партию со сложным подсчётом результата,
то у меня просьба: присылайте, пожалуйста, сюда в SGF тексте.

Единственное требование к партии,
чтобы она была сыграна игроками не ниже 6 Дана
до двух пасов по японским правилам и в турнире.

Молодец mels! Поздравляю!

Изначально, первая заработавшая версия SEOG не использовала перебор вариантов. Просто смотрела на доску и говорила результат... Я думал, времени много (3 месяца), успею рассчет йосе прикрутить :)) Как же... Увяз по самое не балуйся. Сейчас все думаю над структурой программы :) Как 100% наберу, обязательно дам знать!



Rianon (Максим Гуисов)

У нас, на Pocket Go Partner'e тоже идёт работа по алгоритму.
Так что продолжайте трепесчать!
%))))

> Так что продолжайте трепесчать!
Трепещать - в смысле бояться или болтать ? :)

> У нас, на Pocket Go Partner'e тоже идёт работа по алгоритму.

На КПК должны быть проблемы со временем вычисления.

Без перебора вариантов, 100 процентный результат не сделать.
А если перебирать то, есть партии, где на 3-ёх Гигагерцах 5-10 секунд
надо считать результат.
Для КПК это наверно минуты будут.
Можно критичные участки написать на ассемблере, это ускорит в 10-20 раз, но всё равно пол-секунды на трёх ГГЦ это долго.

Вообще, как пользователь КПК,
я бы согласился получать стопроцентный результат где-то за секунду, не больше. :)



Отправка отредактированного (07/03/05 13:17)

> Поздравляю!
Спасибо

> Изначально, первая заработавшая версия SEOG не использовала перебор вариантов.
У меня тоже. :)
Без перебора не обойтись, встречаюся большие не доигранные позиции,
где даже человек делает большой перебор вариантов.

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

> Как 100% наберу, обязательно дам знать!
Давай. Удачи !

Кстати, как только получаешь 100% правильного вычисления результата партии,
то программа начинает играть последний ход в партии как ГО-БОГ.
Даже лучше чем 9 Проф. Дан, ведь он может случайно зевнуть. :)



Отправка отредактированного (07/03/05 14:34)