Hash позиции

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

  1. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    Стал добавлять к своему движку хеш , чтоб не повторял позиции ,
    В результате столкнулся с геморроем :
    1. Скорость перебора упала где-то с 1300 до 1000 Knps
    2. Честно скопированный код из TSCP несет в себе какую-то лажу - программа в ничейном эндшпиле ,
    за просто так дарит ладью , думая , что оценка 0.00 ... а после хода на нее находит озарение :rolleyes:

    в общем у меня вопрос : сужествуют ли другие (может есть что побыстрее) методы оценки повторяемости ходов и не сталкивались ли вы с чем-то похожим? :)

    может быть есть возможность совмещения хеша позиций повторения и transposition tables для экономии времени ?
  2. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Зобрист. Для хеш Таблиц и для контроля повторения используется один и тот-же однократно (по конкретной позиции) посчитанный Зобрист кей.
    Есно Контроль повторения (позиции встретившиеся в партии) Хранятся в отдельном списке, и для проверки повторения - нужно сделать максимум 50 сравнений.
  3. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Изначальный TSCP был без хеша. Его уже кто-то потом добавил. Я этот код так и не видел. Можешь здесь запостить ключевые моменты?

    Для отладки хеша можно вместе с хеш-ключом сохранять и всю позицию. А потом при совпадении ключа смотреть совпадают ли позиции. И если не совпадают, то разбираться почему. У меня такое иногда случалось из-за того, что я пользовался стандартным rand().
  4. gudvinn Учаcтник

    • Новичок
    • Участник
    Рег.:
    04.08.2006
    Сообщения:
    28
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Объясните пожалуста, что такое 1300 до 1000 Knps — это миллион ?
    КАкая скорость должна быть?
    У меня у Fruit 2.1 в середине партии примерно 150000 - 160000 узлов в секунду. У Dragon 4.6 - 500000 узлов в секунду. ( Обе программы под Ареной и коды взял там же ).

    Как же получить 1300000?
  5. bankuss Александр

    • Заслуженный
    • Участник
    Рег.:
    23.05.2006
    Сообщения:
    1.040
    Симпатии:
    26
    Репутация:
    0
    Оффлайн
    gudvinn поставить новый процессор :)
    а вобще сила игры кроется не в количестве node per second, а в качестве их перебора.
  6. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Это миллион :)
    Че-то мало у Фрукта. У меня где-то 700-800.
    Чтобы получить скорость побольше надо купить железо побыстрее :)
  7. WildCat Коршунов Игорь

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

    • Заслуженный
    • Участник
    Рег.:
    23.05.2006
    Сообщения:
    1.040
    Симпатии:
    26
    Репутация:
    0
    Оффлайн
    WildCat в качестве примера можно "ткнуть лицом" в рыбку :) что было понятней
  9. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Я смогу найти два компа таких, что запустив на одном Анечку, а на другом Рыбку убедимся, что сила программы заключается в NPS... :)
  10. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Давайте попробуем Рыбку с примерно 100, как у меня, и Рыбку с поболее чем 500, как у некоторых продвинутых. И можно будет увидеть, что вся сила в NPS :)
  11. gudvinn Учаcтник

    • Новичок
    • Участник
    Рег.:
    04.08.2006
    Сообщения:
    28
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    У меня (беру из свойств мой компьютер на рабочем столе):
    XP Professional версия 2002 Service Pack 2
    AMD Athlon(tm) 64 Processor 3000+ 2.01 ГГц 1.00 ГБ ОЗУ

    Я так понял, что для Fruit 2.1 150 000 узлов в секунду это мало? Но я вижу это в Арене.
  12. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    У меня Fruit 2.2.1.
    2.1 должен быть еще быстрее. А загрузка CPU при работе Фрукта полная? Может есть своп.
  13. gudvinn Учаcтник

    • Новичок
    • Участник
    Рег.:
    04.08.2006
    Сообщения:
    28
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Загрузка 100%.

    Dragon 4.6 показывает 500000 и больше. А Фрут 2.1 именно 150000-170000, к окончанию показывает до 250 000-300 000
    может быть причина в том, что Фрут 2.1 я сам откомпилировал в Визуал Студио 2005?
    Я пробовал ставить оптимизацию по скорости но скорость не меняется.
  14. WildCat Коршунов Игорь

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

    • Заслуженный
    • Участник
    Рег.:
    23.05.2006
    Сообщения:
    1.040
    Симпатии:
    26
    Репутация:
    0
    Оффлайн
    NS я имел ввиду разные движки на одинаковых машинах :)
  16. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Понятно, но NPS тоже влияет на силу.
    Сейчас запустил ровно в 20 раз замедленную Рыбку с Анечкой в полную силу. (контроль 10+10)
    Рыба сливает в ноль... При этом прикол - считают почти на одинаковую глубину!!!
  17. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    То есть не совсем одинаковую :)
    Рыба на 8, Анечка на 11.
  18. WildCat Коршунов Игорь

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

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Не должна терять больше 300 пунктов. Что то здесь не так!
  20. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    В Арене есть параметр (в настройке движка) - поставил Рыбе 5%.
    По Диспетчеру задач - всё честно. Разница в потраченном процессорном времени ровно в 20 раз.
    По формуле Васика (-70 пунктов на двухкратном замедлении) Рыба вроде не должна проигрывать,
    но у меня играет (возможно, точно не уверен) правленная версия 0.08, наверно пунктов на 50-100 сильнее общедоступной. И Рыба просто постоянно влетает в Тактике. Жутко влетает.
  21. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Сравнивать NPS разных движков не имеет никакого смысла.
  22. gudvinn Учаcтник

    • Новичок
    • Участник
    Рег.:
    04.08.2006
    Сообщения:
    28
    Симпатии:
    0
    Репутация:
    0
    Оффлайн
    Скажите пожалуста как определяется глубина? Это уровень общего поиска или плюс глубина форсированного варианта?
  23. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Возможно указание двух параметров.
    1. Глубина заданная в параметре Depth в корне. (это основной параметр)
    2. Максимальная глубина перебора.
    Обычно указывают как например 10/22
    То есть количество полуходов до ФВ, если не будет продлений/сокращений.
  24. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Не доверяю я Арене. Она даже поравну время раздать не может.
    Нигде в WinAPI не видел чтобы процессу можно было давать 5% времени. Если Арена сама издевается над процессами, то видимо как-то криво.
  25. NS Нефёдов Сергей

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

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Под арену - да, некоторая неравномерность в глубине перебора у Рыбки присутствует :)
    Но пока запустил матч с 10% у Рыбки. Неравномерности меньше.
  27. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    Корректно ли Арена играет в эти игры? И возможно ли это вообще?
  28. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Да, под терминальные сервера программы срабатывают очень четко. (у нас в холдинге используются)
    Арена не настолько корректно отрабатывает.
    Но факт что Рыбка весьма слаба в тактике (даже при одинаковом контроле, но при равном контроле из-за хорошей оценки она умудряется обходить неприятности) легко проверяется на тактических тестах (например IQ6.epd) И та беда которая проиходит при сокращениеи контроля - весьма предсказуема. :)
  29. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    А можно использовать разный контроль? Например, Анечка 20 + 20 против Рыбки1 + 1.
  30. NS Нефёдов Сергей

    • Заслуженный
    • Ветеран
    Рег.:
    02.05.2006
    Сообщения:
    6.811
    Симпатии:
    96
    Репутация:
    3
    Адрес:
    Санкт-Петербург
    Оффлайн
    Если давать Рыбке 10% времени - она начинает играть сильнее Анечки.
    Насчет разного контроля - какая-нибудь оболочка поддерживает, или надо опять писать "переходник"?
  31. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    1 Knps = 1000 nps (позиций в секунду)
    на моем Athlon 3000+ у Toga !! получается где-то 700 knps под оболочкой Fritz 9 // в Арене думаю будет больше
  32. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    пожалуйста :
    Код:
    void init_hash()
    {
        int i, j, k;
    
        srand(0);
        for (i = 0; i < 2; ++i)
            for (j = 0; j < 6; ++j)
                for (k = 0; k < 64; ++k)
                    hash_piece[i][j][k] = hash_rand();
        hash_side = hash_rand();
        for (i = 0; i < 64; ++i)
            hash_ep[i] = hash_rand();
    }
    
    
    /* hash_rand() XORs some shifted random numbers together to make sure
       we have good coverage of all 32 bits. (rand() returns 16-bit numbers
       on some systems.) */
    
    int hash_rand()
    {
        int i;
        int r = 0;
    
        for (i = 0; i < 32; ++i)
            r ^= rand() << i;
        return r;
    }
    
    
    /* set_hash() uses the Zobrist method of generating a unique number (hash)
       for the current chess position. Of course, there are many more chess
       positions than there are 32 bit numbers, so the numbers generated are
       not really unique, but they're unique enough for our purposes (to detect
       repetitions of the position). 
       The way it works is to XOR random numbers that correspond to features of
       the position, e.g., if there's a black knight on B8, hash is XORed with
       hash_piece[BLACK][KNIGHT][B8]. All of the pieces are XORed together,
       hash_side is XORed if it's black's move, and the en passant square is
       XORed if there is one. (A chess technicality is that one position can't
       be a repetition of another if the en passant state is different.) */
    
    void set_hash()
    {
        int i;
    
        hash = 0;    
        for (i = 0; i < 64; ++i)
            if (color[i] != EMPTY)
                hash ^= hash_piece[color[i]][piece[i]][i];
        if (side == DARK)
            hash ^= hash_side;
        if (ep != -1)
            hash ^= hash_ep[ep];
    }
    
    в Search :
    
    if (ply && reps() )
        return 0;
    я сделал все то же самое
    (только приспособил нахождение очередной фигуры при хешировании под 0x88 ...
    но там ошибки маловероятны:D)
  33. WildCat Коршунов Игорь

    • Команда форума
    Рег.:
    04.05.2006
    Сообщения:
    3.599
    Симпатии:
    3
    Репутация:
    0
    Адрес:
    Гомель
    Оффлайн
    r ^= rand() << i;
    Так делать плохо. Будут коллизии. Нужен нормальный генератор случайных чисел.

    Ни для чего кроме повторов хеш не используется? Тогда возможно ошибка в reps().
  34. TopicStarter Overlay

    Binary Учаcтник

    • Участник
    Рег.:
    27.08.2006
    Сообщения:
    135
    Симпатии:
    0
    Репутация:
    0
    Адрес:
    Мытищи
    Оффлайн
    2 WildCat кинь сюда код НОРМАЛЬНОГО генератора , плз ...:)

    Код:
    int reps()
    {
        int i;
        int r = 0;
    
        for (i = hply - fifty; i < hply; ++i)
            if (hist_dat[i].hash == hash)
                ++r;
        return r;
    }
    это reps()
  35. NS Нефёдов Сергей

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

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