Сейчас 13:48:45 Суббота, 2 июля, 2022 год
[ x ] Главная ⇒ Форум ⇐ RSS Файлы Cтатьи Картинки В о й т и   или   з а р е г и с т р и р о в а т ь с я


[ Новые сообщения · Участники · Правила форума · Поиск · RSS ]
  • Страница 1 из 1
  • 1
Модератор форума: PUVer, SirNikolas, Ty3uK  
Форум о Warcraft 3 » Раздел для картостроителей » GUI / Jass » [Вопрос] Random в WarCraft 3 (Как насчёт... разобраться? :))
[Вопрос] Random в WarCraft 3
DuosoraДата: Среда, 18 Марта 2015, 16:10:16 | Сообщение # 1
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки:
Всё началось вот с этой темы. Но, думаю, сделать тут обсуждение будет намного лучше.
Предлагаю разобраться в механике работы GetRandomInt/Real.
Для анализа через Preload Exploit я вынул значения случайных чисел при конкретных Random Seed - от 0 до 5999 (могу дополнить аж до 2147483647.

Доподлинно известно, что Варкрафт применяет псевдослучайные числа, генерируемые в определённой последовательности.
Сама последовательность - математическая рекуррентная формула, которая состоит из определённых действий и из предыдущего члена выводит следующий. Первым членом такой последовательности является некое значение Random Seed. В Варкрафте им управляют функции SetRandomSeed и GetRandomSeed (изменение и получение).


Задача - вывести данную рекуррентную формулу. Если у кого-то есть какие-то соображения о том, что стоит попробовать или сделать - обсудим.
Всё-таки, этот вопрос в варкрафте ещё открыт.

Upd.: Из интересного материала на эту тему - распределение случайных чисел варкрафта, которое используется в атаках, уже исследовали в далёком 2008 году и прочитать об этом можно в теме на плейдоте.
Статья на английском языке, но содержит неплохие табличные данные, основанные на математике.


Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.


Сообщение отредактировал Duosora - Среда, 18 Марта 2015, 18:55:36
 

SirNikolasДата: Среда, 18 Марта 2015, 18:47:58 | Сообщение # 2
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Удачи!

 

DuosoraДата: Среда, 18 Марта 2015, 18:54:54 | Сообщение # 3
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки:
Из интересного материала на эту тему - распределение случайных чисел варкрафта, которое используется в атаках, уже исследовали в далёком 2008 году и прочитать об этом можно в теме на плейдоте.
Статья на английском языке, но содержит неплохие табличные данные, основанные на математике.

Добавлено (18 Марта 2015, 18:54:54)
---------------------------------------------
SirNikolas,
Спасибо.)


Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
 

КристоферДата: Среда, 18 Марта 2015, 19:27:13 | Сообщение # 4
7 уровень
Группа: Проверенные
Сообщений: 401
Награды: 0
Репутация: 338
Блокировки:
Duosora, если не ошибаюсь, вар написан на С++, а там есть такая прекрасная функция как randomaze(A); random(B);

"История нашего народа знает немало светлых страниц. Темных было тоже достаточно. И все с белыми пятнами. От белых пятен истории нужно избавляться, но нельзя же всё мазать черной краской!"(с) Рохан.
 

DuosoraДата: Среда, 18 Марта 2015, 20:04:12 | Сообщение # 5
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки:
Цитата Кристофер ()
если не ошибаюсь, вар написан на С++, а там есть такая прекрасная функция как randomaze(A); random(B);

Если так, то что за формула лежит в основе плюсичной функции rand()?


Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
 

BruДата: Среда, 18 Марта 2015, 21:55:47 | Сообщение # 6
i<3bo4k@
Группа: Акулы
Сообщений: 4750
Награды: 2
Репутация: 1950
Блокировки:
Кристофер, откуда уверенность в том, что Warcraft использует дефолтный rand()?
Хотя и это вероятно. Можно предположить, что seed задается через srand(), а сама генерация происходит через rand().
Duosora, в C/C++ используется довольно простой линейный конгруэнтный метод:

Добавлено (18 Марта 2015, 21:55:47)
---------------------------------------------
Кстати, если займешься этим, было бы интересно увидеть разницу в производительности Warcraft'овского генератора и какой-нибудь пользовательской функции, основанной, например, на приведенной выше.


