Re: Offensive Power Ranking Calculations
From the latest commit to my scouting program (pages/strength.act.php):
PHP Code:
/** 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.
|