Custom Search

Friday, January 13, 2012

An analysis of FBS controversies: Part I, the code

America's college Football Bowl Subdivision (FBS) has a history of controversy when it comes to picking a champion. And a history of proposed solutions. I've decided to examine how well those solutions would have worked if applied to previous seasons.

The football background

If you're a football fan, you can skip this section.

The FBS has one unusual property. Unlike every other organized college sport in the US, and every other nationally organized sport anywhere in the world, it has no clear cut way to pick a champion for each season. Instead, various groups - some as small as a single person - analyze the games played during the season and rank the teams according to that play, with the highest ranked team at the end of the season being crowned "champion". If the major groups agree with each other, there's a "consensus champion". If not, then you have a controversy.

People familiar with other sports might be amazed that there's ever a consensus. However, FBS teams play few enough games that winning every game in a season is possible, and it's not at all unusual for one or more teams to be undefeated in a season. It's also hard enough that it's not unusal if there are no undefeated teams at the end of a season.

So the most important criteria any ranking system considers is "number of losses and ties". (Football fans who decided to read this section are now saying "But what about non-AQ schools". For now, I'm going to ignore that, and I'll justify doing so in the sequel.) The other criteria are where the controvery comes in, as a case can be made that any two undefeated teams are equally good, and ditto for any two one-loss teams (provided they haven't played each other), etc.

The proposed solutions - short of an actual playoff, also to be discussed in the sequel - involve picking some small number of teams from the top to play each other. This system has actually been in use since the 1992 season to pick the top two teams. It doesn't seem to be any less controversial, and the formula for picking the two teams has been adjusted nearly continuously to try and deal with those controversies. A "plus-1" system gets a lot of talk, even though it has multiple definitions, but usually involves picking the top 4 teams.

The task

Since the FBS has a controversy any time either a clear winner fails to emerge, or - since the Bowl Coalition and it's succesors starting picking two teams for a championship game - if there's not a clear choice of two teams, the goal of the project is to see how often picking either 1, 2 or 4 teams (historical, current and "plus-1" approaches) who get a chance to play for the national championship would have done on previous seasons.

Deciding if there would have been controversy for a system is easy. If the last team to make the cutoff - either the first place team, the second place team or the fourth place team - has the same number of losses/ties as some team that doesn't get such a chance, the system with that cutoff has a conroversy for that season.

The code

Given that definition, the code is straightforward: for each season, get the records of all the teams, sort them based on losses/ties, and the check the records of the two teams on either side of each cutoff. This part presents the code for doing that.

So, let's start by getting the record for a season. Since that involves IO, the function that does it will work in the IO monad, giving us loadYear:


loadYear :: Int -> IO (Bool, Bool, Bool)
loadYear =
  liftM getYear . (>>= getResponseBody) . simpleHTTP . getRequest . makeURL
          
makeURL :: Show a => a -> String
makeURL year = "http://www.jhowell.net/cf/cf" ++ show year ++ ".htm"

makeURL is a helper function that just turns the integer year into a URL for the data on www.jhowell.net. That url is fed to a series of functions from the Network.HTTP module to produce a page

This idiom - a series of functions separated by '.' - is common in Haskell code. '.' is the compose operator, producing a new function that is the result of applying the right function and then the left function. This idiom and an alternative are going to show up in a number of places.

The interesting part is the first two steps, which actually happen last. The step before them - simpleHTTP takes a string value and produces a value in the IO monad. The form (>>= getResponseBody) is a function that will apply getResponseBody - which also work in the IO monad - to the value in the monad, returning the result from getResponseBody. liftM getYear is similar, except that getYear (presented below) does not work in the IO monad. liftM applies it to the value in the monad, and returns it's result in the monad. I can't use liftM on getResponseBody because getResponseBody, unlike getYear returns a value in the monad.

I've just talked a lot about monads. If you're not familiar with them, you're probably wondering what I'm talking about. A monad is a class - by which I mean a group of functions that can be applied to members of the class - that functional programming languages use to hide plumbing of various types. In this case, the IO monad hides the state information for whatever IO is being done from. One of the properties of a monad is that it can be viral. If a function uses a value in some monad, the function has to return a value in that monad unless the monad includes a function to unwrap the value. Without that, while the using function can extract the value from the monad to pass it to functions that aren't in the monad (know as pure functions) and get a value back, the value of the function has to be in the monad. After all, if a function does IO, then any function that calls it also does IO.

So makeURL and getRequest are pure functions, returning pure values. simpleHTTP takes that value and does IO, so it returns a value in the IO monad. The next two functions - (>>= getResponseBody) and liftM getYear have to accept and return values in the IO monad.

The next group of functions are easier, I promise. They're all pure. getYear takes the string representing the page for a season, and maps it to a set of three booleans, indicating whether or not that seasons results would be a controversy for a poll, a championship or a plus one system.


getYear :: String -> (Bool, Bool, Bool)
getYear = controversy . sort . (\ (t, r) -> map (getData t) r) . getRows . getTable . parseTags

And we once again see that list of function compositions. parseTags is from the Network.HTTP module, and turns the string into a list of Tag String elements. getTable extracts the table from that list:


getTable :: [Tag String] -> [[Tag String]]
getTable = partitions (isOpenTag "tr") . drop 2 
           . takeWhile (not . isCloseTag "table")
           . dropWhile (not . isOpenTag "table")

And again I have a list of function compositions. dropWhile skips over elements that it's first argument says to - in this case, any element that is not a "table" open tag, takeWhile accepts elements that it's first argument says to accept - in this case, any element that is not a "table" close tag. drop just returns the list without it's first two elements, which are the "table" open tag and the text between it and the start of the first row. Finally, partitions (also from the network.HTTP module) turns the list of Tags into a list of lists of Tags, starting a new list at every "tr" open tag.

isOpenTag and isCloseTag are very similar, using haskell's argument matching facility to check for TagOpen or TagClose elements in the list, and then comparing the text in the tag to their first argument to make sure this is the open or close for the proper element:


isOpenTag :: String -> Tag String -> Bool
isOpenTag tag (TagOpen t _) = map toLower t == tag
isOpenTag _ _ = False

isCloseTag :: String -> Tag String -> Bool
isCloseTag tag (TagClose t) = map toLower t == tag
isCloseTag _ _ = False

The table from getTable is then passed to getRows. getRows is more complicated, in that it has to check the first row to see if this year has a column for ties (the rules changed in the 90s, making ties impossible). It returns a Boolean indicating whether or not there was a tie along with list of rows after the first one.


getRows :: [[Tag String]] -> (Bool, [[Tag String]])
getRows rs = (isTies (head rs), tail rs)
  where isTies r = maybe False (const True) (find (== TagText "Ties") r)

isTies is a helper function only visible in the getRows namespace. It runs code in the Maybe monad, which can either hold a value or not (i.e - is Nothing). This monad has an extraction function maybe that can return values outside the monad. It's arguments are a value to return if there is no value in the monad (i.e. - it's Nothing), a function to apply to the value if there is one, and the value to be checked. In this case, I return False if there was no "Ties" column, and use a function that always returns True if there is a "Ties" column.

