Last active
December 1, 2025 18:29
-
-
Save ScriptRaccoon/3383fa36f55fa0184e45fa9b258c3295 to your computer and use it in GitHub Desktop.
Determines which Player wins in Treblecross (TypeScript)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // return true iff player 1 has a winning strategy for n-size treblecross | |
| // https://en.wikipedia.org/wiki/Treblecross | |
| function treblecross_win_optimized(n: number): boolean { | |
| if (n === 0 || n === 2) return false | |
| if (n === 1) return true | |
| if (n >= 32) throw new Error("We use bitmasks, only n <= 32 allowed.") // FIXME | |
| const cache: Map<number, boolean> = new Map() | |
| let board = 0 | |
| function win_from_board(): boolean { | |
| const cached_result = cache.get(board) | |
| if (cached_result !== undefined) return cached_result | |
| // check for direct wins | |
| for (let j = 0; j + 1 < n; j++) { | |
| // check if j,j+1 are filled => then j-1 (if j > 0) or j+2 (if j+2 < n) is winning | |
| if ((board >> j) & 1 && (board >> (j + 1)) & 1) { | |
| cache.set(board, true) | |
| return true | |
| } | |
| // check if j and j+2 are filled (if j+2 < n), then j+1 is winning | |
| if (j + 2 < n && (board >> j) & 1 && (board >> (j + 2)) & 1) { | |
| cache.set(board, true) | |
| return true | |
| } | |
| } | |
| // try move at index i | |
| for (let i = 0; i < n; i++) { | |
| if ((board >> i) & 1) continue | |
| // do not move next to a 1, since then you loose afterwards | |
| if (i + 1 < n && (board >> (i + 1)) & 1) continue | |
| if (i >= 1 && (board >> (i - 1)) & 1) continue | |
| // choose i | |
| board |= 1 << i | |
| const opponent_wins = win_from_board() | |
| // unchoose i | |
| board &= ~(1 << i) | |
| if (!opponent_wins) { | |
| // move i was winning | |
| cache.set(board, true) | |
| return true | |
| } | |
| } | |
| // no winning move has been found | |
| cache.set(board, false) | |
| return false | |
| } | |
| return win_from_board() | |
| } | |
| console.info("detect P-positions:") | |
| for (let n = 0; n <= 30; n++) { | |
| const win = treblecross_win_optimized(n) | |
| if (!win) console.info(n) | |
| } | |
| // returns: 0,2,6,12,22,30 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment