It could be done. Endgame positions (which will probably result in a win in three moves or less) can easily be analysed completely using basic game theory - I could probably write you a program that plays tic-tac-toe, or Nine Man's Morris. More complex positions are the real problem, but a lot of human-playable games have basic strategies like "try to keep as many of your pieces on the board as you can (Chess, drafts, Go, and so on)", "try to get your pieces to form rows (Connect-4, Nine Man's Morris)", or even "bet higher than you should to bluff your opponent (Poker and gambling games)". Perhaps it could learn from past mistakes too.
Not saying it would be easy to make, that it could beat a human at an arbitrary game, or even that it could beat a specialised AI designed for that particular task. But making AIs adaptable makes them much more human-like, if that is what you want.
PS: Toss might actually be able to do this. The description isn't very clear; I'll check for you.
Earlier today I had an idea for a meta-game a group of people could play. It’d be ideal if you lived in an intentional community, or were at university with a games society, or somewhere with regular Less Wrong Meetups.
Each time you would find a new game. Each of you would then study the rules for half an hour and strategise, and then you’d play it, once. Afterwards, compare thoughts on strategies and meta-strategies. If you haven’t played Imperialism, try that. If you’ve never tried out Martin Gardner’s games, try them. If you’ve never played Phutball, give it a go.
It should help teach us to understand new situations quickly, look for workable exploits, accurately model other people, and compute Nash equilibrium. Obviously, be careful not to end up just spending your life playing games; the aim isn't to become good at playing games, it's to become good at learning to play games - hopefully including the great game of life.
However, it’s important that no-one in the group know the rules before hand, which makes finding the new games a little harder. On the plus side, it doesn’t matter that the games are well-balanced: if the world is mad, we should be looking for exploits in real life.
It could be really helpful if people who knew of good games to play gave suggestions. A name, possibly some formal specifications (number of players, average time of a game), and some way of accessing the rules. If you only have the rules in a text-file, rot13 them please, and likewise for any discussion of strategy.