Project 03: Superball!
- CS302 Data Structures and Algorithms II
- (http://www.cs.utk.edu/-plank)
- The original file: http://www.cs.utk.edu/-plank/plank/classes/cs302/Labs/Lab5/ (http://www.cs.utk.edu/-plank/plank/classes/cs302/Labs/Lab5/)
Project 03: Superball!
Superball is a simplistic game that was part of a games CD for Dr. Planks old Windows 95 box. It works as follows. You have a 810 grid which is the game board. Each cell of the game board may be empty or hold a color:
- P Purple: worth 2 points.
- B Blue: worth 3 points.
- Y Yellow: worth 4 points.
- R Red: worth 5 points.
- G Green: worth 6 points.
The board starts with five random colors set. On your turn, you may do one of two things:
- You may swap two cells. After the swap, five new random cells will be filled with a random colors.
- You may score a cell. To score a cell, the cell must be one of the goal cells, and there are sixteen of these, in rows 2-5, columns 0, 1, 8 and 9. (Everything is zero indexed). Moreover, there must be at least five touching cells of the same color, one of which must be the goal cell that you want to score. When you score, you get the sum of the cells connected to the cell that you are scoring, and then all of those cells leave the board, and three new random ones are added.
Dr. Plank has a tcl/tk/shell-scripted Superball player at /home/jplank/Superball. Simply copy that directory to your home directory: UNIX> cp r /home/jplank/Superball $HOME
Then you can play it with /Superball/Superball. The high score probably wont work youll have to change the open command in the file hscore to the name of your web browser.
Lets look at some screen shots. Suppose we fire up Superball:
Project 03: Superball!
The goal cells are marked with asterisks, and there are five non-empty cells. Our only legal action is to swap two cells Dr. Plank swaps cells [3,6] and [5,8] below. This will make those two blue cells contiguous. In the game, we can do that by clicking on the two cells that we want to swap. Afterwards, five new cells are put on the screen. Heres the screen shot:
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Dr. Plank does a bunch more swaps and ends up with the following board:
https://web.eecs.utk.edui-semrich/ds20/assignments/proj03.html
Project 03: Superball!
We can score the green cells by clicking on cell [2,1], [3,0], [3,1] or [4,0] and then clicking Collect. This will score that group of eight green squares, which gets us 48 points (8*6), and three new cells will be added:
Project 03: Superball!
There are no cells to score here (the blues ones in the lower right-hand part of the board only compose a group of four). So Dr. Plank now reverts to swapping. Suppose we keep doing this until we reach:
Were in trouble. Dr. Plank has now got these beautiful groups of red, green and purple cells, but he cant score any of them because they are not connected to a goal. Dang. We can only score those two groups of blue cells. When Dr. Plank does that, he is only left with four open squares, and we cant score anything:
Project 03: Superball!
Perhaps Dr. Plank should have been a little more thoughtful while playing the game. Regardless, he is stuck. We simply swap two random squares and end the game:
Project 03: Superball!
Oh well should have done that swap a little sooner.
For this project, we are going to deal with a text-based version of the game. Our programs will have the following parameters:
- rows the number of rows on the game board. Although the tcl/tk version has that set to eight, our programs will handle any number.
- cols the number of columns on the game board.
- min-score-size the number of contiguous cells that have to be together in order to score them. This is 5 in the tcl/tk version
- colors this must be a string of distinct lower-case letters. They represent that the colors that a cell can have. The point value of the first of these is 2, and each succeeding character is worth one more point. To have the same values as the tcl/tk game, this parameter should be pbyrg.
Dr. Plank has written an interactive game player. Call it as shown below: UNIX> cd /home/jplank/cs302/Labs/Lab5/
UNIX> sb-player
usage: sb-player rows cols min-score-size colors player interactive(yln) output(yln) seed
UNIX> sb-player 8 10 5 pbyrg y y
Empty Cells: 75 Score: 0
Your Move:
The format of the board is as follows: When a letter is capitalized, it is on a goal cell. Dots and asterisks stand for empty cells asterisks are on the goal cells. If you click on the Print Boards button in the tcl/tk game, it will print out each board on standard output in that format. Thats nice for testing.
You can type two commands:
____ II
SWAP rl cl r2 c2 SCORE r c
In the board above, you cant score anything, so youll have to swap. Well swap the blue cell in [2,2] with the green one in [7,2]:
|
|
Project 03: Superball!
Its incredibly tedious play along with us:
| Empty Cells: 70 | Score: | 0 | Empty Cells: 65 | Score: | 0 | Empty Cells: 60 | Score: | 0 | Empty Cells: 55 | Score: | 0 | Empty Cells: 50 | Score: | 0 |
| .r.. | .b | .b.. p | .b..rpp | .r..rgypp | ||||||||||
| .g.. | ||||||||||||||
| **g.b** | **g.bB* | **g.p..bB* | **g.p..bB* | **g.p..bB* | ||||||||||
| **.b.** | ** . b.** | **rb.*R | **gb.*R | **gb.*B | ||||||||||
| **.g.*y | P*.g.RY | P*.g.YY | P*.g.YY | P*.g.YY | ||||||||||
| ** *p rrb | ** *p.. rr.gry | ** *P rr.grr. | **.g.*p.. rrrrrr | **.g.*pprrrrrrr.p. | ||||||||||
| Your Move: SWAP 0 1 | 7 2 | Your Move: SWAP 7 3 | 4 8 | Your Move: SWAP 3 2 | 7 1 | Your Move: SWAP 3 9 | 0 1 | Your Move: SWAP 6 0 | 0 1 | |||||
| Empty Cells: 45 | Score: | 0 | Empty Cells: 40 | Score: | 0 | Empty Cells: 35 | Score: | 0 | Empty Cells: 30 | Score: | 0 | Empty Cells: 37 | Score: | 50 |
| .p..rgy.pp | .p..rgypp | .p..pgypp | .p.pgypp | .p.pgypp | ||||||||||
| .g..gb. | .g..gb. | .g..g.r.b. | .g.pg.b.b. | .g.pg.b.by | ||||||||||
| **g.p..bB* | **g.p.pbB* | G*g.p.pbB* | G*g.p.pbB* | G*g.p.pbB* | ||||||||||
| **gb.*B | R*gby*B | R*gby*B | R*g.r.by*B | R*g.r.byGB | ||||||||||
| P*.g..y.YY | P*.g..y.YY | P*.g..y.YY | P*pg..y.YY | P*pg..y.YY | ||||||||||
| **.g..yp*prrrrrrrr.py | P*.g..yp*Yrrrrb..rrrr.pp | R*.g..yp*Yr..grrrb..rrrrbppy.. | R*.g.bypBYr..grrrbrrrrrppy | **.g.bypBYgb..-1)..-PPY | ||||||||||
| Your Move: SWAP 5 9 | 7 6 | Your Move: SWAP 5 0 | 0 4 | Your Move: SWAP 7 4 | 1 6 | Your Move: SCORE 5 | 0 | Your Move: |
Project 03: Superball!
Program #1: Sb-read
Dr. Plank has provided sb-read.cpp (http://www.cs.utk.eduNplank/plank/classesics302/Labs/Lab5/sb-read.cpp) for us. This program takes the four parameters detailed above, reads in a game board with those parameters and prints out some very basic information. For example, the following board:
May be represented by the following text (in input-1.bct (http://www.cs.utk.eduNplankiplank/classes/cs302/Labs/Lab5/input-1.bct)):
- )(YrYY13 y.rgyppyp **gg.yrpPP GGgbgybp** R*bg.yrp*P G*gygyypY* yyybpby.pb .pgg.ypbb
When we run sb-read on it, we get the following:
Project 03: Superball!
UNIX> sb-read 8 10 5 pbyrg < input-1.txt
Empty cells: 20
Non-Empty cells: 60
Number of pieces in goal cells: 8 Sum of their values: 33 UNIX>
There are three purple pieces in goal cells, one yellow, three green and one red. That makes a total of 32 + 4 + 5 + 3*6 = 33.
You should take a look at sb-read.cpp (http://www.cs.utk.eduNplankiplank/classes/cs302/Labs/Lab5/sb-read.cpp). In particular, look at the Superball class:
| class Superball {public:Superball(int argc, char **argv); int r;int c;int mss;int empty;vector <int> board; vector <int> goals; vector <int> colors;}.; |
Mss is min-score-size. Empty is the number of empty cells in the board. Board is a vector of r* c integers. The element in [i,j] is in entry board[i*c+j], and is either .,’ or a lower case letter. goals is another array of r* c integers. It is equal to 0 if the cell is not a goal cell, and 1 if it is a goal cell. Colors is an array of 256 elements, which should be indexed by a letter. Its value is the value of the letter (e.g. in the above example, colors[p] = 2).
sb-read does all manner of error checking for you. It is a nice program from which to build your other programs.
Program #2: Sb-analyze
You are to write this one.
With sb-analyze, you are to start with sb-read.cpp as a base, and augment it so that it prints out all possible scoring sets. For example, in the above game board (represented by input-1.txt (http://www.cs.utk.eduNplank/plankiclasses/cs302/Labs/Lab5/input-tbct)), there are two scoring sets the set of 10 purple cells in the upper right-hand corner, and the set of 6 green cells on the left side of the screen. Here is the output to sb_analyze:
Project 03: Superball!
UNIX> sb-analyze
usage: sb-analyze rows cols min-score-size colors
UNIX> sbanalyze 8 10 5 pbyrg < input1.txt Scoring sets:
Size: 10 Char: p Scoring Cell: 2,8 Size: 6 Char: g Scoring Cell: 3,0 UNIX>
Each set must be printed exactly once, but in any order, and with any legal goal cell. Thus, the following output would also be ok:
UNIX> sb-analyze 8 10 5 pbyrg < input-1.txt Scoring sets:
Size: 6 Char: g Scoring Cell: 3,1 Size: 10 Char: p Scoring Cell: 2,9 UNIX>
Think about how you would use the disjoint sets data structure to implement this it is a straightforward connected components application. We would recommend augmenting your Superball class with a DisjointSet, and then having a method called analyze_superball() that performs the analysis.
Heres another example:
This is in the file input-2.txt (http://www.cs.utk.eduijplank/plank/classes/cs302/Labs/Lab5/input-2.txt):
7/12/2020 Project 03: Superball!
yyggyryybp ggrgpyppyp RBgggyrpPP GGgggybpPP RGygryrpBP YGyygyypYB yyybpbyppb ppggyypbbb
UNIX> sb-analyze 8 10 5 pbyrg < input-2.txt
| Scoring | sets: | ||||
| Size: | 14 | Char: | g | Scoring Cell: | 5,1 |
| Size: | 15 | Char: | p | Scoring Cell: | 4,9 |
| Size: | 7 | Char: | y | Scoring Cell: | 5,0 |
| Size: | 5 | Char: | b | Scoring Cell: | 5,9 |
| UNIX> | |||||
Program #3: Sb-play
Your next program takes the same arguments and input as sb-analyze. However, now its job is to print a single move as would be accepted as input for the sb-player program. In other words, it needs to output a SWAP or SCORE line with legal values.
If you have fewer than five pieces and cannot score any, you will lose the game you should do that by swapping two legal pieces so that the game can end.
The sb-player program takes as its 5th argument the name of a program that it will use for input. Dr. Plank also also provided three programs sb-play, sb-play2 and sb-play3 in that directory. sb-play simply swaps two random cells until there are fewer than five empty, then it scores a set if it can. The other two are smarter, but are by no means the best one can do.
Heres sb-player running on sb-play2 (note, sb-player creates a temporary file, so you must run it from your own directory):
UNIX> /home/jplank/cs302/Labs/Lab5/sb-player 8 10 5 pbyrg /home/jplank/cs302/Labs/Lab5/sb-play2 y y -Empty Cells: 75 Score: 0
g
* *
*Pr..
** . . p . . . **
b
Type Return for the next play
Project 03: Superball!
It waits for you to press the return key. When you do so, it will send the game board to /home/jplank/cs302/Labs/Lab5/sp-play2 and perform the output. Heres what happens: Move is: SWAP 5 4 3 2
Empty Cells: 70 Score: 0
g.. g
Y
**. **
*pp **
**.. G*
**.. r.. **
..g b
g.
Type Return for the next play
You can bet that the next move will swap that b with one of the gs: Move is: SWAP 6 8 0 0
Empty Cells: 65 Score: 0
Type Return for the next play
And so on. If you run it with n for the 6th argument, it will simply run the program without your input:
Project 03: Superball!
UNIX> /home/jplank/cs302/Labs/Lab5/sb-player 8 10 5 pbyrg /home/jplank/cs302/Labs/Lab5/sb-play2 n y -Empty Cells: 75 Score: 0
**y..y..**** **
*p.. **
pg
Move is: SWAP 3 5 3 2
a bunch of output skipped
Empty Cells: 1 Score: 505
yyrrgggpyy grrbppg.yg GYbgygggPB GBggpgbpPB PPgggggrYB YBbybgpbYR pprrrggggr byyrppppgg
Move is: SWAP 0 1 7 5
Game over. Final score = 505 UNIX>
Even though there were no good moves at the end, the program did a final SWAP so that the game could finish.
If you run with the 7th argument as n, it will only print out the end result, and the last argument can specify a seed (it uses the current time if that argument is -), so that you can compare multiple players on the same game:
| UNIX> /home/jplank/cs302/Labs/Lab5/sb-player 8 Game over. Final score = 0UNIX> /home/jplank/cs302/Labs/Lab5/sbplayer 8 Game over. Final score = 855UNIX> /home/jplank/cs302/Labs/Lab5/sbplayer 8 Game over. Final score = 2572UNIX> | 10 5 pbyrg /home/jplank/cs302/Labs/Lab5/sb-play n n 1 10 5 pbyrg /home/jplank/cs302/Labs/Lab5/sb-play2 n n 1 10 5 pbyrg /home/jplank/cs302/Labs/Lab5/sb-play3 n n 1 |
Project 03: Superball!
It can take a while for these to run if it appears to be hanging, send the process a QUIT signal and it will print out what the current score is.
Shell Script to Run Multiple Times
The file run_multiple.sh (http://www.cs.utk.eduijplankiplank/classes/cs302/Labs/Lab5/run_multiple.sh) is a shell script to run the player on multiple seeds and average the results. Examples:
UNIX> sh run_multiple.sh
usage: sh run_multiple.sh r c mss colors player nruns starting_seed
UNIX> sh run_multiple.sh 8 10 5 pbyrg sbplay 10 1
| Run | 1 | Score: | 38 | Average | 38.000 |
| Run | 2 | Score: | 0 | Average | 19.000 |
| Run | 3 | Score: | 0 | Average | 12.667 |
| Run | 4 | Score: | 57 | Average | 23.750 |
| Run | 5 | Score: | 0 | Average | 19.000 |
| Run | 6 | Score: | 0 | Average | 15.833 |
| Run | 7 | Score: | 89 | Average | 26.286 |
| Run | 8 | Score: | 15 | Average | 24.875 |
| Run | 9 | Score: | 0 | Average | 22.111 |
| Run | 10 | Score: | 20 | Average | 21.900 |
UNIX> sh run_multiple.sh 8 10 5 pbyrg sbplay2 10 1
| Run | 1 | Score: | 855 | Average | 855.000 |
| Run | 2 | Score: | 979 | Average | 917.000 |
| Run | 3 | Score: | 650 | Average | 828.000 |
| Run | 4 | Score: | 833 | Average | 829.250 |
| Run | 5 | Score: | 832 | Average | 829.800 |
| Run | 6 | Score: | 3326 | Average | 1245.833 |
| Run | 7 | Score: | 1507 | Average | 1283.143 |
| Run | 8 | Score: | 3643 | Average | 1578.125 |
| Run | 9 | Score: | 610 | Average | 1470.556 |
| Run | 10 | Score: | 862 | Average | 1409.700 |
UNIX> sh run_multiple.sh 8 10 5 pbyrg sbplay3 10 1
| Run | 1 | Score: | 2572 | Average | 2572.000 |
| Run | 2 | Score: | 2708 | Average | 2640.000 |
| Run | 3 | Score: | 745 | Average | 2008.333 |
| Run | 4 | Score: | 424 | Average | 1612.250 |
| Run | 5 | Score: | 1888 | Average | 1667.400 |
| Run | 6 | Score: | 7140 | Average | 2579.500 |
| Run | 7 | Score: | 3475 | Average | 2707.429 |
| Run | 8 | Score: | 1701 | Average | 2581.625 |
| Run | 9 | Score: | 2699 | Average | 2594.667 |
| Run | 10 | Score: | 2291 | Average | 2564.300 |
| UNIX> |
Obviously, to get a meaningful average, many more runs (than 10) will be required.
Project 03: Superball!
Oh, and make your programs run in reasonable time. Roughly 5 seconds for every thousand points, and if you are burning all that time, your program better be killing Dr. Planks.
The Superball Challenge
To get credit, your player needs to average over 100 points on runs of 100 games.
We will run a Superball tournament with all of your players with extra lab points going to the winners:
- 1st place: 20 extra lab points.
- 2nd place: 10 extra lab points.
- 3rd place: 5 extra lab points.
Dr. Plank and I have previously performed the challenge eight times:
- CS140 in 2007.
- CS302 in 2010.
- CS302 in 2011.
- CS302 in 2012.
- CS302 in 2013.
- CS302 in 2014.
- CS302 in 2015.
- CS302 in 2018.
- CS302 in 2019 (SJE)
Heres the Superball Challenge Hall Of Fame (scores over 650):
| Rank | Average | Name | Semester |
| 1 | 31814.13 | Grant Bruer | CS302, Fall, 2015 |
| 2 | 24278.49 | Alexander Teepe | CS302, Fall, 2015 |
| 3 | 17367.77 | Joseph Connor | CS302, Fall, 2014 |
| 4 | 17021.37 | Cory Walker | CS302, Fall, 2014 |
| 5 | 16963.40 | Seth Kitchens | CS302, Fall, 2015 |
| 6 | 14555.83 | Ben Arnold (Tie) | CS302, Fall, 2012 |
| 7 | 14555.83 | Adam Disney (Tie) | CS302, Fall, 2011 |
| 8 | 13657.79 | Isaak Sikkema | CS302, Fall, 2018 |
| 9 | 12963.47 | Jake Davis , | CS302, Fall, 2014 |
| 10 | 12634.29 | Jake Lamberson | CS302, Fall, 2014 |
| 11 | 11722.05 | Parker Mitchell | CS302, Fall, 2014 |
| 12 | 11418.77 | James Pickens | CS302, Fall, 2014 |
| 13 | 11380.74 | Nathan Ziebart | CS302, Fall, 2011 |
| 14 | 11291.39 | Michael Jugan | CS302, Fall, 2010 |
| 15 | 10576.96 | Tyler Shields | CS302, Fall, 2014 |
| 16 | 8770.67 | Nathan Swartz | S302, Spring, 2019 |
| 17 | 7475.07 | Jared Smith | CS302, Fall, 2014 |
| 18 | 7216.28 | _Michael Bowie | CS302, Fall, 2018 |
| 19 | 7003.56 | Andrew LaPrise | CS302, Fall, 2011 |
| 20 | 6100.28 | Chris Nagy | CS302, Fall, 2015 |
| 21 | 5467.56 | Tyler Marshall | CS302, Fall, 2013 |
| 22 | 5262.80 | Harry Channing | CS302, Fall, 2018 |
| 23 | 5116.13 | Kyle Bashour | CS302, Fall, 2014 |
| 24 | 4808.03 | Matt Baumgartner | CS302, Fall, 2010 |
| 25 | 4586.51 | Jeramy Harrison | CS302, Fall, 2013 |
| 26 | 4531.96 | Philip Hicks | CS302, Spring, 2019 |
| 27 | 4057.08 | Phillip McKnight | CS302, Fall, 2015 |
| 28 | 3882.53 | Pranshu Bansal | CS302, Fall, 2013 |
| 29 | 3882.28 | Kemal Fidan | CS302, Fall, 2018 |
| 30 | 3852.87 | Yaohung Tsai | CS302, Fall, 2015 |
| 31 | 3849.24 | Chris Richardson | CS302, Fall, 2010 |
| 32 | 3809.41 | Arthur Vidineyev | CS302, Fall, 2015 |
| 33 | 3588.35 | Kevin Dunn | CS302, Fall, 2014 |
| 34 | 3464.83 | Patrick Slavick | CS302, Fall, 2012 |
| 35 | 3436.21 | sb-play3 | CS140, Fall, 2007 |
| 36 | 3400.50 | Kody Bloodworth | CS302, Fall, 2018 |
| 37 | 3080.15 | Andrew Messing | CS302, Fall, 2013 |
| 38 | 2903.38 | Adam LaClair | CS302, Fall, 2013 |
| 39 | 2555.36 | Mohammad Fathi | CS302, Fall, 2014 |
| 40 | 2532.89 | Trevor Sharpe | CS302, Fall, 2015 |
| 41 | 2521.44 | Justus Camp | CS302, Fall, 2018 |
| 42 | 2335.88 | Mark Clark | CS302, Fall, 2012 |
| 43 | 2307.16 | John Burnum | CS302, Fall, 2012 |
| 44 | 2205.17 | Shawn Cox | CS302, Fall, 2011 |
| 45 | 2163.70 | Alex Wetherington | CS302, Fall, 2011 |
| 46 | 2134.99 | Julian Kohann | CS302, Fall, 2013 |
| 47 | 2011.38 | Wells Phillip | CS302, Fall, 2015 |
| 48 | 1919.72 | Ravi Patel | CS302, spring, 2019 |
| 49 | 1778.83 | Keith Clinart | CS302, Fall, 2011 |
| 50 | 1740.19 | Luke Bechtel | CS302, Fall, 2014 |
| 51 | 1634.49 | William Brummette | CS302, Fall, 2013 |
| 52 | 1602.83 | Forrest Sable | CS302, Fall, 2014 |
| 53 | 1470.84 | Christopher Tester | CS302, Fall, 2014 |
| 54 | 1433.48 | Xiao Zhou | CS302, Fall, 2015 |
| 55 | 1430.54 | Jonathan Burns | CS302, Fall, 2018 |
| 56 | 1340.32 | John Murray | CS302, Fall, 2012 |
| 57 | 1329.34 | Benjamin Brock | CS302, Fall, 2013 |
| 58 | 1257.56 | Dylan Lee | CS302, Fall, 2018 |
7/12/2020 Project 03: Superball!
| 59 | 1202.06 | _Bandara | CS302, Fall, 2014 |
| 60 | 1149.80 | Will Houston | CS302, Fall, 2010 |
| 61 | 1119.85 | Kevin Chiang | CS302, Fall, 2014 |
| 62 | 1096.48 | Daniel Cash | CS302, Fall, 2011 |
| 63 | 1059.91 | Kaleb McClure | CS302, Fall, 2013 |
| 64 | 1058.26 | sb-play2 | CS140, Fall, 2007 |
| 65 | 1029.63 | Lydia San George | CS302, Fall, 2018 |
| 66 | 972.36 | Erik Rutledge | CS302, Fall, 2013 |
| 67 | 959.79 | Daniel Nichols | CS302, Fall, 2018 |
| 68 | 917.92 | Vasu Kalaria | CS302, Fall, 2015 |
| 69 | 908.09 | Chris Rains | CS302, Fall, 2012 |
| 70 | 875.44 | Allen McBride | CS302, Fall, 2012 |
| 71 | 840.94 | Spencer Howell | CS302, Fall, 2018 |
| 72 | 830.79 | David Cunningham | CS302, Fall, 2014 |
| 73 | 810.17 | Collin Bell | CS302, Fall, 2012 |
| 74 | 763.58 | Jacob Lambert | CS302, Fall, 2013 |
| 75 | 703.67 | Scott Marcus | CS302, Fall, 2015 |
| 76 | 703.00 | Don Lopez | CS140, Fall, 2007 |
| 77 | 700.90 | Tony Abston | CS302, Fall, 2015 |
| 78 | 682.56 | Jackson Collier | CS302, Fall, 2014 |
| 79 | 677.83 | KC Bentjen | CS302, Fall, 2011 |
| 80 | 665.60 | Joshua Clark | CS302, Fall, 2012 |
| 81 | 659.96 | Warren Dewit | CS302, Fall, 2010 |
| 82 | 654.67 | Coburn Brandon | CS302, Fall, 2015 |
| 83 | 650.98 | Joaquin Bujalance | CS140, Fall, 2007 |
Hints
Play the game for a bit to try to figure out some strategies. However, one good way to write a game player is to figure out a way to come up with a rating for a game board. Then when you are faced with making a move, you analyze all potential moves by trying them out and choosing the one that gives you the resulting board with the highest rating.
Reviews
There are no reviews yet.