3
$\begingroup$

I implemented the Q-learning algorithm to play tic-tac-toe. The AI plays against the same algorithm, but they don't share the same Q matrix. After 200,000 games, I still beat the AI very easily and it's rather dumb. My selection is made by epsilon greedy policy.

What could cause the AI not to learn?

Edit

Here is how I do it (pseudo code):

for(int i = 0; i < 200000; ++i){
    //Game is restarted here
    ticTacToe.play();
}

And in my ticTacToe I have a simple loop :

while(!isFinished()){
    swapPlaying(); //Change the players' turn
    Position toPlay = playing.whereToMove();

    applyPosition(toPlay);
    playing.update(toPlay);
}

//Here I just update my players whether they won, draw or lost.

In my players, I select the move with epsilon-greedy implemented sa below :

Moves moves = getMoves(); // Return every move available
Qvalues qValues = getQValues(moves); // return only qvalues of interest
//also create the state and add it to the Q-matrix if not already in.

if(!optimal) {
     updateEpsilon(); //I update epsilon with simple linear function epsilon = 1/k, with k being the number of games played.
     double r = (double) rand() / RAND_MAX; // Random between 0 and 1
     if(r < epsilon) { //Exploration
         return randomMove(moves); // Selection of a random move among every move available.
     }
     else {
         return moveWithMaxQValue(qValues);
     }
} else { // If I'm not in the training part anymore
     return moveWithMaxQValue(qValues);
  }

And I update with the following :

double reward = getReward() // Return 1 if game won, -1 if game lost, 0 otherwise
double thisQ, maxQ, newQ;
Grid prevGrid = Grid(*grid); //I have a shared_ptr on the grid for simplicity
prevGrid.removeAt(position) // We remove the action executed before

string state = stateToString(prevGrid);
thisQ = qTable[state][action];
mawQ = maxQValues();

newQ = thisQ + alpha * (reward + gamma*maxQ - thisQ);
qTable[state][action] = newQ;

As mentioned above, both AI have the same algorithm, but they are two distinct instances, so they don't have the same Q-matrix.

I read somewhere on Stack Overflow that I should take in account the movement of the opposite player, but I update a state after player move and opponent move, so I don't think it's necessary.

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ are you sure of the implementation? tic tac toe has a very limited set of alternative scenarios and Q-learning can even "memorize" the best game policy after a few number of iterations $\endgroup$
    – Alireza
    Commented Apr 12, 2017 at 18:37
  • $\begingroup$ Well I'm not very sure, but when it plays against me, it learns how to avoid loosing against my strategy. But it still need a couple of training set against me to properly learn. I thought I could have a self-trained program with both AI having a Q-learning algorithm. I figured something was wrong in the training part rather than the implementation. Maybe I can train it against an algorithm with minimax ? $\endgroup$
    – Irindul
    Commented Apr 16, 2017 at 15:07
  • $\begingroup$ I guess minimax would not be a good opponent for your algorithm; while minimax always plays the best move, so your QL algorithm always lose. and you know, QL learns from losing and winning, not only losing. self trained QLs should work. Check your explore-exploit ratio. It should start from around 0.95 and decrease over time. $\endgroup$
    – Alireza
    Commented Apr 16, 2017 at 20:07
  • $\begingroup$ I actually have a fixed ratio, I will try to make it decrease over time. $\endgroup$
    – Irindul
    Commented Apr 18, 2017 at 9:25
  • $\begingroup$ I've checked, and after 200,000 games, the AI has visited only 3000 states approximately, this mean there is a problem in my implementation doesn't it ? $\endgroup$
    – Irindul
    Commented Apr 18, 2017 at 14:11

1 Answer 1

Reset to default
2
$\begingroup$

I couldn't add a comment because of my low reputation but you can check this. It is about the state space. https://math.stackexchange.com/questions/485752/tictactoe-state-space-choose-calculation

Improve this answer
$\endgroup$
5
  • $\begingroup$ So there are actually 5000 states, but after a quick correction on my program, I only got 300 states visited.. $\endgroup$
    – Irindul
    Commented Apr 19, 2017 at 14:01
  • $\begingroup$ I didn't go through your code, but maybe you should try anniling the epsilon less in every iteration $\endgroup$
    – Molnár István
    Commented Apr 19, 2017 at 16:00
  • $\begingroup$ I'd recommend checking out this article (brianshourd.com/posts/…) on the number of states in tic-tac-toe. From my understanding of it, a reinforcement learning (Q-learning) AI program would need to know that there are 593 board states. $\endgroup$
    – Daniel G
    Commented Dec 28, 2017 at 0:43
  • $\begingroup$ @DanielG From what I know about Q learning, you can start with an empty Q matrix and just grow it as the bot learns. $\endgroup$
    – Alexus
    Commented Mar 12, 2018 at 23:23
  • $\begingroup$ This is an old question/answer, but could you edit this answer to provide more details? $\endgroup$
    – nbro
    Commented Apr 8, 2022 at 10:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .