I suggest you represent your game as a tree. This obviously mandates that you know basic graph theory. Google: BFS, DFS, graph theory - until you get the basic concepts such as node, leaf, children, parents, siblings, etc.
The initial game setting is the root node, its branches are the moves you can make, the other inner nodes are distinct game states that you get to by taking those moves, and leaf nodes are end states that can be
Visualization of the game state tree:
Where #1 is the empty board, and #2 #7 #8 are the game states you get to from possible moves for the first player. Of course, the tree for Connect Four would look different.
Making a move simply means visiting a node, i.e. going by one of the branches. Please note that a single node presents the entire game state - i.e. it is a collection of all the game pieces and the entire board (obviously this can get memory-heavy, but there are optimizations).
You also have to use some stochastic and heuristic methods because the number of nodes will grow exponentially in size - you simply wont be able to traverse all of them and know which one to choose - statistics is your only weapon.
The Monte Carlo method seems to be suitable here.
When deciding which branch to take, you obviously have to pick the one with the highest probability of winning. So you have to calculate that probability for each of the possible branches (moves).
You do this by moving to them, and then picking random paths to go down. You continue down the paths until you reach a final state. Say you sample 10 000 final states. Then the probability of winning for that branch is
winning states / (losing states + draw states).
The paths have to be random. You do this by picking a random sample of children of a node and only visiting them. At one point down the tree you will have to take only a single random child of a node because picking even a small percentage is still exponential.
There are also options of dividing the result by the depth of the search since deeper searches are less relevant.
Please note that you have to take into account what the other player would do: some of his moves are more likely to be taken than others, see MiniMax.