1
$\begingroup$

I'm creating an RL application for the game Connect Four.

If I tell the algorithm which moves/token positions will receive greater rewards, surely it's not actually learning anything; it's just a basic lookup for the algorithm? "Shall I place the token here, or here? Well, this one receives a greater reward, so I choose this one."

For example, some pseudocode:

function get_reward()
    if 2 in a line
        return 1
    if 3 in a line
        return 2
    if 4 in a line
        return 10
    else 
        return -1

foreach columns
    column_reward_i = get_reward(column_i)
    if column_reward_i >= column_rewards
        place_token(column_i)
$\endgroup$
2
  • $\begingroup$ Maybe you could show a plot of the performance of your algorithm through time. $\endgroup$
    – nbro
    Apr 4, 2020 at 14:01
  • $\begingroup$ There is no code at the moment, I'm just trying to work out how, if I'm assigning values for different positions, the algorithm is actually learning anything? $\endgroup$
    – mason7663
    Apr 4, 2020 at 14:21

1 Answer 1

4
$\begingroup$

What you are proposing is closer to a heuristic for searching than a reward for RL. This is a blurred line, but generally if you start analysing the problem yourself, breaking it down into components and feeding that knowledge into the algorithm, then you place more emphasis on your understanding of the problem, and less on any learning that an agent might do.

Typically in a RL formulation of a simple board game, you would choose rewards or +1 for a win (the goal), 0 for a draw, and -1 for a loss. All non-terminal states would score 0 reward. The point of the RL learning algorithm is that the learning process would assign some nominal value to interim states due to observing play. For value-based RL approaches, such as Q learning or Monte Carlo Control, the algorithm does this more or less directly by "backing up" rewards that it experiences in later states into average value estimates for earlier states.

Most game-playing agents will combine the learning process, which will be imperfect given the limited experience an agent can obtain compared to all possible board states, with a look-ahead search method. Your heuristic scores would also make a reasonable input to a search method too - the difference being you may need to search more deeply using your simple heuristic than if you used a learned heuristic. The simplest heuristic would just be +1 for a win, 0 for everything else, and is still reasonably effective for Connect 4 if you can make it search e.g. 10 moves ahead.

The combination of deep Q learning and negamax search is quite effective in Connect 4. It can make near perfect agents. However, if you actually want a perfect agent, you are better off skipping the self-learning approach and working on optimised look-ahead search with some depth of opening moves stored as data (because search is too expesnive in the early game, even for a simple game like Connect 4).

$\endgroup$
3
  • $\begingroup$ I actually have a Connect 4 agent in training right now, based on the +1/0/-1 reward scheme plus deep Q learning, thanks to this Kaggle competition: kaggle.com/c/connectx - there are plenty of examples and starter code available there $\endgroup$ Apr 4, 2020 at 15:19
  • $\begingroup$ Thank you, Neil. Your first paragraph confirms what I suspected – feeding the algorithm with the 'best' positions/moves means it's not actually learning! In your second paragraph "choose rewards for a win/lose/draw", are you referring to Monte Carlo methods? As these assign the rewards at the end of the episode/terminal state, right? The state space of Connect Four would be too large to use basic Q-Learning, correct? For look-ahead search methods, MiniMax and MCST? Can you recommend any others? Are these both Monte Carlo methods? The formatting on this is bad, I hope u can follow $\endgroup$
    – mason7663
    Apr 4, 2020 at 16:42
  • 1
    $\begingroup$ @mason7663 That's lots of extra questions and not really a good idea to follow up in comments with so many new directions. You can alsways ask a new question on the site, for any specific thing. Also I do recommend that you take a look at kaggle.com/c/connectx because lots of people had similar questions when that competition started and there's a whole bunch of resources linked $\endgroup$ Apr 4, 2020 at 17:16

You must log in to answer this question.

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