To scale without bounds, if you control the client code (so you know people aren't cheating -- which at tic-tac-toe they'd be unlikely to:-), you could have the client open and offer a listening socket in order to connect -- when an odd client connects, just respond with a "please wait" message; when the even client connects to match it up, respond to both clients with the listening-socket info about each other, and get out of the way.
That won't work for clients who can't open, and listen on, a new socket (e.g., ones sequestered behind some NAT arrangement). In such a situation, you could switch the clients (for their follow-on interactions with one another) to UDP to/from your server -- UDP, not being connection oriented, can serve arbitrarily high numbers of clients (client pairs, in your case!) on a single socket (but then you're responsible, cooperatively on the client and server sides!, for checking/acknowledging packets and ensuring their good ordering, which TCP, being connection-oriented, handles on your behalf:-).
I'm not sure where exactly all of your constraints come from in the first place, or what other constraints (such as clients being unable to open, communicate, and listen to, new sockets...) might apply.
But one way or another, once you fully understand and tell us about all the applicable constraints, some solution can always be found (perhaps with new-fangled conniptions such as pub-sub, e.g https://cloud.google.com/pubsub/docs -- as fast as new constraints arise, or faster!, clever guys are always figuring out work-arounds...!-)