The piping the maybe monad is used to hide is error checking. You can pass a value in the monad through a string of functions that return a value in the monad, and once one returns a Nothing the rest will be skipped, passing the Nothing to the top level without having to explicitly code tests for it at each step. I'm not taking advantage of that here, but would have if I'd wanted to treat missing pages as seasons with no teams (as in 1871).

The next step in the processing is to extract the controversy information for each season. That's done by (\ (t, r) -> map (getData t) r), an anonymous function that accepts the tie Bool and then maps getData t over the rows. getData t uses Haskell's automatic currying to create a function that already has the ties Bool and will process a row:


getData :: Bool -> [Tag String] -> (Int, Int)
getData True = (\gs -> (head gs, head $ tail gs)) 
               . map getLosses . take 2 . dropToLosses
getData False = (,0) . getLosses . head . dropToLosses

The two variants of getData are almost identical. Both start with dropToLosses, which partitions the list on data elements, then apply getLosses either to the first element (if there are no ties) or the first two (if there may have been ties) and finally puts the results in a tuple, using a 0 for ties if they weren't possible.

To summarize the list tweakings: I started with a list of Tag's, turned that into a list of lists, each sub-list being a row. The processed each sub-list through getData, which once again turns it into a list of lists - this time of data elements in the row.

dropToLosses is simple:


