Форум Flasher.ru - Оптимизация алгоритма игры Реверси

Форум Flasher.ru (http://www.flasher.ru/forum/index.php)

- ActionScript 3.0 (http://www.flasher.ru/forum/forumdisplay.php?f=83)

- - Оптимизация алгоритма игры Реверси (http://www.flasher.ru/forum/showthread.php?t=213675)

Оптимизация алгоритма игры Реверси

Здравствуйте, пишу игру Реверси с возможностью игры против компьютера. Возникла след. сложность в алгоритме оценки возможных вариантов хода : необходимо вычислить ценность текущего хода в зависимости от того, какие ячейки занимают белые и черные фишки. Текущий ход записан как 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 ) ?
Всем спасибо!

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

Цитата:

А этот метод долго отрабатывает?

скажем так, если с ним - то алгоритм обрабатывает 60 ходов за 1 мс, а без switch - 95 ходов за 1 мс

Цитата:

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

интересная идея, но она не дает прироста производительности - скорее всего операция сравнения эквивалента по времени операции умножения

Цитата:

Но, возможно, я не совсем разобрался в алгоритме: зачем в метод передавать Id1 и id2, если они всегда одинаковы, и почему оценка именно так складывается?

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

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

Цитата:

скажем так, если с ним - то алгоритм обрабатывает 60 ходов за 1 мс, а без switch - 95 ходов за 1 мс

А сколько ходов будет достаточно?

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

Цитата:

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

Это другое дело.Особо оптимизировать тут нечего.Единственное я бы попробовал свич заменить на

Код AS3:

_eval+=(grid[i]==id1)?(_cost[i]):(-cost[i]);

Да в этой функции ничего особо не улучшить... это линейное время, и суммировать массив чисел за меньше чем линейное время не получится, ну не во Флеше, так это точно. Может можно попытаться поэксперементировать с байткодом, удалить какие-нибудь проверки и т.д. Но принципиальной разницы в производительности теоретически добиться нельзя.

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

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