I don't think there's much you can do about that, but is it really a problem? The majority of online multiplayer games don't rely on connecting with random people, they're usually played by people who know each other beforehand. They'll coordinate themselves.

I don't know your game, but you should probably have a single player mode if it is a game that can be fun to play alone. Also consider adding a tutorial mode to teach the player how the game works.

I think you need both friend discovery and random matchups - and having both of those, you probably don't need AI.

Friend discovery (via facebook, twitter, gamecenter, etc) because if the game is good I'll want to play with people I know. And random matchups because when I first download this game from the app store, I most likely don't know any other people who own it, and I need to be able to see if it is fun before I nag my friends to install it...

Can you give me an example of what your definition of friend discovery? I mean how should this work? Just a button to post on your wall?

I think it comes down to a few features:

- I need to be able to see a list of all my facebook/twitter/etc. friends who already have the game installed.

- I need to be able to send invites to specific friends who do not have the game installed, via private message, email or suchlike.

- I need to be able to 'brag', i.e. post highscores/victories/challenges to my facebook wall or twitter feed.

Depending on the specifics of your game, you can also provide more incentives in-game. A great example is Crossy Road: they display your friends highscores directly on the playing field, so that you can see when you are about to beat one of them, and they automatically take a screenshot if you die spectacularly, to encourage you to share with your friends. Obviously, these specific features don't translate well to a board game, but it's worth keeping the general concept in mind...