I'll suggest Ultimate Tic-Tac-Toe. (I believe this is what Sue mentioned in her comment, as well.)
The main ideas is to take a 3x3 tic-tac-toe board and replace each of the 9 squares with its own 3x3 board. When you make a move, you put an X or O in one of the 81 small squares. Whichever small square you play in, that tells your opponent which big square they must play in next. Check out the image for an example: I play the red X, which is in the top-right corner of that particular 3x3 board, so you must respond by playing somewhere in the top-right corner of the big board (the blue squiggly area).
That image comes from a post on the Math With Bad Drawings blog, and that post has a lot more information about the rules and strategy of the game: https://mathwithbaddrawings.com/2013/06/16/ultimate-tic-tac-toe/
An internet search for "ultimate tic tac toe" reveals several places to play the game online, including this one (which I like because you can play against an AI or share a link to play online against a friend): https://ultimate-t3.herokuapp.com/
It's pretty easy to play with pencil and paper, of course, too!
I think this fits what you're looking for because each move you make only has a few options (other than the very first move, you will always have at most 9 options, and you'll have fewer as the game goes on). It's also possible to look ahead a move or two (or more), and this can help your student develop some logical thinking skills along the lines of: "If I go here, you'll have to go there, which means..."
But most of all, this game is fun! I've used it as an ice-breaker / just-for-fun activity in classes before and it always goes over well.