game_of_civilization

GAME OF CIVILIZATION

Authors

Yating Han (yatingh)
Yuying Qian (yuyingq)

Project Repo
Project Website

Table of contents

Running the Game
Final Report
Project Checkpoint
Project Proposal
Work Breakdown
Contacts

Running the Game

Game of Life: under GoL, run make seq or make cuda
Game of Civilization: under GoC, run make baseline or make cuda

Project Report

Project Report

Project Checkpoint

Project Status

We’ve successfully implemented the original game of life. It does not have a visualization yet. However, we can see it working from terminal output. However, we discovered some major design flaws in the game. In the proposal, we described three types of “civilizations”: village, city, and nation. As we discussed the implementation details, we realized that area division of these entities are exactly the same in terms of algorithm design / parallelization: we could just traverse through each “square” and determine if it meets the requirements we defined. A major flaw in this design is that every entity could be characterized by multiple overlapping squares, depending on where the center is. In addition, we proposed that all nations should be squares which is not the case in real world. Therefore, we want to switch to a simpler rule (with just “tribes” and “nations”) but use a more precise (and interesting) algorithm for characterization.

Here are the revised rules:

Original Rules
  • Any live cell with fewer than two live neighbours dies, as if by underpopulation.
  • Any live cell with two or three live neighbours lives on to the next generation.
  • Any live cell with more than three live neighbours dies, as if by overpopulation.
  • Any dead cell with exactly three live neighbours becomes a live cell, as if by reproduction.
Map
  • Any living population belongs to a tribe. Nearby lives belongs to the same tribe. (detailed rule determined by the search algorithm)
  • If tribes are in close proximity, they will unite with each other and form a nation.
Technology & War
  • Only tribes above a basic power level may declare war.
  • Truce condition: Entities engaged in war in a certain round will not go to war again in the next 5 rounds.

The first phase is still updating the pixels, which follows the original game rules. It will be done with a relatively simple CUDA function because each pixel only depends on itself and its neighbor. The second phase will be doing some graph searching or clustering on the 2D array and determining the boundaries of the cities and nations. We are still planning to use CUDA, subjected to change as discussed in the issue section. It is more challenging than the algorithm we described in the proposal, as graphs are inherently recursive data structure and is hard to parallelize using CUDA. We will use BFS which offers more opportunities for parallelism. Finally, we will pairwise-compare the civilizations and determine if they should go to war, then update the pixels once again.

Evaluation

Because we revisited the rules, we are about one week behind schedule. However, we believe that we will still get all the deliverables done because we will both stay on campus during Thanksgiving break. As we revisited the algorithm, we will probably have more interesting nice-to-haves such as implementing different graph searching algorithm or clustering.

We plan to achieve the following:

Issues

We noticed several loopholes in our design of the game rules, like the characterization of entity territory(mentioned in the first section), the expansion rule of a nation (as of now, once the first nation is established, it will soon devour all the nearby entities because the war condition is too easy to be triggered), lack of truce condition (if two entities go to war in a certain round, they will continue fighting in the subsequent rounds until one of them dies or downgrades), etc etc. We realize game design is not as simple as we thought it is :)

We are trying to evaluate which programming model works the best for graph computation. When traversing the map to compute area division of the cities, each 10x10 block is treated as a vertex on the graph and the close ones are grouped into the same city(vertex). To find nations, every city is treated as a vertex and vertices(cities) that are close to each other are grouped together to form a cluster(nation). Although we used CUDA to implement the basic rules of life, where each member of the population is evaluated using the exact same logic, it might not be the best choice for graph computation. From what we learned from assignment 3, it seems OpenMP would work better for algorithms involving recursion. However, the program does not work quite right. We’re still debugging the issue. Our next step is either improving our existing algorithms or exploring new frameworks like GraphLab or trying new algorithms like K-means clustering (which we now think might be a more reasonable choice). Experiments with different kinds of implementations could be pretty time consuming.

Updated Schedule

When What How Who
November Week 3 A The parallel implementation Use CUDA to parallelize basic rules of life Both
November Week 3 B BFSn Parallelize BFS algorithm in area division Both
November Week 4 A K-means Clustering Parallelize K-means clustering in area division Both
November Week 4 B Parameter tuning Optimize the performance Both
December Week 1 Final project report (10 pages) Final project report submission by Friday, Dec 6th. Both

Project Proposal

Project Summary

We are going to implement an enhanced version of Conway’s Game of Life, i.e. Game of Civilization, on GPU, to simulate the evolution of lives, villages, cities and nations.

Background

In the original Game of Life, the status of every cell in the world follows a simple set of rules:

Orignal Game

To make the evolution more interesting, we will add a new set of rules to simulate the development of villages, cities and nations:

Map
  • Any 20x20 block with more than 20 living cells would automatically upgrade to a village.
  • Any 50x50 block with more than 50 cells would upgrade to a city.
  • Any 1000x1000 block with more than 20 cities would upgrade to a nation.
  • Once an entity is upgraded to a higher level, it will never downgrade even when the population falls below the criteria of its current level, unless population dies down to zero or it’s conquered by an entity of lower level. (See the War section)
Technology

Let the history of a village/city/nation be the number of years it has existed, n.

  • The technology index of a village or city = n/4
  • The initial technology index of a nation (when n=0) follows the city with highest technology index. The index would increment by 2 every subsequent year.
War
  • Power of any entity = technology index * population
  • Entity with higher power wins the war and conquers the opponent entity.
  • Villages will not engage in wars.
  • War casualty = (opponent power / entity power) * ( ¼ * population) This equation computes how many cells would die in a war. Cells are killed at random.
  • Any two cities D1 distance apart or closer would go to war. The map remains unchanged.
  • Any nation and city D2 distance apart or closer would go to war.
    • If the nation conquers the city, the city will be colonized. The resulting technology index will follow whoever is higher.
    • If the city wins, the nation collapses: the map will recompute the area division. New cities and villages will inherit the nation’s technology and operate independently.
  • Any two nations D3 distance apart or closer would go to war. The winner will colonize the loser if the power ratio (winner power/ loser power) is greater or equal to 2. Otherwise, the map remains unchanged.

Approach

By the end of the semester, we want to parallelize the simulation by breaking it down to the following:

The Challenge

Resources

We are planning to run the game on GPU. Depending on the scope of the project, we might also implement a CPU version and compare the results. The code will be written from scratch.

Goals and Deliverables

Plan to achieve:

Hope to achieve:

Demo:

Platform Choice

Computer:

We choose to run the game on GPU because a set of homogenous computation needs to be done for each cell and it’s easy to map the cells in the world map to the threads on GPU.

Language:

Kernel will be implemented in CUDA so that it can run on GPU, while the GUI will be implemented in Python to make our life easier.

Schedule

When What How Who
November Week 1 The original Game of Life The game can take in an initial population configuration and simulate the evolution automatically which only follows the 4 fundamental rules of life.
November Week 2 Rules of War and Technology The game is able to identify (1) The villages, cities and nations on the map and mark the territories with different colors; (2) Which of the entities would declare war on each other and compute the population change due to the conflicts.
Checkpoint: Nov 18 Checkpoint Writeup Update the project web page and submit the writeup to Gradescope
November Week 3 The parallel implementation Implement the CUDA version of the game and examine the speedup.
November Week 4 Parameter tuning Optimize the performance
December Week 1 Final project report (10 pages) Final project report submission by Monday, Dec 9th.

Work Breakdown

Yating: 50%
Eryn: 50%

Contacts

Yating Han (yatingh at andrew)
Yuying "Eryn" Qian (yuyingq at andrew)