The Red and Blue Game
- Game specifications
- n: the number of nodes
- R: the number of rounds
- T: time limit
- Game dynamics
- The platform generates a random graph of n nodes
- For each round r =1 to R
- The blue player chooses a node S that has not been colored before. S and all nodes adjacent to S becomes blue (including the nodes that are previously red). This should be done in T seconds.
- The red player choose a node S' that has not been colored before S' and all nodes adjacent to S' becomes blue.
- The player with more nodes wins
- Any player who does not answer in time automatically loses.
- If all nodes are colored, then the game immediately ends and whomever with more nodes wins.
Bonus Project 1: platform development
What to do? Two platforms will be developed
- The client. This is the platform where any participating team develops their algorithms. The client should provide the following functionalities.
- Allows the team to play the game locally.
- Communicate with the server once the competition starts.
- The server. This is the platform that will only be run on an RPI computer (likely on campusopra). The server should provide the following functionalities.
- Host competitions. To achieve this, a protocol between the server and the client should be established. This can be an online gaming system (like Hearthstone), where any team can invite another team for competition (computers running the two algorithms must be online)
- Being able to show the process of any competition in live.
- Offers a UI for human players to play against an AI algorithm.
Deadline? The end of Spring Break.
How to participate?
This will be an open-source project. We need someone with RCOS leader experience to lead each of the two tasks. To participate, a student should
- Form a team of no more than 3 students (should also be the team for the competition) and choose a contact person
- The team contact person should send Lirong an email with preliminary thoughts and availability
- We will meet very often before the end of the spring break.
- First meeting: 2 pm on Friday in Lally 306.
Note: Bonus Project 1 is only for enthusiastic students who can commit a lot of time. So please do not participate if you do not feel extremely excited or do not have enough time (especially during the spring break). Stuents who do not contribute enough will not receive the bonus points. Lirong will be the only judge. Everyone is welcome to participate in Bonus Project 2, though.
Bonus Project 2: Competition, due May 3 midnight
Develop an algorithm to participate in the game. Any team that successfully completes the tournament with a non-trivial algorithm will get 3 pts. The winner will get extra 3 pts and an award certificate. We reserve the right to give credits and decide the winner. Bonus points might be given to innovative algorithms, even though it may not be the winner.
The platform and instructions are here https://github.com/JHBP/Red-Blue-Game/tree/wip/Jihoo
Submission and competition
- Please submit your codes with a short document describing how your approach is non-trivial, and the results and records of all games against the implemented algorithms, to TA Chunheng and cc me by May 3 midnight.
- We are still discussing the (offline) competition. The TA may run your codes offline. If so, please target the following settings.
- Randomly generate 5games with 100 nodes and 10 iterations (10 moves of each team)
- Each game (same graph) will be played twice, where each team moves first in one game.
- In each game, timeout is set to be 1 sec.
- Winner will be chosen using Copeland rule.
Note: please do NOT make your Bonus Project 2 codes public online at any time, even after the class.
List of trivial algorithms (not to say that algorithms not in this list are nontrivial)
- simple greedy or standard minimax search
- simple greedy with limited depth
- random choice based on simple scores (for example greedy or limited-depth greedy scores)
- any algorithm that has been implemented in the platform framework
List of non-trivial algorithms
- strategies based on innovative state abstraction and feature selection, for example deep learning
- strategies that learns and takes advantages of the opponent's strategies
- you may also train your algorithm by letting it play against other opponents, or even itself