The Game

You will be playing an (almost) standard game of Connect-4. Unfortunately, it is a correspondence game and someone has placed black tape on every second row starting from the bottom, so that you cannot see any of your opponent's moves within these rows.

Any moves within already-full columns will count as passing your turn, and if a game runs for longer than 6 * 7 turns it will be adjudicated as a draw.

Challenge Specification

Your program should be implemented as a Python 3 function. The first argument is a 'view' of the board, representing the known board state as a 2D list of rows from bottom to top where 1 is a move by the first player, 2 a move by the second player, and 0 an empty position or a hidden move by your opponent.

The second argument is a turn number indexed from 0, and its parity tells you which player you are.

The final argument is an arbitrary state, initialized to None at the beginning of each game, which you can use to preserve state between turns.

You should return a 2-tuple of the column index you wish to play, and the new state to be returned to you next turn.

Scoring

A win counts as +1, a draw as 0, and a loss as -1. Your goal is to achieve the highest average score in a round-robin tournament. I will try to run as many matches as required to identify a clear winner.

Rules

Any competitor should have at most one competing bot at any one time, but it is OK to update your entry if you make improvements. Please try to limit your bot to ~1 second of thinking time per turn.

Testing

Here is the source code for the controller, together with a few non-competing example bots for reference:

import itertools
import random

def get_strides(board, i, j):
    yield ((i, k) for k in range(j + 1, 7))
    yield ((i, k) for k in range(j - 1, -1, -1))
    yield ((k, j) for k in range(i + 1, 6))
    yield ((k, j) for k in range(i - 1, -1, -1))
    directions = [(1, 1), (-1, -1), (1, -1), (-1, 1)]
    def diag(di, dj):
        i1 = i
        j1 = j
        while True:
            i1 += di
            if i1 < 0 or i1 >= 6:
                break
            j1 += dj
            if j1 < 0 or j1 >= 7:
                break
            yield (i1, j1)
    for d in directions:
        yield diag(*d)

DRAWN = 0
LOST = 1
WON = 2
UNDECIDED = 3

def get_outcome(board, i, j):
    if all(board[-1]):
        return DRAWN
    player = board[i][j]
    strides = get_strides(board, i, j)
    for _ in range(4):
        s0 = next(strides)
        s1 = next(strides)
        n = 1
        for s in (s0, s1):
            for i1, j1 in s:
                if board[i1][j1] == player:
                    n += 1
                    if n >= 4:
                        return WON
                else:
                    break
    return UNDECIDED

def apply_move(board, player, move):
    for i, row in enumerate(board):
        if board[i][move] == 0:
            board[i][move] = player
            outcome = get_outcome(board, i, move)
            return outcome
    if all(board[-1]):
        return DRAWN
    return UNDECIDED

def get_view(board, player):
    view = [list(row) for row in board]
    for i, row in enumerate(view):
        if i % 2:
            continue
        for j, x in enumerate(row):
            if x == 3 - player:
                row[j] = 0
    return view

def run_game(player1, player2):
    players = {1 : player1, 2 : player2}
    board = [[0] * 7 for _ in range(6)]
    states = {1 : None, 2 : None}
    for turn in range(6 * 7):
        p = (turn % 2) + 1
        player = players[p]
        view = get_view(board, p)
        move, state = player(view, turn, states[p])
        outcome = apply_move(board, p, move)
        if outcome == DRAWN:
            return DRAWN
        elif outcome == WON:
            return p
        else:
            states[p] = state
    return DRAWN

def get_score(counts):
    return (counts[WON] - counts[LOST]) / float(sum(counts))

def run_tournament(players, rounds=10000):
    counts = [[0] * 3 for _ in players]
    for r in range(rounds):
        for i, player1 in enumerate(players):
            for j, player2 in enumerate(players):
                if i == j:
                    continue
                outcome = run_game(player1, player2)
                if outcome == DRAWN:
                    for k in i, j:
                        counts[k][DRAWN] += 1
                else:
                    if outcome == 1:
                        w, l = i, j
                    else:
                        w, l = j, i
                    counts[w][WON] += 1
                    counts[l][LOST] += 1
        ranks = sorted(range(len(players)), key = lambda i: get_score(counts[i]), reverse=True)
        print("Round %d of %d\n" % (r + 1, rounds))
        rows = [("Name", "Draws", "Losses", "Wins", "Score")]
        for i in ranks:
            name = players[i].__name__
            score = get_score(counts[i])
            rows.append([name + ":"] + [str(n) for n in counts[i]] + ["%6.3f" % score])
        lengths = [max(len(s) for s in col) + 1 for col in zip(*rows)]
        for i, row in enumerate(rows):
            padding = ((n - len(s)) * ' ' for s, n in zip(row, lengths))
            print(''.join(s + p for s, p in zip(row, padding)))
            if i == 0:
                print()
        print()

