ИМХО для поля произвольной расмерности надо проверять не поле, а ход. Так как число выигрыщных комбинаций с ростом поля будет расти очень плохо. Думаю надо проверять каждый ход, не привел ли он к победе.
То есть после каждого хода проверяем последовательно
1. длина диагонали крестиков вверхвправо + внизвлево+1
2. длина диагонали крестиков вверхвлево+внизвправо+1
3. длина диагонали крестиков вправо+влево+1
4. длина диагонали крестиков вниз+вверх + 1
Если хотя бы одно направление больше целевого значения (на неограниченном поле вроде 5 в ряд играют), то игрок победил.

С одной стороны да, сложностей в приведении к какой-нибудь нормальной форме почти нет. Всего то типов связи - один к одному, один ко многим и многие ко многим через промежуточную таблицу. Выбрать почти всегда не сложно.
А вот когда сложности с производительностью - начинаются извращения с сознательной денормализацией и поддержанием актуальности в связанных таблицах (остатков, оборотов и детальных движений например). Вот про это и я бы общие подходы почитал. Так как знаю только подход одной желтой фирмы.

1. Шагать надо с 2 сторон
2. Если не влезаете в память, то шагать стоит в "глубину", а не в ширину. (перебор начиная с самых "любвеобильных") (помня о том, что "попасть" надо не во второго, а в одного из его связей, так проще)
К тому же:
Шаг 0: 1 человек
Шаг 1: 5000 максимум
Шаг 2: 25000000 максимум
Шаг 3: 40000000 максимум - уперлись

3 запроса, таблички теоретически большие, практически - все это перемалывается без проблем.