HackerRank Conway的生命博弈算法

Question

我最近已经解决了一个有趣的HackerRank问题，题为“康威的生命游戏”。问题陈述如下：

生命游戏是由英国数学家约翰·霍顿·康威设计的细胞自动机游戏。原来的游戏是一个零玩家游戏。它的演变完全取决于它的投入。 生命的游戏发生在2D网格上。网格中的每个单元将处于两种可能的状态之一， 活的死亡细胞的出生或死亡是基于以下规则。 如果一个细胞被3个活细胞所包围，它就会从死细胞变成活细胞。如果一个细胞被2个或3个活细胞包围，它就会存活。如果一个细胞由于人口过多而被三个以上的活细胞所包围，它就会从活着转变为死亡。如果由于人口不足而被不到2个细胞包围的话，细胞就会从活着变为死亡。每个细胞被8个细胞包围，4个在它的侧面，4个在它的角落。极端角的细胞只有3个邻接，在极右、左、上、下的细胞有5个相邻的细胞。上述规则也适用于这些单元格。 这个版本的生命游戏取代了29x29网格，左上角单元格为(0,0)，右下角单元格为(28,28)。它被索引为(行，列)，就像计算机科学中的数组。两名球员互相比赛。这个游戏与原始游戏不同的是，当一个细胞存活时，它有两个状态。这两个州 白黑第一条规则不同。 当一个细胞从死变成活的时候，它就假定了这三个细胞中大多数的颜色。因为3是奇数，所以多数总是存在的。其余的规则遵循原始版本的游戏。起初，所有的细胞都处于死亡状态。第一个玩家玩白色游戏，第二个玩家玩黑色游戏。每个玩家轮流将一个死细胞切换到活着的状态。活动单元格接受分配给播放机的颜色。这种情况一直持续到每个玩家将各自颜色的40个细胞放置在网格上。游戏就开始了。活细胞的最大颜色在500个生命周期结束时赢得游戏！ 输入格式 第一播放器由字符w (ascii值119)表示，第二播放器由字符b (ascii值98)表示。输入的第一行表示播放机的字符。以下29行。每一行都有29个字符，它们之间没有空格。活细胞由各自的特征表示，死细胞由- (ascii值45)表示。 输出 输出为两个单间隔整数，表示需要从死到活的单元格的位置。

这里有一个示例输入和示例输出，以及更多细节，在这里的官方问题站点：https://www.hackerrank.com/challenges/conway。

我想知道其他黑客使用了什么算法。我现在就在列表的底部--任何其他的观点都是非常有用的。

Answer 1

康威的“生命游戏”的两个玩家版本非常有趣，到目前为止，我已经开发并向HackerRank提交了一个可靠的算法(得分为41.656)。

我编写的程序试图在所有方面建立对角线，作为障碍，阻止对手部署他们的常规策略，同时也为我提供了更多的空间来复制和全面展开。

下面是我的实现(用Python)：

#!/usr/bin/python
# Conway's game of life - set up diagonals across the board
BOARD_SIZE = 28;

#get the next move, 
def nextMove(player, board):
    b = [] #append to b
    for s in board:
        b.append(list(s))
    
    #check up left (rows) 
    for r in range(0, BOARD_SIZE, 2):
        if (b[BOARD_SIZE - r][BOARD_SIZE] == "-"):
            return BOARD_SIZE - r, BOARD_SIZE
        else:
            row, col= diagUL(b, BOARD_SIZE - r, BOARD_SIZE)
            if (row!= -1):
                return row, col
    
    #check up left (cols)
    for c in range(0, BOARD_SIZE, 2):
        if (b[BOARD_SIZE][BOARD_SIZE - c] == "-"):
            return BOARD_SIZE, BOARD_SIZE - c
        else:
            row, col= diagUL(b, BOARD_SIZE, BOARD_SIZE - c)
            if (row!= -1):
                return row, col
    
    #check up right (rows) 
    for r in range(0, BOARD_SIZE, 2):
        if (b[r][BOARD_SIZE] == "-"):
            return r, BOARD_SIZE
        else:
            row, col= diagUR(b, r, BOARD_SIZE)
            if (row!= -1):
                return row, col
    
    #check up right (cols)
    for c in range(0, BOARD_SIZE, 2):
        if (b[0][BOARD_SIZE - c] == "-"):
            return 0, BOARD_SIZE - c
        else:
            row, col= diagUR(b, 0, BOARD_SIZE - c)
            if (row!= -1):
                return row, col

#gets the diagonals (up right and up left) 
def diagUL(bd, r, c):
    if (r == 0 or c == 0):
        return -1, -1
    elif (bd[r - 1][c - 1] == "-"):
        return r - 1, c - 1
    else:
        return diagUL(bd, r - 1, c - 1)

def diagUR(bd, r, c):
    if (r == BOARD_SIZE or c == 0):
        return -1, -1
    elif (bd[r + 1][c - 1] == "-"):
        return r + 1, c - 1
    else:
        return diagUL(bd, x + 1, y - 1)

#i/o
player = raw_input()
board = []
for row in xrange(0, 29):
    board.append(raw_input())
a,b = nextMove(player, board)
print a,b