0
$\begingroup$

I would like to implement Q-learning in a game.

Here is the board:

enter image description here

It's a 2 player game. At each turn, each player can put a pawn on a line of their choice. They can't choose the column. The right player will put their pawn on the right column and the left player will put their pawn on the other side. At each turn, each pawn will advance in the direction of the opponent. Each pawn has a cost and each player has an amount of money and health points.

I was wondering how I could enumerate the number of states, and it seems impossible.

Given the number of possible states, is Q-learning a solution? If it is, is it possible to add states to the Q-table after the game has started? If Q-learning isn't a solution, what could I use?

$\endgroup$
5
  • 1
    $\begingroup$ Put your SPECIFIC question in the title. "Add states Q-learning" is not a question. Furthermore, Q-learning is an algorithm and saying "add states Q-learning" doesn't seem to make much sense. So, please, try to ask a clear specific question and put in the title. $\endgroup$
    – nbro
    Jun 10, 2022 at 17:29
  • $\begingroup$ No need to be so agressive. You understood the question. Anyway, I edited it. $\endgroup$
    – Dunno
    Jun 10, 2022 at 17:34
  • $\begingroup$ Well, "Add states Q-table after initialization" still doesn't make sense and it's not a question, so now it should be clearer why I used capitals and bold. My intention was not to be aggressive but to be super clear. Apparently, it was highly ineffective, but sometimes it is. Here's a clear a question: "What is 2+2? Is it 4 or 5?" $\endgroup$
    – nbro
    Jun 10, 2022 at 17:41
  • 1
    $\begingroup$ @Dunno Hello and welcome to AI Stack Exchange! Sometimes we are very direct on this website because we want you to receive the best possible answer to your question. We appreciate that you are here, and we look forward to seeing your questions and answers in the near future! :) $\endgroup$
    – DeepQZero
    Jun 10, 2022 at 18:02
  • $\begingroup$ As usual, I do the dirty work of making posts (even those that are not mine) great here. Thank you... This is the last time I do this for you. You should have followed my recommendation to improve your post. Next time, I will just leave the downvote. $\endgroup$
    – nbro
    Jun 11, 2022 at 15:38

1 Answer 1

0
$\begingroup$

Yes, it is possible to add states to a Q table after the game has started, for example by storing the "table" in a binary tree.

Nonetheless, with a simple interpretation of state (like all the pawn positions), Q learning won't work because there are just too many states. Most states will be new so the agent will choose most actions randomly.

Instead, you'll need to reduce the state space with hand-crafted features, or approximate Q values with a classic Q function approximation or a neural network.

I'd choose the latter alternative, which is called a Deep Q Network, but neural networks might be challenging if you aren't familiar with them.

Alternatively, you could use Monte Carlo Tree Search.

$\endgroup$
5
  • $\begingroup$ It's my problem: every state would be seen as new. I only have experience with neural networks for image recognition. Would you be so kind as to give me the name of a book that would point me in the right direction? I hope it isn't strictly forbidden. $\endgroup$
    – Dunno
    Jun 10, 2022 at 19:20
  • $\begingroup$ Reinforcement Learning: An Introduction by Richard S. Sutton and Andrew G. Barto is the book I learned from. And it's available online at: incompleteideas.net/book/the-book-2nd.html $\endgroup$
    – Lee Reeves
    Jun 10, 2022 at 19:32
  • $\begingroup$ But it's a full textbook covering a lot of RL, and the section on Q learning may be hard to understand on its own. You might find a good tutorial by searching for Approximate Q-Learning or Q function approximation. $\endgroup$
    – Lee Reeves
    Jun 10, 2022 at 19:35
  • $\begingroup$ Is it a legal version? $\endgroup$
    – Dunno
    Jun 10, 2022 at 19:38
  • 1
    $\begingroup$ Yes, it's from the authors. The book is Creative Commons licensed, and also sold on Amazon. $\endgroup$
    – Lee Reeves
    Jun 10, 2022 at 19:43

You must log in to answer this question.

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