Thread: Reinforcement Learning, ConnectFour game

Hello! I've tried recently to solve the ConnectFour game using reinforcement learning (SARSA algorithm). I'm familiar with this method, but I have a big problem with the state space of this game. I identify a table board as a matrix (with 6 rows and 7 columns) and I need a method to classify similar matrix in order to minimize the state space (otherwise the learning algorithm will not learn). I tried with an artificial neural network. In fact, this is a back-propagation network with 126 input nodes (3 for every cell in the matrix -> coresponding to Red,Black or free cell). In the hidden layer I put 84 neurons and the output layer has 42 nodes. Unfortunately, to work with back-propagation I need to know the classed for the training examples, but I don't and the classification is very poor. Maybe you can help me with some hints. Also I want to know whether this ANN is good enough and what other methods can I use to classify the states (in order to minimize the state space)? Thanks a lot, MrRed

What does the storage have to do with the classification algorithms? Are you storing the "ANN" state directly?

How are you actually storing the data? You didn't actually say anything about the data structures you are using to store data.

You tried to classify a game of "Connect 4" with "ANN"? What state do you need to store? How "fuzzy" is the output?

Why does your output layer have 42 nodes? "Connect 4" is influenced by gravity; you play a column and the piece falls to the lowest cell.

Soma

I need classification in order to use the SARSA algorithm (reinforcement learning).
I use ANN to classify the states (of course, similar states), because, in naive version, there are 4.5T possible states (where T = 10^12). I said before...with so many states, SARSA can not learn anything.
For storing data (in fact the table board) i use a matrix with 6 rows and 7 columns, that's why the network has 42 output nodes.
But maybe this is not the best aproach...and I need some hints.

O_o

You misunderstood my questions. You didn't say anything new. I'm trying to get more information out of you so that I can help you do it instead of simply doing it for you. I'm not going to do it for you. (Call it a personal fault.) So, we kind of have an issue here.

If and when you come back, I am, again, looking for new information. You said you "use a matrix with 6 rows and 7 columns." Are you, for example, simply storing an array (`float mData[6][7];') for every "ANN" result?

Again, I can't help without knowing more about what you are actually doing!

Soma

Yes, I use an array...I have 42 nodes (6x7)...don't know what is so hard to understand. I do not want code from you, I only want some ideas. Again, I'm not saying that ANN will solve this problem, but I know this kind of network can classify things...or maybe we can find a surjective function to do the minimization of game boards

I appreciate your answer but it's the same thing...I have no problems with the memory (I do not need compression or stuff like that). SARSA can not learn because there are too many states.

Originally Posted by MrRed

I appreciate your answer but it's the same thing...I have no problems with the memory (I do not need compression or stuff like that). SARSA can not learn because there are too many states.

Which is probably why SARSA isn't used for games like connect 4, chess, checkers, etc.

Why don't you swing by the talkchess or openchess programming forums? That's where the chess programmers mostly talk shop, and you can get a few opinions on it from them. These are high-level programmers, so bring your geek hat, definitely!

Originally Posted by iMalc

So accounting for gravity, there are 1 + 2 + 2*2 + 2*2*2 + 2*2*2*2 + 2*2*2*2*2 + 2*2*2*2*2*2 = 127 possible states for each column, not 3*3*3*3*3*3 = 729, and even that's still assuming we don't stop after a win. It might at first seem like a small difference, but after working it out, clearly you're forcing it to learn based on more than 5 times the amount of actual information held within the valid board states.

Could you explain how did you calculate that possible states?

Originally Posted by iMalc

Also, without personally knowing anything about this SARSA algorithm, I can surmise that it will need to learn the relationship between the column it chooses, the board state at the time it chose, and whether the move turned out to be good or bad. The output from the algorithm will thus be just the column choice, not a choice from a 6*7 grid. So in that sense you're probably asking it to produce 6 times more output data than is required.

My background in AI is more along the lines of genetic algorithms and minimax, rather than this particular algorithm, so take this with a grain of salt... Lets just say that I believe I can somewhat see why it isn't working.

Well...generally, SARSA takes a matrix representing the board and returns a column which is the best move for that board. To do that, SARSA needs a smaller count of states...that's why I tried to get 6*7 outputs.

Well...generally, SARSA takes a matrix representing the board and returns a column which is the best move for that board. To do that, SARSA needs a smaller count of states...that's why I tried to get 6*7 outputs.

That isn't the general approach to SARSA and "Connect4"; as I already said, that approach is flawed.

Your network should be capable of correctly of reducing play to a column refinement. You only need the complete state of the board for later refinement, if you even do that, as a snapshot; you don't need the complete state of the board for input to the SARSA algorithm. The SARSA algorithm can't learn from mutating any point on the board because at any given time at most 7 plays can be made.

Soma