dropToLosses :: [Tag String] -> [[Tag String]]
dropToLosses = drop 8 . partitions (isOpenTag "td")

It does the partitioning, then drops the first eight sub-lists, representing things in the table before the losses column.

getLosses is almost as simple:


getLosses :: [Tag String] -> Int
getLosses = read . fromTagText . head . tail

It drops the first element, the "td" tag, then extracts the fist element after that, which is the text in the "td" tag, then uses read to convert that from a string into an integer.

The last step in getData is to create a triple of Bools, saying whether the first and second teams had the same record, whether the second and third had the same record, and whether the fourth and fifth had the same record. Because list indices start at 0, I have to subtract one from each value in the comparison:


controversy :: [(Int, Int)] -> (Bool, Bool, Bool)
controversy records = (records !! 0 == records !! 1,
                       records !! 1 == records !! 2,
                       records !! 3 == records !! 4)

genStats generates the stats, but starts by calling loadYear, putting it in the IO monad. genStats uses loadYear on a list of years, then calculates and returns the percentage of times each type of controversy occurs in that list of years:


genStats :: [Int] -> IO (Int, Int, Int)
genStats years = do
  pages <- mapM loadYear years
  return $ percents (foldl' counts (0, 0, 0) pages) 
                    (fromIntegral $ length pages)
  where
    percents (a, b, c) l = (a % l, b % l, c % l)
    (%) a b = round $ 100 * a / b
    counts (a, b, c) (ab, bb, cb) = (minc a ab, minc b bb, minc c cb)
    minc x xb = x + if xb then 1 else 0

genStats gets the list of controversy triples via loadYear, then uses a quad of helper functions to calculate percentages. percents takes the triple of counts and the length of the list and uses % to generate the percentages. This is the one place where Haskell's type system gets in the way. It can't coerce the integer from length into a type that can be used with /, so it has to be explicitly coerced with fromIntegral. counts generates the actual counts, using minc to increment the current value of each count depending on whether or not there was a controversy for that count on this page.

I use makeYears to process the arguments. It takes a list of Strings, and returns a list of Ints. If the input list has only one element, it's value as an Int is wrapped in a list and returned. If it has two elements, they are taken from the list, turned into Ints, and the range from the first to the second is returned. Otherwise an error message is printed:


makeYears :: [String] -> [Int]
makeYears args =
  case length args of
    1 -> [read (head args)]
    2 -> (\l -> [head l .. head $ tail l]) $ map read args
    otherwise -> error "Arguments must be first and optional last year."

Finally, the main routine - which in Haskell as in other languages, is where compiled programs start - uses a chain of functions in the IO monad to get the results and print them. This time, the unusual function is makeYears, which isn't in the IO monad, but returns a value to genStats, which is.


main =
  getArgs >>= genStats . makeYears >>= uncurry3 (printf format)
  where
    format = "Percentage of seasons with controversies using\n" ++ 
             "Poll: %d%%, Game: %d%%, Plus 1: %d%%\n"

That's the code. You can, of course, fetch it from the repository if you want to build it and see the results yourself. I'll be discussing that in the next entry.

Dealing with the first three years

This code should work for all football seasons from 1872 forward. There was no football played in 1871. The first season was played in 1869. There were fewer than five teams playing in 1869 and 1870. Dealing with them would require deciding if no teams in the lower slots should be counted as year played without controversy, or not counted at all, and the code modified to match.

In 1869, there were two one-loss teams, so a poll had a controversy, and a championship game didn't. This table also requires special handling, as the pre-season ranking column is missing.

In 1870, there there three teams, one undefeated, and two with one loss. The code would have counted this as no controversy for a poll, and a controversy for a championship. However, Princeton beat Rutgers and Rutgers beat Columbia, so the rankings for 1, 2 and 3 aren't controversial.

In 1871, there was no college football. Worse yet, that page generates an error instead of an empty list, so handling it would require special handling.

Since it would have taken three changes to include just two more seasons - and problematic ones at that - these are ignored.