0

I am programming a game of connect 4. The game array is (6,7) and contains 0s in locations where a player has not yet moved. There are 2 players (player 1 and 2). Currently, this is how I check for victory

def check_success(game_array):
    assert (np.shape(game_array)==(6,7)), 'Incorrect shape'
    for s_r in range(3):
        for s_c in range(4):
            board=game_array[s_r:s_r+4,s_c:s_c+4]*1
            D = np.einsum('ii->i', board)
            DP = D != 0
            if DP[0] and (D[0] == D).all():
                return True, D[0]
            L = DP & (D == board).all(0)
            I = L.argmax()
            if L[I]:
                return True, D[I]
            L = DP & (D == board.T).all(0)
            I = L.argmax()
            if L[I]:
                return True, D[I]
            D = np.einsum('ii->i', board[::-1])
            if D[0] and (D[0] == D).all():
                return True, D[0]
    return False, 0

Can anyone think of a way of handling this without the for loops (or at least fewer iterations)? I looked into numpy.diff and create a for loop to 7 to check rows/columns at the same time (cuts the amount of iterations by 7/12). But I could not come up with an implementation.

James Carter
  • 803
  • 2
  • 10
  • 18
  • 1
    What have you done to my code ?!? ;-) Re your problem: did you consider only checking incrementally, i.e. only fours that contain the last piece played? – Paul Panzer Jun 25 '18 at 00:52
  • Wow wait, that's so obvious. Of course. That'll help a lot. – James Carter Jun 25 '18 at 13:19
  • Also, I do eventually want to expand this game to many dimensions and many different players (as in the previous question) so this method would be great in terms of scalability. – James Carter Jun 25 '18 at 13:24

1 Answers1

0

The solution, based on Checkio - Xs and Os solution and that answer:

def check_success(field):
    rows = field.tolist()
    cols = field.T.tolist()
    diags = [field[::-1,:].diagonal(i)
        for i in range(-field.shape[0] + 1, field.shape[1])]
    diags.extend(field.diagonal(i)
        for i in range(field.shape[1] - 1, -field.shape[0], -1))

    lines = diags + cols + rows
    for line in lines:
        if "2, 2, 2, 2" in repr(line):
            return "2 wins"
        elif "1, 1, 1, 1" in repr(line):
            return "1 wins"
    return "no winner"

It improves readability, not efficiency. However, efficiency is not crucial for 6 x 7 field.

koPytok
  • 3,453
  • 1
  • 14
  • 29
  • The reason I'm pushing for efficiency is because I am trying to design the most efficient engine to choose a move. In that algorithm, I have certain move combinations (All for brute force, Some for certain pruning methods, etc.) but the algorithm has to check for victory often. Checking for victory has slowed me down considerably and not allowing me to use the algorithm with any meaningful depth (I, myself, have had a 40% win rate with the comp and I suck at this game). – James Carter Jun 25 '18 at 13:23
  • Ok, in that case efficiency matters. Anyway, I'll leave the answer :) – koPytok Jun 25 '18 at 13:51