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.

Google Online Preview   Download