14
$\begingroup$

I'm currently reading about machine learning and wondered how to apply it to playing Connect Four.

My current attempt is a simple multiclass classificator using a sigmoid function model and the one-vs-all method.

In my opinion, the input features have to be the state (disc of player 1, disc of player 2, empty) of the 7x6=42 grid fields.

The output would be the number of the row to put the disc into. Because that is a discrete number between 1 and 7, I guess this can be treated as a multiclass classification problem.

But how do I generate training examples usable in supervised learning?

The main goal is to win the game but the outcome obviously isn't known when doing every but the last turn. If I just let two players who decide randomly what to do play against each other thousands of times, will it be sufficient to simply take all turns made by the winner of each game round as training examples? Or do I have to do this in a completly different way?

Edit: As suggested in the comments I read a little about reinforcement learning. From what I know understand, Q-Learning should do the trick, i.e. I have to approximate a function Q of the current state and the action to take to be the maximum cumulative reward beginning in that state. Then each step would be to choose the action which results in the maximum value of Q. However, this game has way too many states in order to do this e.g. as a lookup table. So, what is an effective way to model this Q-Function?

Improve this question
$\endgroup$
9
  • 2
    $\begingroup$ Google "Reinforcement Learning" $\endgroup$
    – George
    Commented Apr 7, 2012 at 20:23
  • $\begingroup$ Okay, I guess that really applies exactly to this problem. Seems like there is much reading ahead. Any more specific pointers or recommendations? $\endgroup$
    – Tom
    Commented Apr 8, 2012 at 13:09
  • 1
    $\begingroup$ If I knew more I would post it as an answer :) Unfortunately I have no experience in reinforcement learning. I would start from the book "Machine Learning" by Tom Mitchell. It is a very good introductory book and also has a chapter about Reinforcement Learning. $\endgroup$
    – George
    Commented Apr 8, 2012 at 20:03
  • 1
    $\begingroup$ The latter, I'm just curious about machine learning and trying to get to know it. $\endgroup$
    – Tom
    Commented Apr 8, 2012 at 20:45
  • 1
    $\begingroup$ @Tom, there are better ways to 'get to know' machine learning techniques. I'd start with more basic classification and regression techniques and move forward from there. You can grab datasets from UCI's machine learning data repository, check out Andrew Ng's (Stanford) machine learning course notes and get implementing. Jumping straight into trying to solve connect 4 using reinforcement learning seems quite awkward and overly complicated. $\endgroup$
    – Nick
    Commented Apr 10, 2012 at 20:11

2 Answers 2

Reset to default
8
$\begingroup$

Just to offer a simpler alternative to reinforcement learning, you can use the basic minimax algorithm to search for good moves, and use machine learning to evaluate board positions.

To clarify, minimax builds a game tree where each node is labeled with the outcome from the leaves up (1=player A wins, 0=player B wins), assuming that A chooses the moves that maximize this number, and B chooses the moves that minimize it.

Unless the game is very simple, you won't be able to construct the whole game tree down to the terminals. You'll instead need to stop at unfinished board positions and evaluate the leaves with some heuristic (essentially the probability that player A will win from the given position). You can let a machine learning algorithm like a neural network try to learn this probability from connect four positions with known outcomes.

To generate training examples you could build your minimax player with a simple heuristic, let it play itself a thousand times, use those games to train your first neural network, then let that pay itself a thousand games and so on. With a little luck, your system will improve with each generation.

Improve this answer
$\endgroup$
2
$\begingroup$

I wrote a blogpost about using minimax to play connect four a while ago. You can see the code in action here. If you need to train your models, you can perhaps let it play a couple of thousand games against my minimax implementation.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Feel free to fork my code on Github. github.com/lukasvermeer/minimax $\endgroup$
    – Lukas Vermeer
    Commented Jun 12, 2012 at 10:15
  • $\begingroup$ Welcome to Stack Exchange. This is a questions and answers site. Please read our faq, in particular how to answer. In particular, we do not want posts that consist solely of a link to an answer. Thank you for your contribution, but could you please summarize the main points of your blog post in your post here? $\endgroup$
    – Gilles 'SO- stop being evil'
    Commented Jun 12, 2012 at 14:06
  • $\begingroup$ I'm sorry, but the original question was "how do I generate training examples usable in supervised learning?" I provided links to working code that can be used to generate these. I fail to see how writing more text above would help the to answer the original need. $\endgroup$
    – Lukas Vermeer
    Commented Jun 13, 2012 at 8:35
  • $\begingroup$ "A link to a potential solution is always welcome, but please add context around the link so your fellow users will have some idea what it is and why it’s there . Always quote the most relevant part of an important link, in case the target site is unreachable or goes permanently offline." I think I did do the former. The latter would be irrelevant. The original question is in need of example games, not an explanation of how to implement a solution. $\endgroup$
    – Lukas Vermeer
    Commented Jun 13, 2012 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.