A Game Engine on Distributed Systems using CORBA
BITS ZG629T: Dissertation
A Game Engine on Distributed Systems using CORBA
Dissertation work carried out at
HCL Technologies Ltd., GRO Chennai - 6
by
N. Vikram
2003HZ12424
Dissertation submitted in partial fulfillment of M.S., (Software Systems) Degree under the Supervision of (Gnanakkan Jesuraj, Project Manager, HCL Technologies Ltd., Chennai - 6)
[pic]
BIRLA INSTITUTE OF TECHNOLOGY & SCIENCE
PILANI (RAJASTHAN)
(April, 2005)
BITS ZG629T: Dissertation
A Game Engine on Distributed Systems using CORBA
Dissertation work carried out at
HCL Technologies Ltd., GRO Chennai - 6
by
N. Vikram
2003HZ12424
Dissertation submitted in partial fulfillment of M.S., (Software Systems) Degree under the Supervision of (Gnanakkan Jesuraj, Project Manager, HCL Technologies Ltd., Chennai - 6)
[pic]
BIRLA INSTITUTE OF TECHNOLOGY & SCIENCE
PILANI (RAJASTHAN)
(April, 2005)
CERTIFICATE
This is to certify that the Dissertation entitled A Game Engine on Distributed Systems using CORBA and submitted by N. Vikram having ID-No. 2003HZ12424 for the partial fulfillment of the requirements of M.S. (Software Systems) degree of BITS, embodies the bonafide work done by him under my supervision.
Place : Chennai Signature of the Supervisor
Date : 29/04/2005 (G.Jesuraj, Project Manager,
HCL Technologies Ltd., Chennai-6)
Abstract
This work aims at solving "Games-of-perfect-information" (Chess, Go, Othello,etc) using distributed Computing and CORBA. A callback model will be used to achieve parallelism and concurrency on multiple computers(10, 100 or 1000). This approach is a clincher in its dynamic client-server programming capabilities, location-transparency, scalability, extendability and security provided by CORBA.
In this attempt, it is planned to build a parallel distributed computing model for solving Chess, and to demonstrate that, given algorithms using similar game-programming/tree-searching techniques (like Minimax, AlphaBeta), this parallel method shall fare better than their sequential single machine counterparts.
Acknowledgements
To Anand Sridharan – the person who served as an inspiration all along the way. His encouraging words and constant striving to attain excellence made him a good role model for me. My gratitude does not go only for the last these months but dates back to the times when we spent time working on other challenging tasks.
To Eli Bendersky, Israel. Elegance is his virtue and simplicity his strength. When I was surfing the net about chess engines, I found Jamca to be fitting exactly to my needs. Eli used to give suggestions and asked questions which really kept me enthusiastic. My vision of Jamca and GeoDisco combining together to play on the Internet is not very far. Thanks Eli for all the support.
To Gnanakkan Jesuraj, my supervisor. He has been a constant source of motivation. I have learnt the art of keeping calm in the toughest of times from him. He played a dual role by being my Manager and supervisor, it has always been very comfortable working with him.
To Subbu Venkatraman, my additional supervisor. I have admired him for his principled and organized way of planning and doing things. Discussions with him really made me ask questions about the project and yielded good results.
To Vidya, my sister for her endearing support through out the project. She was the one who had to bear with all the boredom of listening to my jabber about this project until it got to a proper shape. She has helped me in more ways than one in this project and in normal walks of life.
To Deepak, my cousin whose project kept me motivated whenever I hit the wall. To Yuvaraja, alias doob, for his constant enthusiasm and Vivek, for spending time to understand the project. My sincerest gratitude to Mrs. Ambika Natarajan for her creative ideas during the preparation of the dissertation outline, which helped me in clarifying a lot of things far ahead of the project. To Vibhavari, for asking a lot of questions, the answers of which formed the dissertation outline.
To my mother and father for their never-ending love and affection.
A Game Engine on Distributed Systems using CORBA
Table of Contents
BITS ZG629T: Dissertation 1
Abstract 4
Acknowledgements 5
List of Figures 8
1. Introduction 9
1.1 Overview 9
1.2 Distributed Systems 9
1.3 Games of Perfect Information and Game-Trees 9
1.4 Objective of this work 10
2. Background 11
2.1 Essential Components of a Game Engine 11
2.2 Static Evaluation Functions 11
2.3 Move Generation 11
2.4 Tree Searching Techniques for Game Trees 12
2.4.1 Minimax Algorithm 12
2.4.2 Negamax Algorithm 13
2.4.3 Alpha-Beta Algorithm 13
2.4.4 Other Searching Enhancements 14
2.5 Existing Parallel Game Engine approaches 15
3.CORBA Primer 16
3.1 Introduction 16
3.2 Features of CORBA 16
3.2.1 Location Transparency 16
3.2.2 Scalability 16
3.2.3 Reliability & Security 16
3.3 CORBA Architecture 17
3.4 Interface Definition Language (IDL) Compilation & Mapping 18
3.5 Asynchronous Calls (Oneway Operations) / Callback 20
3.6 Implementation Repository 20
3.7 Advantages and Disadvantages of CORBA 21
4. Supervisor-Subcontroller-Volunteer Model 22
4.1 Introduction 22
4.2 Cryptanalysis Problem Specification 22
4.3 Workflow 22
4.4 CORBA IDL File for Cryptanalysis using callbacks 24
4.5 Application Pseudo Code 24
4.6 Role played by this model in GeoDisco 25
5. Reference Collector Module 26
5.1 Introduction 26
5.2 Specification & Design 26
5.3 Reference Collector IDL File and Application Pseudo Code 27
5.4 Role played by RefCollector in GeoDisco 28
6. Game Engine in a Collocated CORBA Environment 29
6.1 Intent 29
6.2 Collocated Environment 29
6.3 Negamax Algorithm 29
6.4 CORBA IDL File for Negamax Game Engine 30
6.5 Application Pseudo Code 31
7. Components of Chess Engine - JAMCA 32
7.1 Introduction 32
7.2 Board Representation 32
7.3 Game State & Conversion Routines (FEN) 33
7.4 Move Generation 35
7.4.1 Move Legality 35
7.4.2 Directions on Chess Board 35
7.4.3 Square Attacked 36
7.4.4 Making a Move 37
7.5 Static Leaf Position Evaluation 37
7.6 Jamca Integration with GeoDisco 37
7.6.1 Wrapper Functions 37
7.6.2 Linking Jamca into a dynamic library 38
8. Game Engine (Chess) on CORBA – Distributed Model 39
8.1 Introduction 39
8.2 Architecture 39
8.3 Components & WorkFlow 40
8.4 Outer Depth and Inner Depth 41
8.5 IDL File 41
9. Running the Demonstration 43
9.1 Environment 43
9.2 Build 43
9.3 Execution 43
10.Performance Results 45
10.1 Comparison Chart 45
11.Summary 46
12.Conclusion 47
13.Directions for Future Work 48
14.Bibliography & References 49
15.Checklist of items for the Final Dissertation Report 50
List of Figures
Figure 1.a Game Tree for Tic-Tac-Toe
Figure 3.a CORBA ORB Architecture
Figure 3.b IDL Compilation (C++ Language)
Figure 4.a Supervisor-Subcontroller-Volunteer Model for Cryptanalysis
Figure 5.a RefCollector
Figure 7.a Chess Board Geometry
Figure 8.a GeoDisco Architecture
Figure 10.a Performance comparison
Chapter 1
1. Introduction
1.1 Overview
From time immemorial, games like Chess, Go, etc have been entertaining, thought provoking and highly contemplative. With the proliferation of individual personal computers, the current trend is to build a powerful cluster from a collection of several ordinary computing machines to solve difficult problems in a collaborated and unified fashion.
The adage “Two Hands is better than one” is the norm of the day and this work too is build around it.
This is a distributed computation project that involves identifying and harnessing computing resources of multiple computers to solve computationally intensive problems. This system is focused on solving Chess, but the underlying system can be adapted for other games as well as for non-game-related applications.
1.2 Distributed Systems
Distributed computing technologies such as distributed computation, file sharing, and other P2P collaboration tools are poised to impact our social and technological evolution. It is a nice thing to know that many people are contributing their computers’ processing resources towards numerous exciting and challenging distributed projects. This area of research is promising and has diverse applications ranging from biology, mathematics, cryptography, physics, space etc.,
1.3 Games of Perfect Information and Game-Trees
Games-of-perfect information are ones where information specific to the game is known to both players, and there is neither secrecy or chance. Both players can see everything about the position on the chess board, and they know each other’s moves, for the moves are not played at the same time but rather in order. Games like Chess, Go, Othello are examples of games-of-perfect-information while Poker is not. Thus, Chess is a purely intellectual game, a perfect environment for testing Artificial Intelligence techniques.
Current chess programs view the game as a tree search in which each position corresponds to a node in the game-tree, and each move is a branch ( a transition from one node to the next). Thus the tree is made up of alternating layers or levels of moves for each side. In such games, the deeper one searches a game tree, the better the evaluation and response.
Given a board position, the best next move could be determined by considering all possible moves and resulting positions. The move selected should be the one that results in the board position with the highest evaluation. The evaluation function is one that calculates heuristically a value representing the status of the game. Most games are too complex for static evaluator to determine the best response. An efficient way is to “look ahead” several moves. Starting at any position, it is possible to construct a tree of the possible board positions that may result from each move. Such a tree is called a game-tree. For example, Refer to Figure 1.a that shows a simple game tree for a game of Tic-Tac-Toe upto a look ahead level of 2.
Figure 1.a Game Tree for Tic-Tac-Toe
The Game Tree of Tic-Tac-Toe can be easily searched and the best move can be solved with considerable ease. But, games of real interest like Chess or Go have trees so huge that there is no hope of investigating all the branches, and a program that runs in reasonable time can examine only a few levels below the current vertex of the tree. Solving Chess is too complex and resource intensive. An exhaustive search of all positions in Chess or Go is impossible today, given that “the total number of positions in a game of Chess is more than the number of drops of water in the ocean”. Nevertheless, a best effort mechanism is used by current computing machines to produce better outcomes than their opponents.
1.4 Objective of this work
The objective of this work is to build a parallel distributed computing model for solving games of perfect information like Chess. It will be demonstrated that given algorithms using similar game programming/tree-searching techniques like Minimax, Negamax, Alpha-Beta this parallel distributed method shall perform faster than their sequential single machine counterparts.
The vision of this work is to construct an architectural framework where in a collection of computers in the order of 10,100 or 1000 within a single or multiple organizations, coordinating together to play Games-of-Perfect-Information better than their single computer or other distributed counterparts.
The distribution task is carried out using CORBA as a bridge. Parallel models are built for parallelization in this work and they are used in solving Chess Games. Multiple processes running in multiple machines are coordinated in a systematic way to parallelize the searching of the game tree.
Chapter 2
2. Background
2.1 Essential Components of a Game Engine
The essential components of a Game Engine are
* Static Evaluation Functions
* Move Generation
* Tree Searching
2.2 Static Evaluation Functions
An evaluation function, also known as heuristic evaluation function or static evaluation function is used by game-playing programs to estimate the value or goodness of a position in the search algorithm. The evaluation function is typically designed to be fast and accuracy is not a concern (therefore heuristic); the function looks only at the current position and does not explore possible moves (therefore static).
One popular strategy for constructing evaluation functions is as a weighted sum of various factors that are thought to influence the value of a position. For instance, an evaluation function for chess might take the form
c1 * material + c2 * mobility + c3 * king safety + c4 * center control + …
It is important that the static evaluation function be designed and implemented carefully because, this is where game-specific intelligence is embedded.
2.3 Move Generation
Move Generation is one of the building blocks of any game engine. The generated moves from a given position must be accurate and the process should also be efficient. Given some game position, and all the transitions or moves available, the engine must search for all possible moves to give a correct response. Hence it is important that the move generator must return all the moves available in the current position.
The move Generation is game specific functionality. Different games have different rules and exceptions and care should be taken to programming the rules for a game. In this work, legal moves will be generated for Chess and TicTacToe. For advanced search techniques like Alpha-Beta and Iterative Deepening, move ordering is very important since, the earlier the better moves are investigated, the better.
2.4 Tree Searching Techniques for Game Trees
Tree search is one of the central algorithms of any game playing program. The term is based on looking at all possible game positions as a tree, with the legal game moves forming the branches of this tree. The leaves of the tree are all final positions, where the outcome of the game is known. Different Search Techniques by existing game engines are explained below.
2.4.1 Minimax Algorithm
A minimax algorithm is a recursive algorithm for choosing the next move in a two-player game. The player then makes the move that maximises the minimum value of the position resulting from the opponent's possible following moves.
There are two players involved, MAX and MIN. A search tree is generated, depth-first, starting with the current game position up to the end game position or a specified agreeable depth. Then, the final game position is evaluated from MAX's point of view, as shown in Figure 1.a. Afterwards, the inner node values of the tree are filled bottom-up with the evaluated values. The nodes that belong to the MAX player receive the maximum value of it's children. The nodes for the MIN player will select the minimum value of it's children.
The algorithm is given below.
MinMax (GamePosition game)
{
return MaxMove (game);
}
MaxMove (GamePosition game)
{
if GameEnded
return EvalGameState(game)
moves notify(key);
}
else
{
obtain ten references by using some mechanism like
implementation repository,IOR relfile, direct binding etc.,
foreach reference obtained
reference->assign(mine_this,krange,ptext,ctext);
Start listening on object mine_this for notifications
}
}
Cryptanalysis::notify(in long key)
{
if(parent_reference != NULL) //it is a sub-controller or a volunteer
{
parent_reference->notify(key);
}
else
{
anounce the successful key. //it is a supervisor
}
}
4.6 Role played by this model in GeoDisco
This model is used as a prototype for the distribution philosophy. The application chosen is cryptanalysis because, it is easily distributable, understandable and illustratable. The supervisor-subcontroller-volunteer model is used in later chapters for distributing the chess logic. The oneway asynchronous calling mechanism of CORBA is well studied and understood in this module. Also, the callback features are tested, proven and implemented.
Chapter 5
5. Reference Collector Module
5.1 Introduction
This module is used in the process of distribution of tasks. This process is used to invoke the required number of volunteers, collect their object references and return them. This is something like a customized implementation repository. The client needs to get the reference of the RefCollector alone. Using this reference, it can request for the references of the volunteers. The client can then invoke methods on the volunteer processes’ references directly. Such a decoupling helps in improving the mechanism of services invocation and reference collection from the core.
5.2 Specification & Design
The Reference Collector gets as input, the number of references required and an empty sequence to be filled with object References. The RefCollector starts the processes, collects their reference, fills the sequence and returns the sequence. The figure below explains the process.
[pic]
Figure 5.a RefCollector
5.3 Reference Collector IDL File and Application Pseudo Code
Based on the above design, an IDL file is written as below. The ChessEngine interface is the process that is requested to the RefCollector. An empty sequence of such references is sent as a parameter to be filled.
//IDL File Begins---
interface Chessserver
{
…//explained in Chapter 8
}
typedef sequence RefSequence;
interface RefCollector
{
void getRef( in long count, inout RefSequence refseq);
}
//IDL File Ends
Chessserver is the interface or the process that holds the logic for GameEngines. Game Engine related functionalities can be invoked using such a reference. A sequence of Chessserver references is declared as RefSequence. The getRef method takes as input the number of volunteers required an empty RefSequence refseq.
The Application Pseudo Code is explained below for the method getRef().
//Pseudocode –begins
void getRef( long count, ::Ref_sequence & ref_seq)
{
for(int i=0;ithis_; //Client obtains object reference by simple assignment.
The rest of the code, IDL and the business logic is similar to a distributed CORBA application. This approach is chosen because, it is speedy during the understanding and development of the business logic (Game Engine programming). This program can then be easily migrated to a distributed environment without much difficulty by using Implementation Repositories or IOR Relfiles.
6.3 Negamax Algorithm
The algorithm used is similar to the one described in section 2.x.x. It is given here again for easier reference and completeness. For a detailed algorithm description, refer to 2.x.x.
Negamax(depth)
{
var score, best, move_list, new_pos;
if(depth=0 || game_ovr(pos))
retirm evaluate(pos);
best= - infinity
move_list best) best = score
}
return best
}
6.4 CORBA IDL File for Negamax Game Engine
What was thought to be complex to solve, turned out to be surprisingly simple, thanks to flexible data structures, parameter passing modes and other features of CORBA IDL. The IDL file is given below followed by explanation. The board is represented as a string. This helps in decoupling game-independent Search Logic and the Game-specific functionalities.
//IDL File --begins--
struct board
{
string boardstr_; //This contains the game specific board.
};
typedef sequence BoardSeq; //sequence of struct boards
interface GameEngine
{
long Negamax( in board bd, in long depth, in long player);//Game independent
void GenerateMoves(in board bd, inout BoardSeq boseq); //Game specific
long Evaluate(in board bd, in long player); //Game specific
};
//IDL File --ends--
The struct board is a game specific structure, which can hold the board state of Chess( or any other game). The heart of the algorithm is the function Negamax. It is called recursively till the specified depth is reached.
The interesting component is GenerateMoves. An empty boardsequence(BoardSeq) is created and passed to GenerateMoves. This sequence is filled with new possible boards and returned. This is implemented in a clean manner thanks to CORBA sequences and inout parameter passing specification.
The Evaluation function takes in a board and based on certain heuristics and the player to move, returns a value for the leaf node.
Another useful capability realized by using IDL, was the board data structure could be passed between IDL member functions seamlessly without conversions as is evident in the next section.
6.5 Application Pseudo Code
GameEngine::Negamax( in board bd, in long depth, in long player)
{
if(depth ==0)
return Evaluate(bd, player); //Return the evaluation value at leaf nodes
best = -infinity;
BoardSeq boseq; //Empty Sequence of boards
GenerateMoves( bd, boseq); //This will fill the sequence with new
//possible boards
foreach (boseq.length() > 0)
{
score= -Negamax( boseq[i], depth-1, !player); //boseq[i] –easy use of sequences
if(score > best)
best = score;
}
return best;
}
GameEngine::GenerateMoves(in board bd, inout BoardSeq boseq)
{
Determine the new possible boards from the current board
foreach newboard in list of possible new boards //This code fills the sequence with
{ boseq.length(i); //new possible boards.
boseq[i++]=newboard;
}
}
GameEngine::Evaluate(in board bd, in long player)
{
Game specific Functionalities.
For Chess - Material balance, Mobility,
Castled kings, blocked pawns, doubled rooks, etc.,
}
The above model was tested with different game positions of Chess and the result was succesful. This module was a significant step forward towards realizing the dissertation goal.
Chapter 7
7. Components of Chess Engine - JAMCA
7.1 Introduction
Jamca is a Chess Agent written by Eli Bendersky(spur4444@). It is written in C++ and compiles with any standard compiler. Its components include Board Representation, Move Generation and conversion routines. Search Engine is not included in Jamca. Static Position Evaluation is added to it. This module explains the organization of Jamca thus giving us an insight into game engine programming. GeoDisco uses Jamca for Movegeneration, Position Evaluation. The integration of GeoDisco Search Engine with Jamca is dealt with in this module.
7.2 Board Representation
The game board is probably the most important data structure in chess programming. It represents the state of the game – in some sense it is the beginning of all the algorithms that work together to make the chess agent tick. Evaluation and move generation depend on the board representation heavily. It will decide how easily and efficiently these operations can be performed.
|110 |111 |112 |
|1 |3 |30 |
|2 |30 |58 |
|3 |420 |94 |
|4 |10800 |1500 |
.
[pic]
Figure 10.a Performance comparison
Chapter 11
11.Summary
In this work, considerable light was thrown on the different components of a parallel distributed game engine and progress was made in a systematic approach.
The application of distributed callback model in Game Engines is a new approach and promises gratifying results. The excellent dynamic client-server programming capabilities of CORBA, together with its flexible data structures contribute very well to programming over a distributed environment.
The domain related gaming algorithms were studied, analysed and implemented in this distributed system. It was also demonstrated that such a model can be used for other parallelizable problems in an efficient and a simple manner. The programs that were written are suitably commented and documented for future references.
Chapter 12
12.Conclusion
This work took an innovative approach in solving games. Parallelism in Chess is still in its infancy and this work suggests a realizable approach. The final product confirms to the requirements in that, it plays correct chess(functionality), quicker than its single machine/process counterparts and it is readily extensible and scalable. It has been demonstrated with examples that this technique of parallelization can be used for other applications too. This work puts brings into perspective a new way of solving problems in a concurrent fashion which is scalable and reliable.
Chapter 13
13.Directions for Future Work
There are a lot of enhancements that are in the pipeline. This engine can become an expert with different improvements. These include improvements in
• Distribution techniques
• Searching Techniques (Alpha-Beta & Other advanced methods)
• Reference collection
• Static Leaf Position evaluation
• Performance Measurement and Improvement
Few issues that need to be addressed in making it a better product are
• Multi-machine co-ordination issues
• Portability issues
• Multi-ORB vendors coordination
• Documentation methods
Chapter 14
14.Bibliography & References
· “Advanced CORBA Programming with C++” - Michi Henning, Steve Vinoski
· “Data Structures and Program Design in C++” - Robert. L. Kruse
· “Data Structures using C and C++” - Yedidyah Langsam, Moshe. J. Augenstein, Aaron.
M.Tenenbaum
· “The C++ Programming Language” – Bjarne Stroustroup
·
·
.
Chapter 15
15.Checklist of items for the Final Dissertation Report
This checklist is to be attached as the last page of the report.
This checklist is to be duly completed by the student and verified by the Supervisor.
|1. |Is the report properly hard bound? |Yes / No |
|2. |Is the Cover page in proper format? |Yes / No |
|3. |Is the Title page (Inner cover page) in proper format? |Yes / No |
|4. |(a) Is the Certificate from the Supervisor in proper format? |Yes / No |
| |(b) Has it been signed by the Supervisor? |Yes / No |
|5. |Is the Abstract included in the report properly written? |Yes / No |
|6. |Does the Report contain a summary of the literature survey? |Yes / No |
|7. |Does the Table of Contents include page numbers? |Yes / No |
| |(i). Are the Pages numbered properly? |Yes / No |
| |(ii). Are the Figures numbered properly? |Yes / No |
| |(iii). Are the Tables numbered properly? |Yes / No |
| |(iv). Are the Captions for the Figures and Tables proper? |Yes / No |
| |(v). Are the Appendices numbered properly? |Yes / No |
|8. |Is the conclusion of the Report based on discussion of the work? |Yes / No |
|9. |Are References or Bibliography given in the Report? |Yes / No |
| |Have the References been cited inside the text of the Report? |Yes / No |
| |Is the citation of References in proper format? |Yes / No |
|10. |A Compact Disk (CD) containing the softcopy of the Final Report and a copy of the Final Seminar |Yes / No |
| |Presentation made to the Supervisor / Examiner (both preferably in PDF format only) has been placed in a | |
| |protective jacket securely fastened to the inner back cover of the Final Report. | |
Declaration by Student:
I certify that I have properly verified all the items in the checklist and ensure that the report is in proper format as specified in the course handout.
Place : Chennai Signature of the Student
Date: 29/04/2005 Name: N. VIKRAM
I have duly verified all the items in the checklist and ensured that the report is in proper format.
Place : Chennai Signature of the Supervisor
Date : 29/04/2005 Name: G.Jesuraj
-----------------------
-2
-1
2
1
0
1
+
+
+
+
+
+
-
-
-
+
X
O
O
O
O
X
X
O
X
X
X
O
X
X
X
-1
1
-2
IDL Developer
x.idl
IDL Compiler
Server Developer
x.h
x.cpp
x.skel.h
x.skel.cpp
Srv.cpp
app.cpp
Client Developer
Client Executable
Server Executable
C++ ORB RunTime Library
RPC
0 - 1000
0 - 100
101-200
201-300
301-400
901-1000
11-20
101-120
0-10
90-100
191-200
240-250
901-910
991-1000
The matching key is 245
supervisor
volunteers
subcontrollers
RefCollector
ChessServer
Getref()
Chess server
Chess server
Chess server
RefSeq
invoke
references
Super-visor
A
Sub-controller
C
Sub-controller
D
Sub-controller
B
Sub-controller
Reference Collector
Volun-teers
Outer Depth=1
Outer Depth=2
1
2
3
4
5
6
7
8
9
InnerDepth=2
J M G
J M G
1
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- video game effects on kids
- video game impact on kids
- solving systems using matrices calculator
- last game played on computer
- how to open game files on mobile
- xbox game pass on pc
- xbox game streaming on ios
- download game engine for pc
- 2d game engine no coding
- 3d game engine no coding
- no coding game engine free
- 3d game engine without coding