Go to Post Winning is an outcome, not the whole point. - StephLee [more]
Home
Go Back   Chief Delphi > FIRST > General Forum
CD-Media   CD-Spy  
portal register members calendar search Today's Posts Mark Forums Read FAQ rules

 
Reply
 
Thread Tools Rating: Thread Rating: 5 votes, 5.00 average. Display Modes
  #1   Spotlight this post!  
Unread 03-10-2008, 17:23
Unsung FIRST Hero
Greg Marra Greg Marra is offline
[automate(a) for a in tasks_to_do]
FRC #5507 (Robotic Eagles)
Team Role: Mentor
 
Join Date: Oct 2004
Rookie Year: 2005
Location: San Francisco, CA
Posts: 2,030
Greg Marra has a reputation beyond reputeGreg Marra has a reputation beyond reputeGreg Marra has a reputation beyond reputeGreg Marra has a reputation beyond reputeGreg Marra has a reputation beyond reputeGreg Marra has a reputation beyond reputeGreg Marra has a reputation beyond reputeGreg Marra has a reputation beyond reputeGreg Marra has a reputation beyond reputeGreg Marra has a reputation beyond reputeGreg Marra has a reputation beyond repute
Offensive Power Ranking Calculations

Hi everyone,

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?

Thanks!
Reply With Quote
  #2   Spotlight this post!  
Unread 03-10-2008, 17:34
The Lucas's Avatar
The Lucas The Lucas is offline
CaMOElot, it is a silly place
AKA: My First Name is really "The" (or Brian)
FRC #0365 (The Miracle Workerz); FRC#1495 (AGR); FRC#4342 (Demon)
Team Role: Mentor
 
Join Date: Mar 2002
Rookie Year: 2001
Location: Dela-Where?
Posts: 1,564
The Lucas has a reputation beyond reputeThe Lucas has a reputation beyond reputeThe Lucas has a reputation beyond reputeThe Lucas has a reputation beyond reputeThe Lucas has a reputation beyond reputeThe Lucas has a reputation beyond reputeThe Lucas has a reputation beyond reputeThe Lucas has a reputation beyond reputeThe Lucas has a reputation beyond reputeThe Lucas has a reputation beyond reputeThe Lucas has a reputation beyond repute
Send a message via AIM to The Lucas
Re: Offensive Power Ranking Calculations

Bongle posted his C++ implementation. I successfully ran it.
__________________
Electrical & Programming Mentor ---Team #365 "The Miracle Workerz"
Programming Mentor ---Team #4342 "Demon Robotics"
Founding Mentor --- Team #1495 Avon Grove High School
2007 CMP Chairman's Award - Thanks to all MOE members (and others) past and present who made it a reality.
Robot Inspector
"I don't think I'm ever more ''aware'' than I am right after I burn my thumb with a soldering iron"
Reply With Quote
  #3   Spotlight this post!  
Unread 03-10-2008, 20:01
=Martin=Taylor= =Martin=Taylor= is offline
run the trap!!!
FRC #0100 (The Wild Hat Society)
Team Role: Human Player
 
Join Date: Feb 2006
Rookie Year: 2005
Location: Bezerkeley, California
Posts: 1,255
=Martin=Taylor= has a reputation beyond repute=Martin=Taylor= has a reputation beyond repute=Martin=Taylor= has a reputation beyond repute=Martin=Taylor= has a reputation beyond repute=Martin=Taylor= has a reputation beyond repute=Martin=Taylor= has a reputation beyond repute=Martin=Taylor= has a reputation beyond repute=Martin=Taylor= has a reputation beyond repute=Martin=Taylor= has a reputation beyond repute=Martin=Taylor= has a reputation beyond repute=Martin=Taylor= has a reputation beyond repute
Re: Offensive Power Ranking Calculations

Would it be possible to create a Defensive Power Ranking system? Perhaps calculate which teams successively reduced the average score of other teams?

Second picks are harder than first picks…..
__________________
"Cooperation; because life is a team sport"
-Philip J. Fry
Reply With Quote
  #4   Spotlight this post!  
Unread 04-10-2008, 08:18
IKE's Avatar
IKE IKE is offline
Not so Custom User Title
AKA: Isaac Rife
no team (N/A)
Team Role: Mechanical
 
Join Date: Jan 2008
Rookie Year: 2003
Location: Michigan
Posts: 2,148
IKE has a reputation beyond reputeIKE has a reputation beyond reputeIKE has a reputation beyond reputeIKE has a reputation beyond reputeIKE has a reputation beyond reputeIKE has a reputation beyond reputeIKE has a reputation beyond reputeIKE has a reputation beyond reputeIKE has a reputation beyond reputeIKE has a reputation beyond reputeIKE has a reputation beyond repute
Re: Offensive Power Ranking Calculations

Here is a great thread to read through with regards to OPR.
http://www.chiefdelphi.com/forums/sh... +power+rating

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.
Reply With Quote
  #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
Reply


Thread Tools
Display Modes Rate This Thread
Rate This Thread:

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Offensive Power Rankings for 2008 Bongle General Forum 166 18-05-2008 15:05
Offensive+Defensive Power Rankings BornaE General Forum 4 05-04-2008 01:33
2006 Offensive Power Ratings sw293 General Forum 16 10-05-2006 17:04
best offensive play thatphotochick General Forum 6 04-04-2006 20:35
Best Offensive Round archiver 2000 10 23-06-2002 22:37


All times are GMT -5. The time now is 00:38.

The Chief Delphi Forums are sponsored by Innovation First International, Inc.


Powered by vBulletin® Version 3.6.4
Copyright ©2000 - 2017, Jelsoft Enterprises Ltd.
Copyright © Chief Delphi