Сообщение отредактировал Bru - Среда, 18 Марта 2015, 21:56:38
 

DuosoraДата: Пятница, 20 Марта 2015, 21:55:04 | Сообщение # 7
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки:
Код
function RandInt takes integer seed returns integer
      local integer next   = GetRandomSeed()*1103515245+12345
      local integer result = ModuloInteger(R2I(next/65536),2048)

      set next   = next*1103515245+12345   
      set result = result*1024
      set result = Pow(result,ModuloInteger(R2I(next/65536),1024))
        
      set next   = next*1103515245+12345   
      set result = result*1024
      set result = Pow(result,ModuloInteger(R2I(next/65536),1024))
       
      call SetRandomSeed(next)  
       
      return result
endfunction


Вроде бы, я верно переписал эту штуковину на JASS. Поддерживаются 32-битные числа.


Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.


Сообщение отредактировал Duosora - Пятница, 20 Марта 2015, 21:59:45
 

BruДата: Суббота, 21 Марта 2015, 14:15:49 | Сообщение # 8
i<3bo4k@
Группа: Акулы
Сообщений: 4750
Награды: 2
Репутация: 1950
Блокировки:
Цитата Duosora ()
верно переписал

Даа?
>takes integer seed
Не вижу что-то упоминаний переменной seed в теле функции.
А в остальном, кажется, верно.

Добавлено (21 Марта 2015, 13:55:11)
---------------------------------------------
Тестировал ее, кстати?

Добавлено (21 Марта 2015, 14:15:49)
---------------------------------------------
local integer next=GetRandomSeed() * 1103515245 + 12345 //Undeclared function GetRandomSeed()
local integer next=GetRandomSeed() * 1103515245 + 12345 //Bad types for binary operator
local integer next=GetRandomSeed() * 1103515245 + 12345 //Cannot convert real to integer
set result=Pow(result, ModuloInteger(R2I(next / 65536), 1024)) //Cannot convert real to integer
set result=Pow(result, ModuloInteger(R2I(next / 65536), 1024)) //Cannot convert real to integer

 

SirNikolasДата: Суббота, 21 Марта 2015, 14:17:21 | Сообщение # 9
Группа: Модераторы
Сообщений: 6729
Награды: 1
Репутация: 1867
Блокировки:
Duosora, ^ - это xor, а не pow.

 

BruДата: Суббота, 21 Марта 2015, 19:13:41 | Сообщение # 10
i<3bo4k@
Группа: Акулы
Сообщений: 4750
Награды: 2
Репутация: 1950
Блокировки:
SirNikolas, разве? Всегда считал, что Pow.

Добавлено (21 Марта 2015, 15:02:01)
---------------------------------------------
Оп, прошу прощения. Да, функция не работает из-за того, что нет xor'a.

Добавлено (21 Марта 2015, 19:13:41)
---------------------------------------------
В общем, функция должна иметь такой вид:
Код
function rand_r takes integer seed returns integer
       local integer next = seed
       local integer result

       set next = next * 1103515245
       set next = next + 12345;
       set result = ModuloInteger(R2I(next/65536),2048)

       set next = next * 1103515245
       set next = next + 12345;
       set result = ShiftLeft(result, 10);
       set result = xor(ModuloInteger(R2I(next/65536),1024))

       set next = next * 1103515245
       set next = next + 12345;
       set result = ShiftLeft(result, 10);
       set result = xor(ModuloInteger(R2I(next/65536),1024))

       set seed = next

       return result
endfunction

Использован ShiftLeft из библиотеки дуоса из соседней темы, но еще нужно реализовать xor.


Сообщение отредактировал Bru - Суббота, 21 Марта 2015, 19:14:10
 

DuosoraДата: Суббота, 21 Марта 2015, 20:18:53 | Сообщение # 11
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки:
Прошу прощения, тупанул с xor.
А в ShiftLeft и надобности особой нет, я написал это умножение напрямую.

Кстати, через Return Bug xor можно реализовать довольно просто, написав B2I-функцию, которая бы сравнивала именно побитово.
А в 1.24+... Даже не знаю.


Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
 

