There's a wonderful story in the March 2008 National Geographic called "Animal Minds". Turns out even critters that aren't primates can plan, count, lie, cheat, steal, make tools, and perform simple household repairs. Which, except for the lie-cheat-steal thing, is more than most people can do. The star, for me, is Betsy the Border Collie (that's her pretty face at the top of the story). She has a vocabulary of 340 words and, when show a picture of a frisbee, can go get the frisbee from the next room. If you don't find this impressive, try getting a toddler to pick up a toy.
A quote from the story illustrates that Darwin called this game early and he called it right:
Charles Darwin, who attempted to explain how human intelligence developed, extended his theory of evolution to the human brain: Like the rest of our physiology, intelligence must have evolved from simpler organisms, since all animals face the same general challenges of life.
Too bad Gus can't play at this level.