Ответы в темах
-
Сообщения
-
Они недавно убрали информацию о методике просчета с сайта, но это не значит что сама эта методика изменилась.
На сайте было четко написано, что в случае большого материального перевеса одной из сторон ветвь отсекалась.Наверное я неточно выразился. Во время вычислений никаких обрезаний не было и всй было доведено до конуа. Рбрезана была информация, выложенная на сайте.
Скорей всего вы неправильно поняли.
Судя по информации на их сайте — обрезана не выложенная информация, а резали ветви они в процессе решения.
При большом материальном перевесе одной из сторон.То что Винда не однопотоковая система можно увидеть открыв диспетчер задач, и есно многоядерность и многопроцессорность увеличивают скорость загрузки.
Насчет игр. Главное окно, главная форма должны отвечать всегда, поэтому в любом случае, даже если не заявлена поддержка нескльких процессоров, у любой игры несколько потоков. Это легко можно увидеть в диспетчере задач. То есть выигрыш от нескольких яжер есть всегда!
Подавляющее большинство новых игр (и как уже было замечено из старых например F.E.A.R) поддерживают несколько процессоров. Это значит что идет разделение на потоки ресурсоемких задач, и соотвественно нагрузка на каждое ядро падает практически в два раза.
RAR поддерживает многопроцессорность, программы кодирования Видео. Шахматные программы и т.д.
Реально выхлоп от нескольких ядер очень велик. Можно запустить несколько ресурсоемких задач, и при этом продолжать работать в Винде, можно запустить матч движков с Ponder-ом, отсутствует подвисание системы при запуске ресурсоемкого процесса с высоким приоритетом. И т.д.И в любом случае — в Винде по умолчанию запущено много процессов. В случае многопроцессорности они делятся между процессорами/ядрами.
1. Отсечения проводились только в тех случаях, когда это не мешало доказательству. К примеру: если в позиции у белых было 10 продолжений, но первое же из них выигрывало, то остальные 9 не расматривались.
Это альфа-бета (метод ветвей и границ), понятно что это честное отсечение.
Здесь он подчеркнул, что из за громадного объёма инфомации и дерева, некоторые варианты обрезаны и до ЭБ точно ход-в-ход не доведены.
А вот после этого их доказательство ничего не стоит.
И где доказательство что их программа не содержит ошибок?
Хеш перекрестных позиций они использовали? Что использовалось в качестве ключа?Могу выслать по почте.
Вот еще одна ссылка:
http://says.ifolder.ru/2735283Заходишь по ссылке, внизу странице жмешь клавишу «Free», набираешь контрольный текст и начинается закачка.
Количество возможных позиций в шестидесятичетырехклеточных шашках примерно равняется 5×1020.
5000 позиций. Круто!
Вот оргинал статьи
http://lenta.ru/news/2007/07/20/checkers/Скачать версию от 11.06 можно тут:
http://rapidshare.com/files/43973283/skifi_russian_0_04_01.rar.html
Но это что-то промежуточное и непонятно играющее.
Надеюсь что в релизе Каллисто будет выложена значительно более сильная и стабильная версия. (ну и в любом случае будет поддержка ЭБ в формате Каллисто)Извиняюсь, конечно-же f8 против h6.
Вот партия:
[Event «Match»]
[Site «?»]
[Date «2007.7.19»]
[Round «10.2»]
[White «KestoG v1.3»]
[Black «Skifi russian 0.04.01»]
[Result «0-1»]
[TimeControl «60+1»]
[FEN «W:W13,18,22,24,25,26,27,28,29,30,31,32:B1,2,3,4,5,6,7,8,10,12,16,17»]1. b2-a3 g5-h4 2. a3:c5 d6:b4 3. a1-b2 b4-a3 4. g3-f4 e7-d6 5. d4-e5 f8-e7 6. c3-d4 g7-f6 7. e5:g7 h6:f8 8. f2-e3 a7-b6 9. g1-f2 h8-g7 10. d4-c5 d6:b4 11. a5:c3 b6-a5 12. c3-d4 c7-d6 13. f2-g3 h4:f2 14. e1:g3 d6-c5 15. d4:b6 a5:c7 16. f4-g5 c7-b6 17. g5-h6 g7-f6 18. g3-h4 b8-c7 19. h2-g3 c7-d6 20. b2-c3 b6-a5 21. e3-d4 d8-c7 22. g3-f4 c7-b6 23. d2-e3 b6-c5 24. d4:b6 a5:c7 25. c3-d4 c7-b6 26. d4-e5 f6:f2 27. c1-b2 a3:g5 28. h4:a5 f2-e1 29. a5-d8 e1-h4 30. d8-a5 h4-f6 31. a5-b6 f6-b2 32. b6-a7 b2-g7 33. a7-e3 g7-e5 34. e3-a7 e5-h8 35. a7-g1 d6-e5 36. g1-h2 e5-d4 37. h2-g1 d4-c3 38. g1-f2 c3-d2 39. f2-g1 d2-e1 40. g1-e3 h8-f6 41. e3-g1 e1-d2 42. g1-f2 d2-a5 43. f2-g1 a5-e1 44. g1-e3 f6-e5 45. e3-g1 e5-g7 46. g1-e3 e1-c3 47. e3-f2 g7-e5 48. f2-g1 e5-c7 49. g1-f2 c7-d8 50. f2-a7 c3-g7 51. a7-c5 g7-f6 52. c5-e3 d8-c7 53. e3-g1 f6-h8 54. g1-f2 f8-e7 55. f2-g1 e7-d6 56. g1-e3 d6-e5 57. e3-d2 c7-d8 58. d2-e1 e5-f4 59. e1-a5 f4-g3 60. a5-b4 g3-f2 61. b4-d6 f2-g1 62. d6-b8 g1-h2 63. b8-a7 d8-h4 64. a7-g1 h2-f4 65. h6-g7 h8:e5 66. g1-c5 h4-e1 67. c5-a3 e1-f2 68. a3-b4 f2-d4 69. b4-a3 d4-e3 70. a3-b4 e5-f6 71. b4-a5 e3-c5 72. a5-e1 f6-h4 73. e1-c3 f4-d2 74. c3:e1 c5-f2 75. e1:g3 h4:e1 0-1
Сейчас запустил матч текущей версии (от 11.06) с KestoG 1.3
с контролем 1+1
Вроде эта версия играет сильнее чем KestoG1.3, и самое главное что я заметил — даже с таким коротким контролем, она из двух партий в одной всё-таки смогла провести черную c8 против белой h6 без ЭБ!!!распараллеливание можно проверить и на одной машине (никто же не запрещает запустить две нити), а оценку потерь на PVS всегда можно прикинуть.
Если второстепенный процесс хватает только не PV узлы, потери времени возникают только если один процесс нашел опровержении в узле (на более раннем ходе).
при этом этот опровергающий ход не первый в узле!
50% потерь не будет даже при использовании простейших алгоритмов. Поэтому выигрыш в 1.5 раза (1 от первого процесса, и (1-0.5)=0.5 от второго процесса) распараллеливание на два потока практически гарантирует.http://www.cis.uab.edu/hyatt/search.html
Вот пример алгоритма.простейший алгоритм — неосновной процесс (второй) Хватает очередной ход из наиболее близкого к корню узла текущего варианта первого процесса, с уже полученной оценкой первого хода (либо с уже полученным опровержением по альфе на первом ходу)
Интересно, почему так… Ну вот чисто умозрительно, берем нечетные ходы, их считаем на одном процессоре, четные на другом…
Чело в том что в шашках (и шахматах) при игре точная оценка просчитывается не для всех ходов. В общем случае мы вначале получаем точную оценку лучшего на данный момент хода (по результатам предыдущих вычислений) а потом для остальных ходов просто убеждаемся что их оценка хуже чем у лучшего хода. На первую часть (полный расчет одного хода) уходит обычно больше половины времени, и распараллеливать там нечего, ибо бренчинг фактор в шашках сам по себе мал, а квадратный корень из него (фактор альфа-беты) вообще меньше 2, так что распараллеливать нечего теоретически, в отличие от шахмат. Вторую часть можно распараллелить но 50% раскиданная по 2 процессорам даст 25% теоретического прироста.
Если же точный расчет производится по всем (или нескольким) ходам, как например, в расширенном анализе Авроры, или Плюс600 то это дело действительно можно делать параллельно, и на 4-х ядерке добиться 4-х кратного ускорения (или близко к тому, пусть даже 3 кратного).
Что касается алгоритма игры то можно внутри распараллелить работу — допустим при начале позиции один процессор генерирует ходы второй проверяет хэш, третий четвертый еще что-нибудь, но боюсь что синхронизация этих потоков сожрет весь выигрыш в производительности, если не больше
Вы видимо незнакомы с алгоритмами распараллеливания альфа-беты.
У Рыбки бренчинг фактор меньше двух, при этом она отлично параллелится. Хоть на 8000 процессовКак продвигается проект Скифи?
Я добился перевеса в 50 пунктов Эло над KestoG 1.3, но где-то потом внес ослабление, нужно поднимать историю и искать сильнейший код.
(сила указана без поддержки ЭБ)
Текущая, последняя версия — от начала июня, с испорченным алгоритмом и без поддержки ЭБ — играющая в силу KestoG 1.3
(ЭБ не включено для тестов — то есть переносил код в новый проект и поддержку ЭБ еше не перенес)
Сейчас надеюсь себя заставить опять сесть за доработку. Если не заставлю, то будет в начале августа выложена текущая версия (только добавлю поддержку ЭБ)
