Monday, July 18, 2016

Gotta catch 'em all? Then think like a traveling salesman

When you absolutely, positively, have to catch every Pokémon in the area, it turns out there's a mathematical model for that.

To say that Pokémon Go, the mobile game based on the 20-year-old Nintendo franchise that has probably eaten more Game Boy batteries and caused more playground squabbles over collectible cards than any other game in history, has taken the world by storm this month is a Snorlax-sized understatement.

The game's user base quickly surpassed that of Candy Crush and Twitter within days, and added more than $7 billion to Nintendo's market value. (It's worth noting that Nintendo was notoriously mobile-game averse for many years. Let's just say that so far, this particular game has been super effective.) It's serious business - the CBC has already interviewed Games Institute researcher Betsy Brey about the phenomenon.

So what is it, exactly? Pokémon Go is a free-to-play mobile game that uses location-based GPS gameplay and augmented reality to put players right in the middle of the action in finding, capturing, and doing battle with the eponymous creatures made famous by a series of video games, card games, Saturday morning cartoons, and a subsequent avalanche of internet memes. Using their Android or IOS devices, players physically stalk the creatures and hurl virtual Poké Balls at them until they...look, you get the idea.

It was released in the United States on July 6 and officially released in Canada over the weekend, though a quick glance out the window last week would have revealed any number of students, faculty, and staff already engaged in the game on campus, gathering around so-called PokéStops, Pokémon gyms, and other points of interest that have been generated around a variety of real-world locations (hence the "reality" part of "augmented reality"). Players are engaging in real-world activity and videogame activity simultaneously, interacting with sprites that appear on their screen, overlaid on whatever object their camera is currently pointed at.

All jokes about gaming geeks getting tricked into exercise aside, the real world nature of the game and the fact that Pokémon types are scattered far and wide across physical spaces does present the aspiring Pokémon trainer with a problem - how does one make the best use of their phone's limited battery life when there are so many of the monsters to catch? 

People have been posting maps of PokéStops and gyms online to help game players plan their routes on their quest to, well, catch 'em all.

And that's where this mathematical model comes into play. It's called "The Traveling Salesman Problem" or TSP and it's been studied for more than 60 years.

So what's the problem? Imagine you are a traveling salesman, fedora on head and sample case or vacuum in hand. "Given a collection of cities and the cost of travel between each pair of them, the traveling salesman problem, or TSP for short, is to find the cheapest way of visiting all of the cities and returning to your starting point," says Waterloo's TSP website.

Professor Bill Cook of Combinatorics and Optimization has been working on the TSP for some time, authoring and co-authoring several books on the subject, and as game players make use of digital maps to find out where they need to go, he has created a Pokémon Go Tour site that includes TSP solutions for optimal routes.

"The best-known methods can be combined to make short work of finding the shortest possible route for the Pokemon hunter-gatherer," the website says. "If your Pokemon area has hundreds, or even thousands, of stops, mathematics can both find the best route and prove it is the shortest possible without going through all the candidate solutions, one by one by one."

Cook's efforts to apply the TSP to Pokémon routes has attracted the interest of Popular Mechanics.

In the meantime, Pokémon trainers should keep their heads up while crossing intersections, and as always, stay out of the tall grass unless they're properly equipped to do battle.

CTE Director is co-investigator on SSHRC-funded research project

This article was originally posted on the Centre for Teaching Excellence's website.

Staff members at the Centre for Teaching Excellence are pleased to share the news that the SSHRC has awarded funding to a research project for which their Director, Donna Ellis, is co-investigator.

The project, entitled “Teaching Culture Indicators: Enhancing Quality Teaching,” is a joint initiative involving individuals from eight Canadian Universities. The survey component of the project will be run at Waterloo this fall, and will include faculty, staff, and students.

This project builds upon a 2014 pilot study funded by a provincial Productivity and Innovation Fund grant.

Velocity Fund finals to take place Thursday

The University of Waterloo will host the Velocity Fund Finals this Thursday, where Waterloo students and alumni will pitch their innovative startups for the chance to win funding to grow their businesses, and entry into the Velocity Garage, the largest free startup incubator in the world.

Ten companies will compete for four prizes of $25,000. Judges will present one winner with an additional $10,000 for the top hardware pitch. Another 10 startups will compete for one of three awards of $5,000.

The judging panel for the $25K competition consists of:

• Chris Best, co-founder and CTO, Kik
• Dan Park, principal, Azure Capital Partners
• Devon Galloway; co-founder & CTO, Vidyard
• Janet Bannister; partner, Real Ventures

The judging panel for the $5K competition consists of:

• Heather Galt, VP talent initiatives and executive in residence, Communitech
• Mike Kirkup, CTO, Encircle
• Tricia Mumby, co-founder, Mabel's Labels

Both competitions take place in the Great Hall of the Student Life Centre. The $5K competition starts at 11:00 a.m., and the $25K competition starts at 1:00 p.m., with the event wrapping up at about 3 p.m.

Remembering Dawn Roussel

​Dawn Roussel, a staff member in the Early Childhood Education Centre in the Department of Psychology, died on Wednesday, July 13.

Roussel began her career at Waterloo in July 1984. She worked as a pre-school teacher for the Early Childhood Education Centre.

In 2007 Roussel was the recipient a national certificate of achievement in early childhood education as part of the Prime Minister's Awards for Teaching Excellence. She was cited for her ability to ease children and families into their first-school experience, her support of individual needs of children, and her mentoring skills with university, college and high-school students interning in the ECEC.

A memorial visitation will be held at the Erb & Good Family Funeral Home today from 2:00 p.m. to 4:00 p.m. and from 7:00 p.m. to 9:00 p.m. A celebration of her life will be held in the funeral home's chapel on Tuesday, July 19 at 11:00 a.m. A lunch will be served after the service, followed by interment at Parkview Cemetery.

Dawn is survived by her husband, Rod Smith (a Waterloo Environmental Studies alumnus) and her children Megan (who currently works in the University's Cognitive Development Lab), Erin (a staff member at the Registrar's Office), Alex (a current Waterloo anthropology student) and Brendan.