Due to the progress of Internet technology and technical improvement, the growths of multimedia products and services ,such as Multimedia Message Service¡]MMS¡^, Multimedia on Demand¡]MoD¡^, Video Conferencing, and Digital TV, are very fast. All of these services need good video compression and audio compression standards to support. It is impossible to transmit source data of multimedia on networks. Motion Estimation needs the most computing complexity in the video compression. In our research, we focus on how to reduce candidate blocks and keep video quality. We study some fast motion estimation algorithms and architectures, and design a fast motion estimation architecture which supports resolution of 1280x720 at 30fps frame rate in HDTV specification based on hierarchical motion estimation algorithm. In the limit of hardware resources and the compressed video quality, the architecture can improve inter-coding performance. Two adjacent MacroBlocks have similar Motion Vector in our observation. We arrange a 16x8 processing element array to deal with two adjacent MacroBlocks together. The design can reduce a lot of clock cycles in the hierarchical motion estimation architecture, and keep high video quality. Furthermore, we propose a search range prediction method¡]called ASR¡^which reflect the motion behavior of video sequences into search range on MB-By-MB Basis. ASR can reduce the unnecessary operation of candidate blocks and keep very high video quality compared with Full Search Block Matching algorithm by the implementation in official software of the new video compression standard, Joint Model of H.264/AVC.

The most basic requirement for any computer controlled game agent in a video game is to be able to successfully navigate the game environment. Pathfinding is an essential component of any agent navigation system. Pathfinding is, at the simplest level, a search technique for finding a route between two points in an environment. The real-time multi-agent nature of video games places extremely tight constraints on the pathfinding problem. This study aims to provide the first complete review of the current state of video game pathfinding both in regards to the graph search algorithms employed as well as the implications of pathfinding within dynamic game environments. Furthermore this thesis presents novel work in the form of a domain specific search algorithm for use on grid-based game maps: the spatial grid A* algorithm which is shown to offer significant improvements over A* within the intended domain. Copyright / Dissertation (MSc)--University of Pretoria, 2011. / Computer Science / unrestricted

The strategy game Risk is a very popular boardgame, requiring little effort to learn but lots of skill to master.The aim of this project is to explore the fortification phase of thegame, where the player’s troops are moved between territories.Our method is based on adapting Monte Carlo tree search(MCTS) to Risk. To improve the troop movements, we proposetwo techniques, hierarchical search and progressive bias. Thesemethods, combined with other extensions of MCTS are thencompared against a baseline player of the game. Our results showthat hierarchical search improved the MCTS agent’s playingpower and the progressive bias have potential to improve theagent but needs further investigation. / Strategispelet Risk är ett väldigt populärt brädspel som är lätt att lära sig men svårt att bemästra. Syftet med detta projekt är att utforska spelets befästningsfas, där spelarens trupper flyttas mellan territorier. Vår metod är baserad på en anpassning av Monte Carlo trädsökning (MCTS) till Risk. För att förbättra trupprörelserna föreslår vi två tekniker, ”hierarchical search” och ”progressive bias”. Dessa metoder, i kombination med andra tillägg av MCTS, jämförs sedan mot en standard agent i spelet. Våra resultat visar att hierarchical search förbättrade MCTS agentens spelstyrka och att progressivce bias har möjlighet att förbättra agenten men kräver fortsatt utforskning. / Kandidatexjobb i elektroteknik 2020, KTH, Stockholm