def random_player(view, turn, state):
    return random.randrange(0, 7), state

def constant_player(view, turn, state):
    return 0, state

def better_random_player(view, turn, state):
    while True:
        j = random.randrange(0, 7)
        if view[-1][j] == 0:
            return j, state

def better_constant_player(view, turn, state):
    for j in range(7):
        if view[-1][j] == 0:
            return j, state

players = [random_player, constant_player, better_random_player, better_constant_player]

run_tournament(players)

Happy KoTHing!

Provisional Results

Name                    Draws Losses Wins  Score  

zsani_bot:              40    5377   94583  0.892 
better_constant_player: 0     28665  71335  0.427 
constant_player:        3     53961  46036 -0.079 
normalBot:              38    64903  35059 -0.298 
better_random_player:   192   71447  28361 -0.431 
random_player:          199   75411  24390 -0.510 
  • Could you explain why you check view[-1][j] == 0? I am not entirely sure I see where you filled them and my python knowledge seems to be a bit rusty. – Barbarian772 Sep 10 at 11:57
  • @Barbarian772 I'm checking if there is still space in that column. Note that there are 6 rows so the top row is fully-observed. – user1502040 Sep 10 at 12:03
  • 1
    You shouldn’t count placing in already full columns as a pass. Many connect 4 games end with only one column not filled and if one player will lose by playing in that column, this will make the game tie when it is otherwise a forced win for one player. – soktinpk Sep 10 at 16:35
  • @soktinpk Doesn't that just add another layer of strategy? Connect-4 is a solved game after all, so the turn skipping factor could be enough of a rule change that contributors can't just use the standard algorithms. – mypetlion Sep 10 at 17:56
  • 1
    Zero-indexing from the bottom, are the taped-over rows (0,2,4,6) or (1,3,5)? Some ASCII art would be helpful. – Blacksilver Sep 21 at 18:02

This bot takes all sure wins, and falls back to block the rivals, second guess them vertically and horizontally or make random moves.

import pprint, math, collections, copy
def zsani_bot_2(view, turn, state):
    if state == None: #first own turn - always for for middle
        state = (1, 2) if turn == 0 else (2, 1) #(my_symbol, your symbol)
        #print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]))
        return 3, state

    #locate obvious points
    for i in range (1, 6):              #skip first row
        for j in range(len(view[i])):   #TODO: Optimise with zip. Go for clarity now
            if view[i][j] != 0 and view[i-1][j] == 0:
                view[i-1][j] = state[1]
    enemy_points = math.floor(turn/2)
    ++enemy_points if state[0] == 2 else enemy_points
    known_points = sum([i.count(state[1]) for i in view])
    missing_points = enemy_points - known_points

    #get sure wins in any direction
    for j in range(0, 7): #every column
        for i in range(4, -1, -1):
            if view[i][j] !=0:
                break #find highest known filled point
        if (not missing_points or i+1 in {1, 3, 5}):
            view1 = copy.deepcopy(view)
            attempt = apply_move(view1, state[0], j)
            if attempt == WON:
               # print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' winner move')
                return j, state

    #block sure enemy wins in any direction
    for j in range(0, 7):
        for i in range(4, -1, -1):
            if view[i][j] !=0:
                break #find highest known filled point
        if (not missing_points or (i+1 in {1, 3, 5})):
            view1 = copy.deepcopy(view)
            attempt = apply_move(view1, state[1], j)
            if attempt == WON:
              #  print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' saving move')
                return j, state

    #block walls
    for i in range(0, 3): #impossible to get 4 in a row when the column is full
        for j in range(0, 6):
            if view[i][j] != 0 and view[i][j] == view[i+1][j] and view[i+2][j] == view[i+3][j] == 0:
             #   print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' column move')
                return j, state

    #block platforms if posessing perfect information on row below and drop point
    for i in range(0, 5):
        for j in range(0, 3):
            stats = collections.Counter([view[i][j], view[i][j+1], view[i][j+2], view[i][j+3]])
            if stats[0] == 2 and (stats[state[0]] == 2 or stats[state[0]] == 2):
                for k in range(0, 3):
                    if view[i][j+k] == 0:
                        break
                if (i == 0 or view[i-1][j+k] != 0) and (not missing_points or i in {1, 3, 5}):
                    #print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' platform move')
                    return j+k, state
                else:
                    for l in range (k, 3):
                        if view[i][j+l] == 0:
                            break
                        if (i == 0 or view[i-1][j+l] != 0) and (not missing_points or i in {1, 3, 5}):
                     #       print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' platform move')
                            return j+l, state

    #fallback -> random
    while True:
        j = random.randrange(0, 7)
        if view[-1][j] == 0:
            #print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' random move')
            return j, state

