Predição de movimento em jogos distribuídos baseada em aprendizado de máquina

Abstract

Resumo: Em jogos distribuídos multiplayer os jogadores mantém uma visão consistente das posições uns dos outros através da troca periódica de informações sobre a movimentação de seus personagens. As mensagens de atualização, alem de representarem uma sobrecarga na rede, podem sofrer atrasos de entrega, podendo causar inconsistências ou ainda saltos abruptos de renderização. Tradicionalmente, o algoritmo Dead Reckoning ó utilizado para que os jogadores possam prever as movimentações que realizam e, quando acerta, evita a troca de mensagens. Por exemplo, considere um jogador prevendo a posição do outro; ambos executam o algoritmo e a mensagem de atualização ó apenas enviada quando o jogador que movimentou constata que o Dead Reckoning não previu a nova posição correta. O Dead Reckoning utiliza as leis da física para fazer uma previsão, assumindo que a movimentação ocorre em linha reta. Porem, ó notória sua baixa taxa de precisão. Neste trabalho, apresentamos uma nova estratégia para a predição de movimentação em jogos distribuídos baseada em aprendizado de maquina. A estratégia consiste de duas fases bem definidas, em que modelos de aprendizado são construídos utilizando os algoritmos: LWL, Bagging, Multilayer Perceptron e REPTree. Na primeira fase, um modelo de aprendizado classifica se o Dead Reckoning acerta ou erra sua predição. Em caso de acerto, o Dead Reckoning ó utilizado para fazer a previsão. Entretanto, em caso de erro, concretamente quando se conclui que o jogador muda sua direção de movimentação, íe utilizado um novo modelo de aprendizado para prever a nova direção. A estratégia proposta foi aplicada para o jogo World of Warcraft. Os modelos de aprendizado foram construídos utilizando a ferramenta Weka, com dados de traces do jogo extraídos de bases de dados publicamente disponíveis. Resultados mostram que a estratégia proposta obtém uma taxa de acerto médio de 76.60% para a primeira fase; e de 51.02% para a segunda fase. Destaca-se o algoritmo Bagging, que obtém uma taxa de acerto para a primeira e a segunda fases de 81.10% e 73.37%, respectivamente. Esses resultados confirmam o potencial da aplicação de aprendizado de máquina na previsao de movimentação em jogos distribuídos.

Abstract: In distributed multiplayer games, players have to keep a consistent vision of the positions of each other. Usually they exchange periodic messages about avatar movement updates. These messages not only represent an overload, but can also suffer delays that may lead to renderization inconsistencies. Traditionally, the Dead Reckoning algorithm is used by players for predict movement updates and, when the prediction is correct, a message is avoided. For example, consider a player predicting the position of another player; both players execute the algorithm and the message is only sent when the output of the Dead Reckoning is not the new position. The Dead Reckoning algorithm uses physics laws to make predictions, and it assumes that the movement is on a straight line. However, the low precision of this method is notorious. In this work, we present a new strategy to predict movement in distributed multiplayer games based on machine learning. The strategy consists of two well-defined phases, in which models are constructed using the following machine learning algorithms: LWL, Bagging, Multilayer Perceptron and REPTree. In the first phase, a learning model is used to classify whether the Dead Reckoning algorithm will make a correct or incorrect the prediction. If the prediction is right, then Dead Reckoning is executed. Otherwise, if the prediction is classified as incorrect, in other words, if the player changes the movement direction, another learning model is used to predict the new direction. The new strategy was applyed to the popular World of Warcraft game. The learning models were constructed using the Weka tool, using game trace data pu-blicly available. Results show that the proposed strategy has an average success rate of 76.60% for the first phase; the success rate for the second phase is 51.02%. Its stands out The Bagging algorithm produced the best results, the success rate for the first and second phases were of 81.10%and 73.37%, respectively. These results confirms the potential for the application of machine learning to predict player movement in distributed multiplayer games.