I bet it loses when I get frustrated and uninstall its ass from Add/Remove programs! :O)
I thought some time ago it was solvable in a reasonable time — of course I was not ambitious enough to actually program it. There are less than 5^32 possible boards (red king, red pawn, black pawn, black king, blank square), red men <= 12, black men <= 12.
A really good checkers player disagreed with me though.
Chess will require heuristics for some time, I think...