Thank you for fixing run_game!

Changelog:

  • v2 adds horizontal blocking - if, in a row of 4, there are two empty spots and two spots filled by the same player, it will attempt to fill one of them to have three in a row/block the opponents row, which will hopefully be capitalized upon in the following turns.
  • 3
    Welcome to the site. I voted to reject the edit to change to code, it would be best left as a comment, that way the OP can decide what to do with the code. – Post Left Garf Hunter Oct 8 at 16:20
  • I don't have enough reputation to comment on the main post. How do I withdraw an edit? – Syfer Polski Oct 8 at 16:30
  • No need to withdraw the edit (I don't think you can anyway). In the future commenting will be sufficient but since you have said it in your answer it is likely that the OP will see. Plus I think that the OP will see that you suggested and edit even if it has been rejected. – Post Left Garf Hunter Oct 8 at 16:44
  • The reason I'd like to withdraw the edit is because I missed one line in the changes, without which the edited code will completely fail to run. I've included it in the edit suggestion in my post. Thank you for your help! – Syfer Polski Oct 8 at 16:48

normalBot plays upon the assumption that spots in the middle are more valuable than spots on the ends. Thus, it uses a normal distribution centered in the middle to determine its choices.

def normalBot(view, turn, state):
    randomNumber = round(np.random.normal(3, 1.25))
    fullColumns = []
    for i in range(7):
        if view[-1][i] != 0:
            fullColumns.append(i)
    while (randomNumber > 6) or (randomNumber < 0) or (randomNumber in fullColumns):
        randomNumber = round(np.random.normal(3, 1.25))
    return randomNumber, state

This is obviously non-competing, but nonetheless very useful for debugging... and surprisingly fun, if you know your bot well enough to cheat :D so I'm posting in the hopes of inspiring more submissions:

import math, pprint
def manual_bot(view, turn, state):
    if state == None:
        state = (1, 2) if turn == 0 else (2, 1) #(my_symbol, your symbol)

#locate obvious points
    for row in range (1, 6):
        for j in range(len(view[row])):
            if view[row][j] != 0 and view[row-1][j] == 0:
                view[row-1][j] = state[1]

#if you're second, the opponent has one more point than half the turns
    enemy_points = math.ceil(turn/2)
    known_points = sum([row.count(state[1]) for row in view])
    missing_points = enemy_points - known_points

    print(pprint.pformat(view) + ' Turn: ' + str(turn) + ' Player: ' + str(state[0]) + ' Missing points: ' + str(missing_points))
    while True:
        try:
            move = int(input("What is your move?(0-6) "))
        except ValueError:
            continue
        if move in {0, 1, 2, 3, 4, 5, 6}:
            return move, state

The grid is upside down(the bottom row is highest). To get the winner announcements, you need to patch the game controller, adding a print statement before returning the win:

elif outcome == WON:
    print(pprint.pformat(board) + ' Turn: ' + str(turn) +' Winner: '+ str(p))
    return p

[[0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turn: 0 Player: 1 Missing points: 0
What is your move?(0-6) 3
[[0, 0, 0, 1, 0, 0, 0],
 [0, 0, 0, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turn: 2 Player: 1 Missing points: 0
What is your move?(0-6) 2
[[0, 0, 1, 1, 0, 0, 0],
 [0, 0, 0, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turn: 4 Player: 1 Missing points: 1
What is your move?(0-6) 4
[[0, 0, 1, 1, 1, 0, 0],
 [0, 0, 0, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turn: 6 Player: 1 Missing points: 2
What is your move?(0-6) 1
[[2, 1, 1, 1, 1, 2, 0],
 [0, 0, 0, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turn: 6 Winner: 1
[[0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turn: 1 Player: 2 Missing points: 1
What is your move?(0-6) 2
[[0, 0, 2, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turn: 3 Player: 2 Missing points: 2
What is your move?(0-6) 3
[[0, 0, 2, 1, 0, 0, 0],
 [0, 0, 1, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turn: 5 Player: 2 Missing points: 1
What is your move?(0-6) 4
[[0, 0, 2, 1, 2, 0, 0],
 [0, 0, 1, 2, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turn: 7 Player: 2 Missing points: 2
What is your move?(0-6) 1
[[0, 2, 2, 1, 2, 0, 0],
 [0, 0, 1, 2, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0, 0, 0]] Turn: 9 Player: 2 Missing points: 1
What is your move?(0-6) 2
[[0, 2, 2, 1, 2, 0, 0],
 [0, 0, 1, 2, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turn: 11 Player: 2 Missing points: 1
What is your move?(0-6) 4
[[0, 2, 2, 1, 2, 0, 0],
 [0, 0, 1, 2, 2, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turn: 13 Player: 2 Missing points: 2
What is your move?(0-6) 4
[[0, 2, 2, 1, 2, 0, 0],
 [0, 1, 1, 2, 2, 0, 0],
 [0, 0, 1, 0, 1, 0, 0],
 [0, 0, 1, 0, 2, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turn: 15 Player: 2 Missing points: 1
What is your move?(0-6) 3
[[0, 2, 2, 1, 2, 0, 0],
 [0, 1, 1, 2, 2, 0, 0],
 [0, 0, 1, 2, 1, 0, 0],
 [0, 0, 1, 0, 2, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turn: 17 Player: 2 Missing points: 2
What is your move?(0-6) 5
[[0, 2, 2, 1, 2, 1, 1],
 [0, 1, 1, 2, 2, 2, 1],
 [0, 0, 1, 2, 1, 0, 0],
 [0, 0, 1, 0, 2, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turn: 19 Player: 2 Missing points: 0
What is your move?(0-6) 
What is your move?(0-6) 6
[[0, 2, 2, 1, 2, 1, 1],
 [0, 1, 1, 2, 2, 2, 1],
 [0, 0, 1, 2, 1, 0, 2],
 [0, 0, 1, 0, 2, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turn: 21 Player: 2 Missing points: 1
What is your move?(0-6) 1
[[0, 2, 2, 1, 2, 1, 1],
 [0, 1, 1, 2, 2, 2, 1],
 [0, 2, 1, 2, 1, 0, 2],
 [0, 1, 1, 0, 2, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turn: 23 Player: 2 Missing points: 1
What is your move?(0-6) 3
[[0, 2, 2, 1, 2, 1, 1],
 [0, 1, 1, 2, 2, 2, 1],
 [0, 2, 1, 2, 1, 0, 2],
 [0, 1, 1, 2, 2, 0, 0],
 [0, 0, 2, 0, 0, 0, 0],
 [0, 0, 1, 0, 0, 0, 0]] Turn: 25 Player: 2 Missing points: 2
What is your move?(0-6) 6
[[0, 2, 2, 1, 2, 1, 1],
 [0, 1, 1, 2, 2, 2, 1],
 [0, 2, 1, 2, 1, 0, 2],
 [0, 1, 1, 2, 2, 0, 2],
 [0, 0, 2, 1, 0, 0, 0],
 [0, 0, 1, 1, 0, 0, 0]] Turn: 27 Player: 2 Missing points: 1
What is your move?(0-6) 5
[[1, 2, 2, 1, 2, 1, 1],
 [1, 1, 1, 2, 2, 2, 1],
 [0, 2, 1, 2, 1, 2, 2],
 [0, 1, 1, 2, 2, 0, 2],
 [0, 0, 2, 1, 0, 0, 0],
 [0, 0, 1, 1, 0, 0, 0]] Turn: 29 Player: 2 Missing points: 0
What is your move?(0-6) 5
[[1, 2, 2, 1, 2, 1, 1],
 [1, 1, 1, 2, 2, 2, 1],
 [0, 2, 1, 2, 1, 2, 2],
 [0, 1, 1, 2, 2, 2, 2],
 [0, 0, 2, 1, 0, 0, 0],
 [0, 0, 1, 1, 0, 0, 0]] Turn: 29 Winner: 2
Round 1 of 1

Name Draws Losses Wins Score
manual_bot: 0 0 2 1.000 zsani_bot_2: 0 2 0 -1.000

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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