Computer Science II
Contact Information
Course Overview
Prerequisites
Schedule
Lab Times
Office Hours
Calendar
Lecture notes
Lab materials
Homework
Test reviews
Textbooks
Web Resources
Drop in Tutoring
Homework
Due Date and Time
Late Day Policy
Compilers
Electronic Submission
C++ Development
Cygwin
Emacs
Dev C++
MinGW
HW9 City Chase Contest
EVADERS
- anthom: go to the first neighbor without a pursuer
- archid: goes to the place that none of the pursuers can go to (that has the most links)
- cutleb: explores up to 4 links away, chooses spot that is furthest from closest pursuer
- kongv: choose randomly, rechoose if there is an pursuer there
- nobled: assumes pursuer is random, computes probability of avoiding caputre
- okalyk: move randomly, excluding cities that pursuers are in
- rydzam: looks for places with fewest common neighbors to pursuers
- sarris: always pick the first option
- sayavn: ranking based on # of exits & # of nearby pursuers
- schwaj3: calls the pursuer's function (avoids infinite loop) lots of paths are good
- todacs: moves if tas are close
- vassin: looks for cities with fewest pursuers, but most connections (for escape)
- never: never moves
- random: moves randomly
- longest: goes to the place it hasn't been recently
PURSUERS
- anthom: if share a neighbor with the evader's city, go there
- chingj: looks 2 links away for evader
- cutleb: explores 4 links away, also avoids sticking with other pursuers
- kongv: always move, if evader is in a neighbor, go there
- schwaj3: calls the evader's function, calls repeatedly to check for randomness, looks for places with fewer paths
- todacs: pursuers try to split up
- vassin: looks for neighbors with the evader, and cities with most connections
- never: never moves
- random: moves randomly
- longest: goes to the place it hasn't been recently
GRAPHS
- cutleb: graph with loop
- sayavn: middleearth map, big
- schwaj3: cube, a good evader should never lose
- vassin: lots of links, 5 pursuers
In each test graph below, each pair of evader & pursuer was run for 100 trials of 100 tick movements. The number recorded is the average number of ticks until the evader was captured. 100.0 means the evader was never caught.
The winning pursuer is the column with the lowest average and the winning evader is the row with the highest average (highlighted in red).
two.txt: 2 cities, 1 link, 1 pursuer, 1 evader
PURSUERS
EVADERS| anthom chingj cutleb kongv schwaj3 todacs vassin never random longest
anthom| 1.0 2.0 1.8 1.0 1.0 2.1 1.0 100.0 2.1 1.0 11.3
archid| 2.0 2.0 1.8 2.1 1.8 1.9 2.2 1.9 1.9 1.9 2.0
cutleb| 2.2 2.0 1.8 1.8 1.9 1.9 2.1 2.5 2.0 2.0 2.0
kongv| 1.9 1.8 2.0 2.1 2.0 1.9 2.0 2.0 2.4 2.0 2.0
nobled| 1.0 1.9 2.0 1.0 1.0 1.9 1.0 100.0 1.9 1.0 11.3
okalyk| 2.2 1.8 1.9 2.0 1.8 2.2 2.0 2.1 2.0 2.0 2.0
rydzam| 100.0 2.0 2.0 100.0 1.0 2.2 100.0 1.0 2.0 100.0 41.0
sarris| 100.0 2.3 1.9 100.0 1.0 2.0 100.0 1.0 1.9 100.0 41.0
sayavn| 1.0 2.1 2.1 1.0 1.0 2.0 1.0 100.0 2.1 1.0 11.3
schwaj3| 100.0 2.0 1.9 100.0 1.9 2.1 100.0 100.0 2.2 100.0 51.0
todacs| 2.0 1.9 2.0 2.3 2.1 2.2 2.0 2.1 2.1 1.8 2.1
vassin| 1.0 2.0 2.0 1.0 1.0 2.0 1.0 100.0 1.9 1.0 11.3
never| 1.0 1.9 1.6 1.0 1.0 1.8 1.0 100.0 1.9 1.0 11.2
random| 2.0 2.0 1.7 2.0 2.3 2.0 1.9 1.7 2.0 2.1 2.0
longest| 100.0 1.9 2.0 100.0 1.0 1.9 100.0 1.0 2.2 100.0 41.0
27.8 2.0 1.9 27.8 1.5 2.0 27.8 41.0 2.1 27.8
line.txt: 5 cities, 4 links, 1 pursuer, 1 evader
PURSUERS
EVADERS| anthom chingj cutleb kongv schwaj3 todacs vassin never random longest
anthom| 3.0 17.9 19.1 8.2 100.0 20.4 3.0 100.0 16.2 3.0 29.1
archid| 20.7 25.3 26.3 10.9 17.4 24.4 6.0 100.0 22.8 5.4 25.9
cutleb| 60.6 31.7 28.2 12.7 100.0 29.1 100.0 100.0 31.8 7.4 50.2
kongv| 4.6 10.1 10.0 5.8 8.8 10.3 4.4 26.4 10.2 4.6 9.5
nobled| 4.0 28.7 24.8 11.5 100.0 27.8 100.0 100.0 28.1 4.0 42.9
okalyk| 4.3 13.1 12.4 5.5 8.8 11.4 4.3 100.0 13.2 3.8 17.7
rydzam| 100.0 26.2 21.3 100.0 100.0 22.5 100.0 100.0 22.8 100.0 69.3
sarris| 3.0 20.8 17.0 8.7 100.0 17.8 3.0 100.0 17.0 3.0 29.0
sayavn| 3.0 19.3 18.9 8.6 100.0 17.1 3.0 100.0 19.6 3.0 29.3
schwaj3| 100.0 34.2 31.7 100.0 100.0 33.7 100.0 100.0 33.0 100.0 73.3
todacs| 49.1 21.4 21.5 61.8 100.0 21.8 100.0 100.0 22.0 53.9 55.1
vassin| 4.0 22.9 25.7 9.7 100.0 24.4 100.0 100.0 24.5 4.0 41.5
never| 4.0 26.2 26.4 10.0 100.0 27.6 100.0 100.0 26.2 4.0 42.4
random| 4.2 10.2 10.1 5.6 11.6 8.7 4.7 26.0 11.7 4.7 9.8
longest| 2.0 4.2 5.9 2.5 3.0 4.3 2.0 4.0 4.8 2.0 3.5
24.4 20.8 20.0 24.1 70.0 20.1 48.7 83.8 20.3 20.2
circle.txt: 6 cities, 6 links, 1 pursuer, 1 evader
PURSUERS
EVADERS| anthom chingj cutleb kongv schwaj3 todacs vassin never random longest
anthom| 100.0 16.8 18.3 100.0 100.0 16.7 3.0 100.0 16.9 100.0 57.2
archid| 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
cutleb| 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
kongv| 6.7 10.1 8.5 5.8 4.8 9.3 4.8 14.6 9.1 5.8 8.0
nobled| 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
okalyk| 5.4 13.0 10.7 4.6 4.0 12.2 4.0 100.0 10.3 3.7 16.8
rydzam| 100.0 14.8 17.7 100.0 3.0 15.5 100.0 100.0 17.2 100.0 56.8
sarris| 100.0 13.1 13.0 100.0 3.0 12.2 3.0 100.0 11.4 100.0 45.6
sayavn| 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
schwaj3| 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
todacs| 100.0 20.4 17.3 100.0 5.4 20.1 100.0 100.0 19.4 100.0 58.3
vassin| 100.0 16.3 18.4 100.0 3.0 17.1 100.0 100.0 15.3 100.0 57.0
never| 3.0 13.9 13.1 4.8 3.4 11.4 100.0 100.0 13.3 3.0 26.6
random| 6.5 9.0 9.5 5.8 4.6 9.3 4.7 13.3 9.6 5.9 7.8
longest| 100.0 6.0 6.3 100.0 2.0 6.4 2.0 3.0 6.7 100.0 33.2
74.8 42.2 42.2 74.7 42.2 42.0 61.4 82.1 41.9 74.6
schwaj3_my_game.txt: 6 cities, 12 links, 1 pursuer, 1 evader
PURSUERS
EVADERS| anthom chingj cutleb kongv schwaj3 todacs vassin never random longest
anthom| 1.0 6.8 6.0 67.5 1.0 5.9 1.0 100.0 6.1 1.0 19.6
archid| 72.4 29.2 22.9 80.2 75.3 20.9 80.3 100.0 27.9 78.3 58.7
cutleb| 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
kongv| 5.1 5.5 5.5 4.9 5.6 5.5 4.6 6.4 6.7 6.0 5.6
nobled| 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
okalyk| 4.8 6.9 6.1 5.3 4.8 6.4 4.5 100.0 6.2 5.2 15.0
rydzam| 100.0 8.8 10.2 42.2 2.3 8.3 100.0 100.0 9.6 100.0 48.1
sarris| 1.0 6.2 6.3 72.4 1.0 6.1 1.0 2.0 7.0 1.0 10.4
sayavn| 1.0 20.6 16.3 68.4 1.0 17.2 1.0 100.0 15.6 1.0 24.2
schwaj3| 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0 100.0
todacs| 4.0 10.0 9.1 100.0 9.1 8.8 3.0 100.0 9.1 3.0 25.6
vassin| 3.0 8.2 8.1 100.0 2.3 9.7 100.0 100.0 9.2 6.0 34.7
never| 100.0 7.4 7.7 2.0 2.0 7.8 2.0 100.0 7.8 2.0 23.9
random| 5.2 7.1 6.7 5.8 5.0 6.3 4.3 7.9 5.2 5.6 5.9
longest| 1.0 5.6 6.4 66.4 1.0 6.5 1.0 2.0 6.2 1.0 9.7
39.9 28.2 27.4 61.0 27.4 27.3 40.2 74.6 27.8 34.0
schwaj3_my_game2.txt: 5 cities, 8 links, 1 pursuer, 1 evader
PURSUERS
EVADERS| anthom chingj cutleb kongv schwaj3 todacs vassin never random longest
anthom| 1.0 5.2 4.8 71.3 1.0 4.8 1.0 100.0 4.5 1.0 19.5
archid| 5.4 10.0 10.0 48.1 48.9 8.3 6.0 100.0 9.4 11.4 25.8
cutleb| 11.4 18.9 24.8 92.2 100.0 20.6 9.0 100.0 19.7 16.5 41.3
kongv| 4.4 5.3 5.9 3.9 3.5 4.9 3.9 6.8 6.0 4.4 4.9
nobled| 100.0 19.1 19.7 66.7 100.0 20.3 2.0 100.0 21.7 2.0 45.1
okalyk| 3.6 3.9 5.6 3.1 3.7 6.5 3.3 100.0 5.5 3.8 13.9
rydzam| 100.0 7.2 6.7 38.3 2.0 7.3 100.0 100.0 6.1 4.0 37.2
sarris| 1.0 4.5 4.4 72.3 1.0 4.7 1.0 2.0 3.7 1.0 9.6
sayavn| 1.0 9.8 8.9 67.3 1.0 7.6 1.0 100.0 10.5 1.0 20.8
schwaj3| 100.0 27.2 21.7 100.0 8.9 24.8 100.0 100.0 19.2 100.0 60.2
todacs| 4.0 6.8 8.9 100.0 5.2 7.1 3.0 100.0 7.9 4.0 24.7
vassin| 3.0 6.5 6.6 3.4 2.0 7.1 2.0 100.0 7.4 2.0 14.0
never| 100.0 5.8 7.4 2.0 2.0 7.2 2.0 100.0 6.7 2.0 23.5
random| 3.7 5.5 5.4 4.2 3.7 4.5 3.7 6.1 5.7 4.2 4.7
longest| 1.0 4.6 4.3 64.4 1.0 4.3 1.0 2.0 4.9 1.0 8.8
29.3 9.4 9.7 49.1 18.9 9.3 15.9 74.5 9.3 10.6
cutleb_northeast.txt: 9 cities, 11 links, 2 pursuers, 1 evader
PURSUERS
EVADERS| anthom chingj cutleb kongv schwaj3 todacs vassin never random longest
anthom| 2.0 7.1 7.1 100.0 2.0 6.2 6.0 100.0 6.9 100.0 33.7
archid| 14.3 22.4 19.3 100.0 70.2 18.6 100.0 100.0 20.9 38.0 50.4
cutleb| 49.1 28.0 29.2 16.1 73.9 30.0 13.7 100.0 24.3 17.4 38.2
kongv| 3.3 5.1 4.0 3.9 2.5 4.7 3.5 5.1 4.3 3.4 4.0
nobled| 100.0 28.9 25.0 6.0 75.8 27.0 100.0 100.0 22.7 12.0 49.7
okalyk| 4.5 6.1 7.0 2.2 1.9 5.9 2.6 100.0 6.5 4.1 14.1
rydzam| 1.0 3.9 4.0 100.0 1.0 3.5 4.0 1.0 3.6 1.0 12.3
sarris| 1.0 4.7 3.5 100.0 1.0 3.3 100.0 1.0 3.9 1.0 21.9
sayavn| 7.0 23.7 21.0 100.0 71.6 17.9 100.0 100.0 22.6 20.0 48.4
schwaj3| 100.0 39.6 35.7 100.0 72.7 34.0 100.0 100.0 37.2 100.0 71.9
todacs| N/A* 7.2* 3.4* 6.7* 48.7 2.9* 5.5* N/A* 5.3* N/A* 11.4
vassin| 1.0 2.2 3.0 100.0 1.0 2.9 100.0 1.0 3.1 2.0 21.6
never| 100.0 3.0 2.7 1.0 1.0 2.6 1.0 100.0 3.2 1.0 21.5
random| 3.2 4.1 3.7 3.8 2.5 5.2 3.6 4.1 4.0 3.3 3.8
longest| 1.0 3.3 3.8 100.0 1.0 3.2 2.0 1.0 3.2 1.0 12.0
27.7 12.6 11.5 56.0 28.4 11.2 42.8 58.1 11.5 21.7
* = error in one or more test runs
vassin_mynetwork.txt: 13 cities, 23 links, 5 pursuers, 1 evader
PURSUERS
EVADERS| anthom chingj cutleb kongv schwaj3 todacs vassin never random longest
anthom| 1.0 4.0 3.9 18.7 1.0 3.9 1.0 100.0 3.5 1.0 13.8
archid| 8.6 5.7 5.3 42.5 100.0 6.7 3.7 100.0 6.4 3.5 28.2
cutleb| 13.0 6.4 6.4 7.1 100.0 6.3 2.8 100.0 6.4 3.5 25.2
kongv| 2.7 2.9 3.1 2.9 1.7 3.5 1.8 6.4 3.3 2.4 3.1
nobled| 100.0 10.7 10.6 29.3 100.0 9.7 2.0 100.0 9.0 2.0 37.3
okalyk| 2.5 2.8 3.2 2.3 1.7 3.5 1.8 100.0 3.5 1.7 12.3
rydzam| 1.0 3.7 4.1 25.8 1.0 3.2 1.0 100.0 3.6 1.0 14.4
sarris| 1.0 4.0 3.9 33.5 1.0 3.5 1.0 100.0 3.7 1.0 15.3
sayavn| 3.0 6.9 6.8 62.2 100.0 7.4 3.0 100.0 7.8 3.0 30.0
schwaj3| 100.0 11.4 8.0 90.5 5.0 9.7 100.0 100.0 10.2 100.0 53.5
todacs| 1.0 1.5* 1.7* 2.3* 1.2* 1.7* 2.3 1.0 1.8* 4.3* 1.9
vassin| 1.0 2.3 2.5 2.3 1.0 2.5 1.0 100.0 2.5 1.0 11.6
never| 100.0 1.8 1.6 1.0 1.0 1.6 1.0 100.0 1.6 1.0 21.1
random| 2.7 3.0 3.1 2.4 2.0 2.9 2.0 5.9 2.8 2.7 3.0
longest| 1.0 3.6 3.2 14.9 1.0 3.2 1.0 7.0 3.3 1.0 3.9
22.6 4.7 4.5 22.5 27.8 4.6 8.4 74.7 4.6 8.6
* = error in one or more test runs
sayavn_ne.txt: 12 cities, 16 links, 1 pursuer, 1 evader
PURSUERS
EVADERS| anthom chingj cutleb kongv schwaj3 todacs vassin never random longest
anthom| 3.0 27.0 32.4 5.0 100.0 29.9 2.0 100.0 28.4 9.0 33.7
archid| 15.7 64.3 68.2 100.0 100.0 61.4 100.0 100.0 63.9 51.5 72.5
cutleb| 24.2 61.0 61.5 11.8 100.0 54.2 9.2 100.0 61.8 21.0 50.5
kongv| 4.6 15.6 16.4 4.0 4.6 13.6 4.0 17.6 14.3 11.3 10.6
nobled| 100.0 35.4 36.7 3.0 100.0 34.6 100.0 100.0 38.0 20.0 56.8
okalyk| 5.2 18.0 14.8 3.3 3.5 14.4 3.0 100.0 18.0 10.5 19.1
rydzam| 100.0 25.6 26.8 2.0 100.0 22.3 4.0 100.0 24.6 6.0 41.1
sarris| 3.0 24.7 25.4 100.0 100.0 24.5 2.0 100.0 22.8 19.0 42.1
sayavn| 4.0 66.8 69.3 100.0 100.0 64.5 100.0 100.0 67.7 14.0 68.6
schwaj3| 100.0 80.2 81.2 100.0 81.7 82.3 100.0 100.0 81.0 100.0 90.6
todacs| N/A* N/A* N/A* N/A* 100.0 N/A* N/A* 100.0 N/A* N/A* 100.0
vassin| 100.0 34.5 36.4 100.0 100.0 30.5 100.0 100.0 36.3 100.0 73.8
never| 100.0 8.1 9.0 1.0 1.0 9.7 1.0 100.0 9.3 5.0 24.4
random| 4.7 13.4 12.2 4.9 4.4 14.7 4.3 24.0 15.9 11.2 11.0
longest| 5.0 14.8 15.4 100.0 9.0 14.4 2.0 11.0 15.2 12.0 19.9
40.7 35.0 36.1 45.4 66.9 33.6 38.0 83.5 35.5 27.9
* = error in one or more test runs
sayavn_middleearth.txt: 33 cities, 59 links, 9 pursuers, 1 evader
PURSUERS
EVADERS| anthom chingj cutleb kongv schwaj3 todacs vassin never random longest
anthom| 6.0 18.2 18.7 56.8 100.0 20.0 3.0 100.0 17.1 10.0 35.0
archid| 100.0 58.8 60.3 21.5 100.0 60.7 15.8 100.0 54.7 60.4 63.2
cutleb| 100.0 73.7 67.8 56.0 100.0 70.5 100.0 100.0 73.2 54.7 79.6
kongv| 38.2 26.1 26.0 17.5 31.4 25.3 7.2 63.9 24.9 20.9 28.1
nobled| 100.0 76.1 74.2 30.5 100.0 68.0 6.0 100.0 73.2 57.0 68.5
okalyk| 36.1 31.2 28.5 17.4 26.9 28.1 6.7 100.0 30.7 22.7 32.8
rydzam| 6.0 20.8 18.8 91.3 100.0 20.2 100.0 100.0 16.9 11.0 48.5
sarris| 6.0 20.0 22.7 90.3 100.0 18.3 100.0 100.0 22.1 11.0 49.0
sayavn| 8.0 65.9 61.5 12.0 N/A* 60.4 4.0 100.0* 68.2* 100.0* 52.7
schwaj3| 100.0 76.0 72.4 100.0 100.0 74.0 100.0 100.0 76.0 100.0 89.8
todacs| 100.0 100.0* 84.5* 35.0* 100.0 100.0* 5.0* 100.0 89.7* N/A* 79.4
vassin| 100.0 19.8 18.0 29.8 100.0 19.5 2.0 100.0 19.8 10.0 41.9
never| 100.0 43.7 39.3 27.8 100.0 45.0 4.0 100.0 42.2 13.0 51.5
random| 35.2 26.9 28.0 17.2 29.8 26.8 8.0 68.8 27.9 19.8 28.8
longest| 13.0 10.0 10.1 16.9 8.0 9.7 13.0 15.0 9.8 9.0 11.4
56.6 44.5 42.0 41.3 78.3 43.1 31.6 89.8 42.7 35.7
* = error in one or more test runs
The Winners
best evader: schwaj3best pursuer: chingj
best map: sayavn
honorable mentions: nobled & vassin