Conceptually, the thing you are trying to learn is a graph where each board state is a unique node, valid moves are edges connecting them. Each game is a walk through the graph where players take turns picking an edge, trying to get to one of their win states. Your first order concern is to pick edges such that you maximize your odds of having a path to the win. The second order concern is to sabotage the opponents path to his win.
In reality the tree is huge, and running actual graph algos like breadth first search is unfeasible. You would likely need heuristics. Firstly symmetry can cut it down a few fold, but probably not by orders of magnitude (depending on the exact game rules). A very common strategy is to devise a way of "scoring" the board to figure out how strong is each player's position. This vastly simplifies the search, instead of trying to find a path you just try to go to the best adjacent node, and hope that if you keep doing that you'll automatically get to a win state. This is effectively a greedy strategy, and cannot so gambits by temporarily revealing weakness to trap the opponent. Also, it will only work as good as the scoring heuristic, which may or may not be hard to compose. You could try collecting statistics on past games as a naive way of finding states that seem like they tend to decide the outcome.
A simple extension of the above is to not go to the best adjacent node, but best node within X hops. In chess, I think 3-10 is common. Obviously this exponentially increases computational demands, but also looking further ahead can make traps, feints and gambits available.
You can further cull the tree by distinguishing moves that are simply legal, from moves that are "no brainer" moves. In many games, you may have the choice of dozens or hundreds of legal moves, but most are obviously bad ideas. It's usually not that hard to see that only a few moves are really worth considering, and it comes down to choosing among those. If you can add that to your algorithm (for instance by embedding it in the structure of your graph, eg. the color of edges) that should speed things up.
Ultimately it comes down to layers of heuristics to decide what moves strengthen or weaken your position. There's some obvious, general ones that I mentioned, but you're also only limited by your imagination and insight into the game. Ideally you should have a framework that can easily deal with an arbitrary number of heuristics for any given situation.