| 1 | import { NUM_BASIC, toCounts, type Tile } from './tiles'; |
| 2 | |
| 3 | /** |
| 4 | * 向聽 — how many tiles a hand still has to exchange before it is 聽牌. |
| 5 | * 0 is ready, -1 is already a winning hand. |
| 6 | * |
| 7 | * `hu.ts` answers "is this hand finished"; this answers "how far off is it", |
| 8 | * which is the only question a computer player ever really asks. The two are |
| 9 | * kept apart because the win check has to be exact and this one has to be |
| 10 | * fast — it runs a few hundred times for every discard a bot considers. |
| 11 | * |
| 12 | * Everything here counts a hand at its *resting* size: (5 − melds) × 3 + 1 |
| 13 | * tiles, the shape you are in between a discard and your next draw. Comparing |
| 14 | * two lines of play means comparing them at that size, never a 17-tile hand |
| 15 | * against a 16-tile one. |
| 16 | */ |
| 17 | |
| 18 | /** One way of reading a group of tiles: complete sets, pairs, and other partials. */ |
| 19 | interface Profile { |
| 20 | sets: number; |
| 21 | /** Incomplete runs — 兩面, 嵌張, 邊張. Pairs are counted separately. */ |
| 22 | partials: number; |
| 23 | pairs: number; |
| 24 | } |
| 25 | |
| 26 | /** |
| 27 | * Suits are independent, so each is read on its own and the readings combined. |
| 28 | * The same nine-tile shape comes up constantly across a search, hence the cache. |
| 29 | */ |
| 30 | const profileCache = new Map<string, Profile[]>(); |
| 31 | |
| 32 | function profilesOf(counts: number[], runs: boolean): Profile[] { |
| 33 | const key = (runs ? 's' : 'h') + counts.join(''); |
| 34 | const hit = profileCache.get(key); |
| 35 | if (hit) return hit; |
| 36 | |
| 37 | const c = counts.slice(); |
| 38 | const out: Profile[] = []; |
| 39 | const seen = new Set<number>(); |
| 40 | |
| 41 | const record = (sets: number, partials: number, pairs: number) => { |
| 42 | const id = (sets * 8 + partials) * 8 + pairs; |
| 43 | if (seen.has(id)) return; |
| 44 | seen.add(id); |
| 45 | out.push({ sets, partials, pairs }); |
| 46 | }; |
| 47 | |
| 48 | const walk = (i: number, sets: number, partials: number, pairs: number) => { |
| 49 | while (i < c.length && c[i] === 0) i++; |
| 50 | if (i === c.length) return record(sets, partials, pairs); |
| 51 | |
| 52 | if (c[i] >= 3) { |
| 53 | c[i] -= 3; |
| 54 | walk(i, sets + 1, partials, pairs); |
| 55 | c[i] += 3; |
| 56 | } |
| 57 | if (c[i] >= 2) { |
| 58 | c[i] -= 2; |
| 59 | walk(i, sets, partials, pairs + 1); |
| 60 | c[i] += 2; |
| 61 | } |
| 62 | if (runs && i <= 6 && c[i + 1] > 0 && c[i + 2] > 0) { |
| 63 | c[i]--; c[i + 1]--; c[i + 2]--; |
| 64 | walk(i, sets + 1, partials, pairs); |
| 65 | c[i]++; c[i + 1]++; c[i + 2]++; |
| 66 | } |
| 67 | if (runs && i <= 7 && c[i + 1] > 0) { |
| 68 | c[i]--; c[i + 1]--; |
| 69 | walk(i, sets, partials + 1, pairs); |
| 70 | c[i]++; c[i + 1]++; |
| 71 | } |
| 72 | if (runs && i <= 6 && c[i + 2] > 0) { |
| 73 | c[i]--; c[i + 2]--; |
| 74 | walk(i, sets, partials + 1, pairs); |
| 75 | c[i]++; c[i + 2]++; |
| 76 | } |
| 77 | // ...or the tile is doing nothing for us, in this reading at least. |
| 78 | c[i]--; |
| 79 | walk(i, sets, partials, pairs); |
| 80 | c[i]++; |
| 81 | }; |
| 82 | |
| 83 | walk(0, 0, 0, 0); |
| 84 | profileCache.set(key, out); |
| 85 | return out; |
| 86 | } |
| 87 | |
| 88 | /** |
| 89 | * The classic count: every set is worth two tiles of progress and every |
| 90 | * partial one, up to the `need + 1` blocks a finished hand has room for, and a |
| 91 | * hand with no pair at all still owes one tile for it. |
| 92 | */ |
| 93 | function shantenOf(p: Profile, need: number): number { |
| 94 | const sets = Math.min(p.sets, need); |
| 95 | const blocks = Math.min(p.partials + p.pairs, need + 1 - sets); |
| 96 | const noPair = p.pairs === 0 && sets + blocks === need + 1 ? 1 : 0; |
| 97 | return 2 * need - 2 * sets - blocks + noPair; |
| 98 | } |
| 99 | |
| 100 | const GROUPS: [number, number, boolean][] = [ |
| 101 | [0, 9, true], // 萬 |
| 102 | [9, 18, true], // 條 |
| 103 | [18, 27, true], // 筒 |
| 104 | [27, NUM_BASIC, false], // 字牌 — no runs |
| 105 | ]; |
| 106 | |
| 107 | /** 向聽 of a concealed hand backed by `meldCount` exposed sets. */ |
| 108 | export function shanten(tiles: Tile[], meldCount: number): number { |
| 109 | const need = 5 - meldCount; |
| 110 | const counts = toCounts(tiles); |
| 111 | |
| 112 | // Fold the suits together, keeping one entry per distinct reading. The state |
| 113 | // space is tiny — sets, partials and pairs are all bounded by six. |
| 114 | let states = new Map<number, Profile>([[0, { sets: 0, partials: 0, pairs: 0 }]]); |
| 115 | for (const [lo, hi, runs] of GROUPS) { |
| 116 | const merged = new Map<number, Profile>(); |
| 117 | for (const a of states.values()) { |
| 118 | for (const b of profilesOf(counts.slice(lo, hi), runs)) { |
| 119 | const sets = Math.min(a.sets + b.sets, need); |
| 120 | const partials = Math.min(a.partials + b.partials, need + 1); |
| 121 | const pairs = Math.min(a.pairs + b.pairs, need + 1); |
| 122 | const id = (sets * 8 + partials) * 8 + pairs; |
| 123 | if (!merged.has(id)) merged.set(id, { sets, partials, pairs }); |
| 124 | } |
| 125 | } |
| 126 | states = merged; |
| 127 | } |
| 128 | |
| 129 | let best = 99; |
| 130 | for (const st of states.values()) best = Math.min(best, shantenOf(st, need)); |
| 131 | return best; |
| 132 | } |
| 133 | |
| 134 | /** |
| 135 | * 進張 — which tiles would bring the hand a step closer, and how many of each |
| 136 | * are still out there. `unseen` is counted from the caller's own point of |
| 137 | * view: the bot only ever subtracts what it can actually see. |
| 138 | */ |
| 139 | export function ukeire(tiles: Tile[], meldCount: number, unseen: number[]): { tiles: Tile[]; count: number } { |
| 140 | const now = shanten(tiles, meldCount); |
| 141 | const out: Tile[] = []; |
| 142 | let count = 0; |
| 143 | for (let t = 0; t < NUM_BASIC; t++) { |
| 144 | if (unseen[t] <= 0) continue; |
| 145 | if (shanten([...tiles, t], meldCount) < now) { |
| 146 | out.push(t); |
| 147 | count += unseen[t]; |
| 148 | } |
| 149 | } |
| 150 | return { tiles: out, count }; |
| 151 | } |