I love board games (own a little over 150) and enjoy them a lot more than video games. You can extract pretty good optimization problems form many of them (especially Eurogames).

In fact I own quite a few games that I haven't really played a lot but spent quite some time thinking about AIs for those games...dunno it's a strange but fun hobby :D

Cooperative games are probably the most popular ones in my collection. Incidentally they make for excellent solo puzzles as well.