1vannДата: Четверг, 18 Июня 2015, 15:11:21 | Сообщение # 12
1 уровень
Группа: Пользователи
Сообщений: 2
Награды: 0
Репутация: 0
Блокировки:
Вот тебе код функций (только на Python'e, ибо С не очень):
Код

s1 = []
s2 = 0
tr = (0x9927148E, 0x08C7AAFD, 0x1F3EE6D5, 0xDA55BBF6,
       0x6A4AA075, 0xFF97BDE8, 0x9FBC9BDE, 0x46A18A81,
       0x63E30B6E, 0x5D6C7A76, 0xCA69D388, 0x25B947C3,
       0x3FA2AB83, 0xBA7C41A6, 0x0195ACE5, 0xC109CF7E,
       0x717062D9, 0x0205DB8D, 0x54EF8724, 0x3037D4C6,
       0x7BCB1BD0, 0xECD8E4B8, 0xDCADCE49, 0xC494A913,
       0x0DAE398F, 0x0EDD5218, 0x85F5FA78, 0x6DAFD258,
       0x3B53B2A4, 0xBE50A551, 0x11F42DFC, 0xF1169848,
       0x663DDF86, 0x2F2E445E, 0x176B0736, 0xB64C298B,
       0xE75F89E2, 0xE121A7CD, 0xED65C94D, 0x239CEEFE,
       0x04B77D33, 0x402A9A9E, 0xF35B10B3, 0x921C7782,
       0x571E4E20, 0x8C067222, 0xFB732C67, 0xBF0AC259,
       0x0CF95C79, 0x68121A28, 0x42193474, 0xF884C0B1,
       0x9D15F038, 0x6F3AF260, 0x91EB90B4, 0x61357F1D,
       0x5603325A, 0x932BC5A3, 0x434B0F80, 0x3CE0A8F7,
       0x2664D196, 0x4FCC45D7, 0xB5E9B0C8, 0xEA31D600)

def rol(a, n):
     return a if n == 0 else (a << n) + (a >> 32 - n)

def random():
     global s2
     b = [[7, 6, 3, 1], [54, 53, 50, 46], [0, 3, 2, 1]]
     c = 0

     for i in range(4):
         s1[i] += b[1][i] if s1[i] <= b[0][i] else -b[0][i]
         c ^= rol(tr[s1[i]], b[2][i])

     s2 = (s2 + c) & 0xFFFFFFFF
     return s2

def SetRandomSeed(seed):
     global s1, s2
     s1 = [(seed + (1 << 32 if seed < 0 else 0)) % i for i in (61, 59, 53, 47)]
     s2 = seed
     random()

def GetRandomInt(l, h):
     i = random()
     j = abs(h - l) + 1
     return h if h == l else (i * j >> 32) + l
 

DuosoraДата: Вторник, 18 Августа 2015, 22:55:35 | Сообщение # 13
The cats never sleep...
Группа: Ветераны
Сообщений: 6734
Награды: 10
Репутация: 2161
Блокировки:
1vann,
Благодарю. Это пролило свет на многие вещи.
Поверчусь вокруг них.


Не зли других и сам не злись.
Мы - гости в этом мире.
И если что не так - смирись,
Будь поумнее - улыбнись,
Ведь в мире всё закономерно.
Зло, излучённое тобой,
К тебе вернётся непременно.
 

1vannДата: Четверг, 20 Августа 2015, 09:37:20 | Сообщение # 14
1 уровень
Группа: Пользователи
Сообщений: 2
Награды: 0
Репутация: 0
Блокировки:
Небольшая ошибка в коде. Вместо
Код
s1[i] += b[1][i] if s1[i] <= b[0][i] else -b[0][i]

должно быть
Код
s1[i] += b[1][i] if s1[i] < b[0][i] else -b[0][i]
 

Форум о Warcraft 3 » Раздел для картостроителей » GUI / Jass » [Вопрос] Random в WarCraft 3 (Как насчёт... разобраться? :))
  • Страница 1 из 1
  • 1
Поиск:

Copyright © 2006 - 2022 Warcraft3FT.info При копировании материалов c сайта ставьте, пожалуйста, активную обратную ссылку на нас • Design by gReeB04ki ©
Хостинг от uCoz