Форум Flasher.ru
Ближайшие курсы в Школе RealTime
Список интенсивных курсов: [см.]  
  
Специальные предложения: [см.]  
  
 
Блоги Правила Справка Пользователи Календарь Поиск рулит! Сообщения за день Все разделы прочитаны
 

Вернуться   Форум Flasher.ru > Flash > ActionScript 3.0

Версия для печати  Отправить по электронной почте    « Предыдущая тема | Следующая тема »  
Опции темы Опции просмотра
 
Создать новую тему Ответ
Старый 11.12.2016, 01:30
Samuel_D вне форума Посмотреть профиль Отправить личное сообщение для Samuel_D Найти все сообщения от Samuel_D
  № 1  
Ответить с цитированием
Samuel_D

Регистрация: Aug 2010
Сообщений: 18
По умолчанию Оптимизация алгоритма игры Реверси

Здравствуйте, пишу игру Реверси с возможностью игры против компьютера. Возникла след. сложность в алгоритме оценки возможных вариантов хода : необходимо вычислить ценность текущего хода в зависимости от того, какие ячейки занимают белые и черные фишки. Текущий ход записан как Vector.<int>(64), в котором 0 - пустая ячейка, 1 - белая фишка и 2 - черная фишка. Есть еще один Vector.<int>(64) - который хранит ценность каждой ячейки. Оценка происходит при помощи след. метода
Код AS3:
// grid - поле с фишками
// _cost - ценность каждой ячейки
// id1 - id белых фишек
// id2 - id черных фишек
public function calc(grid:Vector.<int>, id1:int, id2:int):int {
      var eval:int = 0;
      for (var i:int = 0, l:int = grid.length; i < l; i++) {
             switch(grid[i]) {
                    case id1:
                           eval += _cost[i];
                    break;
                    case id2:
                           eval -= _cost[i];
                    break;
            }
      }
      return eval;
}
Проблема в том, что такой подход забирает на себя около 40% времени алгоритма. Есть какие-то варианты, как оптимизировать этот процесс ( основная нагрузка здесь из-за оператора switch ) ?
Всем спасибо!

Старый 11.12.2016, 02:25
Attos вне форума Посмотреть профиль Отправить личное сообщение для Attos Найти все сообщения от Attos
  № 2  
Ответить с цитированием
Attos

Регистрация: Aug 2015
Сообщений: 26
А этот метод долго отрабатывает?
Если не нравится именно switch, то можно сделать фишки 1 - белые, а черные не 2, а -1, тогда switch заменится на eval += grid[i] * _cost[i]
Но, возможно, я не совсем разобрался в алгоритме: зачем в метод передавать Id1 и id2, если они всегда одинаковы, и почему оценка именно так складывается?

Старый 11.12.2016, 12:15
Samuel_D вне форума Посмотреть профиль Отправить личное сообщение для Samuel_D Найти все сообщения от Samuel_D
  № 3  
Ответить с цитированием
Samuel_D

Регистрация: Aug 2010
Сообщений: 18
Цитата:
А этот метод долго отрабатывает?
скажем так, если с ним - то алгоритм обрабатывает 60 ходов за 1 мс, а без switch - 95 ходов за 1 мс

Цитата:
Если не нравится именно switch, то можно сделать фишки 1 - белые, а черные не 2, а -1, тогда switch заменится на eval += grid[i] * _cost[i]
интересная идея, но она не дает прироста производительности - скорее всего операция сравнения эквивалента по времени операции умножения

Цитата:
Но, возможно, я не совсем разобрался в алгоритме: зачем в метод передавать Id1 и id2, если они всегда одинаковы, и почему оценка именно так складывается?
id1 и id2 передаются т.к. не хотелось хардкодить значения, чтобы можно было их заменить безболезненно ( они же используются не только в этом методе )

