Back to search

University of British Columbia

αβService : an asynchronous parallel tree search service for ChessGrid

Abstract

dc:description

The performance of game playing programs depends heavily on the strength of the search algorithm used. As such, several research activities have been conducted to speed up game tree search algorithms by using parallel machines. Most of these algorithms are targeted towards shared memory models or tightly coupled systems. In recent years, the rapid progress of Grid computing has led to finding a Grid solution to difficult computational problems. To ensure interoperability among diverse computational resources in the Grid, Service Oriented Architecture is used to achieve loose coupling among interacting software agents, known as services. Finding an efficient tree search algorithm in this new paradigm is a challenging problem. This thesis proposes a new service oriented algorithm, called αβService, which targets loosely coupled systems. It creates a tree of services to search the game tree concurrently. The necessity of synchronization points is eliminated with a notification mechanism, enabling the concurrently running services to continue their asynchronous search without waiting for others to finish. The αβService is implemented as a Grid service in Globus using Globus Toolkit 3. The service is deployed to create a ChessGrid testbed and experiments are conducted with a branching factor controlled test suite which demonstrates an average speedup of 2.61 with six machines.

Degree

thesis:*
Name thesis:degree_name
Master of Science - MSc
Level thesis:degree_level
master's
Discipline thesis:degree_discipline
Computer Science
Grantor dc:publisher
University of British Columbia
Year dc:date
2005

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pramanik, Sukanta

Rights

dc:rights
Statement dc:rights
  • For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use.
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/16669

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Pramanik, Sukanta. αβService : an asynchronous parallel tree search service for ChessGrid. master's thesis, University of British Columbia, 2005. http://hdl.handle.net/2429/16669