I’m currently working on the 2009 version of The Blue Alliance codebase (some exciting stuff is going to happen!). One of the features I want to include is dynamic “Offensive Power Ranking” calculations.
I know that the linear algebra behind this is detailed on this Chief Delphi post, but I think I could roll this into The Blue Alliance faster if I could base my work off someone else’s. Can anyone point me at any implementations of this algorithm? Alternatively, is anyone willing to try to implement this algorithm in Python or PHP?
Bongle and others did some fantastic work throughout that thread.
I highlighted page 11 because the DPR topic comes up. One problem with the DPR (for last year’s game) was too much room for error. While OPR has some areas for error to influence the overall outcome, DPR was based off of OPR results and thus compounded some of the error.
Also last year was fairly unique with the extreme amount of penalties. Unless you had good data on how many G22s, and who did them, the matrix method might just as easily assume you were being defended well.
Now that was last year’s game. This year could be totally different.
From the latest commit to my scouting program (pages/strength.act.php):
/** Gaussian elimination solver with partial pivoting.
* Originally written in Java by Robert Sedgewick and Kevin Wayne:
* @see http://www.cs.princeton.edu/introcs/95linear/GaussianElimination.java.html
*
* Ported to PHP by Paul Meagher
* @see http://www.phpmath.com/home?op=perm&nid=82
*
* @modified June 12/2007 reimplemented as a GaussianElimination.php class
* @modified March 26/2007 implemented as a function gauss($A, $b)
* @version 0.3
*/
/** Implements gaussian elimination solver with partial pivoting.
*
* @param double]] $A coefficient matrix
* @param double] $b output vector
* @return double]$x solution vector
*/
function solve($A, $b) {
// number of rows
$N= count($b);
// forward elimination
for ($p=0; $p<$N; $p++) {
// find pivot row and swap
$max = $p;
for ($i = $p+1; $i < $N; $i++)
if (abs($A$i]$p]) > abs($A$max]$p]))
$max = $i;
$temp = $A$p]; $A$p] = $A$max]; $A$max] = $temp;
$temp = $b$p]; $b$p] = $b$max]; $b$max] = $temp;
// check if matrix is singular
if (abs($A$p]$p]) <= 1e-10) throw new Exception("Matrix is singular or nearly singular");
// pivot within A and b
for ($i = $p+1; $i < $N; $i++) {
$alpha = $A$i]$p] / $A$p]$p];
$b$i] -= $alpha * $b$p];
for ($j = $p; $j < $N; $j++)
$A$i]$j] -= $alpha * $A$p]$j];
}
}
// zero the solution vector
$x = array_fill(0, $N-1, 0);
// back substitution
for ($i = $N - 1; $i >= 0; $i--) {
$sum = 0.0;
for ($j = $i + 1; $j < $N; $j++)
$sum += $A$i]$j] * $x$j];
$x$i] = ($b$i] - $sum) / $A$i]$i];
}
return $x;
}
// Get score data from database
switch ($_REQUEST'method']){
case 'linear_points':
$sql = <<<SQL
SELECT teamnum, SUM(IF(points IS NULL,score,points)) AS p
FROM team_match m, alliance a
WHERE m.matchid=a.matchid AND m.alliance=a.alliance AND m.eventid=$eventid AND a.eventid=$eventid
GROUP BY teamnum
ORDER BY teamnum
SQL;
break;
case 'linear_score':
$sql = <<<SQL
SELECT teamnum, SUM(score) AS p
FROM team_match m, alliance a
WHERE m.matchid=a.matchid AND m.alliance=a.alliance AND m.eventid=$eventid AND a.eventid=$eventid
GROUP BY teamnum
ORDER BY teamnum
SQL;
break;
case 'linear_difference':
$sql = <<<SQL
SELECT teamnum, SUM(CAST(IF(points IS NULL,score,points) AS SIGNED)*IF(m.alliance=a.alliance,1,-1)) AS p
FROM team_match m, alliance a
WHERE m.matchid=a.matchid AND m.eventid=$eventid AND a.eventid=$eventid
GROUP BY teamnum
ORDER BY teamnum
SQL;
break;
case 'linear_penalty':
$sql = <<<SQL
SELECT teamnum, SUM(IF(penalty IS NULL,0,penalty)) AS p
FROM team_match m, alliance a
WHERE m.matchid=a.matchid AND m.eventid=$eventid AND a.eventid=$eventid
GROUP BY teamnum
ORDER BY teamnum
SQL;
break;
}
$i = 0;
$matrix = $score = $team = $rows = array();
// Put scores into an array and index team numbers
foreach($db->Execute($sql) as $row){
$team$i] = $row'teamnum'];
$score$i] = $row'p'];
$i++;
}
$sql = <<<SQL
SELECT a.teamnum AS a, b.teamnum AS b, COUNT(a.matchid) AS count
FROM team_match a, team_match b
WHERE a.eventid=6 AND b.eventid=6 AND a.matchid=b.matchid AND a.alliance=b.alliance
GROUP BY a.teamnum, b.teamnum
ORDER BY a.teamnum, b.teamnum
SQL;
// Organize returned database data
foreach($db->Execute($sql) as $row){
$rows$row'a']]$row'b']] = $row'count'];
}
// Build n-by-n matrix of teams
foreach($team as $i=>$row){
foreach($team as $j=>$cell) $matrix$i]$j] = $rows$row]$cell];
}
// Solve for solution matrix and convert that to SQL
$rows = array();
foreach(solve($matrix, $score) as $i=>$strength) $rows] = '('.$team$i].','.round($strength,1).')';
// Put the data back into the database
$db->Execute("CREATE TEMPORARY TABLE tmp_team_strength (`teamnum` int(10) unsigned NOT NULL, `strength` float NOT NULL, PRIMARY KEY (`teamnum`))");
$db->Execute("INSERT INTO tmp_team_strength VALUES ".implode(',',$rows));
$db->Execute("UPDATE team_event d, tmp_team_strength s SET d.strength=s.strength WHERE d.eventid=$eventid AND d.teamnum=s.teamnum");
$db->Execute("DROP TEMPORARY TABLE tmp_team_strength");
The solve function I found after I tried programming my own. It runs surprisingly quick for a 50x50 matrix operation compared to the function I wrote (no more then a tenth of a second I think, I didn’t do any tests), and far better then the SQL-only script this code replaced (which was basically a really fancy average). All of my work here I declare public domain, the solve function I assume is posted for general use too. And of course, the SQL and functions that call it (I use ADODB here) may require changing.