Не совсем понял вопроса о подсчете оценки, но опишу ее логику :
В игре угловые клетки самые важные, т.к. их нельзя отобрать у противника, соседние с ними клетки наоборот повышают вероятность захвата углов противника и т.д. Соотв. я дал каждой клетке свой вес, после чего я к весу хода добавляю вес клетки если там мои фишки и отнимаю вес клетки если там фишка противника. Так получаю вес хода, чтобы его можно было сравнить с остальными ходами.


Последний раз редактировалось Samuel_D; 11.12.2016 в 23:53.
Старый 11.12.2016, 14:16
undefined вне форума Посмотреть профиль Отправить личное сообщение для undefined Найти все сообщения от undefined
  № 4  
Ответить с цитированием
undefined

Регистрация: Oct 2006
Сообщений: 2,281
Цитата:
скажем так, если с ним - то алгоритм обрабатывает 60 ходов за 1 мс, а без switch - 95 ходов за 1 мс
А сколько ходов будет достаточно?

Добавлено через 18 минут
60К ходов в секунду будет достаточно всем и каждому © имхо.Или планируется параллельная игра со всем китаем?)


Последний раз редактировалось undefined; 11.12.2016 в 21:21.
Старый 11.12.2016, 23:46
Samuel_D вне форума Посмотреть профиль Отправить личное сообщение для Samuel_D Найти все сообщения от Samuel_D
  № 5  
Ответить с цитированием
Samuel_D

Регистрация: Aug 2010
Сообщений: 18
Цитата:
А сколько ходов будет достаточно?

Добавлено через 18 минут
60К ходов в секунду будет достаточно всем и каждому © имхо.Или планируется параллельная игра со всем китаем?)
Вы же понимаете что слово "достаточно" слишком субъективное значение в данном контексте. На своем примере я могу сказать, что при глубине в 5-ть ходов, не редко приходиться обрабатывать порядка 90 тыс. ходов( и это с учетом альфа бета отсечения) - т.е. задержка в 1.8 сек. Как по мне - допустима задержка не более 0.5 секунды( по крайней мере это не так сильно меня раздражает ).

Старый 12.12.2016, 12:17
undefined вне форума Посмотреть профиль Отправить личное сообщение для undefined Найти все сообщения от undefined
  № 6  
Ответить с цитированием
undefined

Регистрация: Oct 2006
Сообщений: 2,281
Это другое дело.Особо оптимизировать тут нечего.Единственное я бы попробовал свич заменить на
Код AS3:
_eval+=(grid[i]==id1)?(_cost[i]):(-cost[i]);


Последний раз редактировалось undefined; 12.12.2016 в 12:31.
Старый 12.12.2016, 13:59
wvxvw вне форума Посмотреть профиль Отправить личное сообщение для wvxvw Найти все сообщения от wvxvw
  № 7  
Ответить с цитированием
wvxvw
Modus ponens
 
Аватар для wvxvw

модератор форума
Регистрация: Jul 2006
Адрес: #1=(list #1#)
Сообщений: 8,049
Записей в блоге: 38
Да в этой функции ничего особо не улучшить... это линейное время, и суммировать массив чисел за меньше чем линейное время не получится, ну не во Флеше, так это точно. Может можно попытаться поэксперементировать с байткодом, удалить какие-нибудь проверки и т.д. Но принципиальной разницы в производительности теоретически добиться нельзя.

Если прям такая жестокая необходимость ускорить: можно посмотреть на Хекс и попытаться воспользоваться его АПИ для быстрого доступа к памяти (с его помощю можно снизить затраты на доступ к элементам массива).

Или можно попробовать шейдеры: там, как правило, возможно добиться параллельного выполнения (и тогда суммирование массива чисел можно сделать за логарифмическое время, если чисел не очень много.
__________________
Hell is the possibility of sanity

Создать новую тему Ответ Часовой пояс GMT +4, время: 00:44.
Быстрый переход
  « Предыдущая тема | Следующая тема »  
Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


 


Часовой пояс GMT +4, время: 00:44.


Copyright © 1999-2008 Flasher.ru. All rights reserved.
Работает на vBulletin®. Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Администрация сайта не несёт ответственности за любую предоставленную посетителями информацию. Подробнее см. Правила.