View Single Post
  #5   Spotlight this post!  
Unread 18-03-2009, 22:03
Nibbles Nibbles is offline
Interstellar Hitchhiker
AKA: Austin Wright
FRC #0498 (Cobra Commanders)
Team Role: Alumni
 
Join Date: Jan 2008
Rookie Year: 2003
Location: Arizona
Posts: 103
Nibbles is just really niceNibbles is just really niceNibbles is just really niceNibbles is just really niceNibbles is just really nice
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
    
$Ncount($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-10);
    
    
// 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.
__________________
Help standardize match data! Use the XML interchange format. (Specification page)
AAA_awright on Freenode IRC chat. (Join us at ##FRC on chat.freenode.net, or in your browser)
Reply With Quote