#include #include #include #include #include enum{ DARK, LIGHT, KING, BAIZE, LSQ, HSQ, DSQ, HUE, Eremote = 8, SQ = 50, RAD = 20, MOVE = 512, MSG = 8, MSGLEN = 128, ↖ = 0x79fbf3db, ↗ = 0x7dfdf5dd, ↙ = 0xfbfbebba, ↘ = 0xfdf9edbc, CROWNHEAD = 0x82041861, ∞ = 0x7fffffff }; ulong rgb[HUE] = { [DARK] DRed, [LIGHT] DWhite, [KING] DBlack, [BAIZE] DDarkgreen, [LSQ] DPaleyellow, [HSQ] DPalegreygreen, [DSQ] DYellowgreen }; char bitboard[32] = {/* dark pieces at bottom */ 11, 5, 31, 25, 10, 4, 30, 24, 3, 29, 23, 17, 2, 28, 22, 16, 27, 21, 15, 9, 26, 20, 14, 8, 19, 13, 7, 1, 18, 12, 6, 0}; Rectangle sq[32], r[3]; Image *hue[HUE]; char msg[MSG][MSGLEN], p[2][64]; u32int b[3], m[MOVE], h, jump, slide; int t, v, msgn, flip = 1; int aislide(int, int, int, u32int*); void drawboard(void){ Point o; u32int i, bit; for(i = 0; i < 32; i++){ bit = 1 << i; o = addpt(sq[i].min, Pt(SQ >> 1, SQ >> 1)); draw(screen, sq[i], hue[HSQ + !(bit & h)], nil, ZP); if(bit & (b[DARK] | b[LIGHT])){ fillellipse(screen, o, RAD, RAD, hue[!(bit & b[DARK])], ZP); ellipse(screen, o, RAD, RAD, 0, hue[KING], ZP); if(bit & b[KING]) ellipse(screen, o, RAD >> 1, RAD >> 1, 0, hue[KING], ZP); } } } void drawmsgs(void){ Point o; int i; draw(screen, r[2], hue[LIGHT], nil, ZP); for(o = r[2].min, i = 0; i < MSG; o.y += font->height) string(screen, o, hue[KING], ZP, font, msg[msgn + i++ & MSG - 1]); } void drawlabel(int i){ draw(screen, r[i], hue[BAIZE], nil, ZP); string(screen, addpt(r[i].min, Pt(Dx(r[i]) - stringwidth(font, p[i]) >> 1, 0)), hue[LSQ], ZP, font, p[i]); } void eresized(int i){ char *n; if(i && getwindow(display, Refnone) < 0) sysfatal("can't reattach to window"); if((!i || Dx(screen->r) != 10 * SQ + MSG * font->height) && (i = open("/dev/wctl", OWRITE)) >= 0){ fprint(i, "resize -dy %d", 10 * SQ + MSG * font->height + 2 * Borderwidth); close(i); } draw(screen, screen->r, hue[BAIZE], nil, ZP); r[0] = Rect(-4 * SQ, SQ, SQ << 2, 9 * SQ); r[0] = rectaddpt(r[0], Pt(screen->r.min.x + screen->r.max.x >> 1, screen->r.min.y)); draw(screen, r[0], hue[LSQ], nil, ZP); r[0].max = addpt(r[0].min, Pt(SQ, SQ)); n = bitboard + (31 & flip >> 1); for(i = -1; ++i < 32; n += flip) sq[*n] = rectaddpt(r[0], Pt(((i << 1 & 7) + !(i & 4)) * SQ, (i >> 2) * SQ)); drawboard(); i = flip > 0; r[1] = Rect(0, -SQ - font->height >> 1, 8 * SQ, font->height - SQ >> 1); r[i] = rectaddpt(r[1], r[0].min); drawlabel(i); r[!i] = rectaddpt(r[i], Pt(0, 9 * SQ)); drawlabel(!i); r[2] = screen->r; r[2].min.y += 10 * SQ; drawmsgs(); } void zero(void){ b[DARK] = 0x41c71c3; b[LIGHT] = 0xe3820c38; slide = 0x4104100; b[KING] = jump = v = h = 0; } void movers(void){ u32int nw, se, n, s, e, ∅; n = b[v & 1] & b[(v & 1) << 1]; s = b[v & 1] & b[!(v & 1) + 1]; e = b[~v & 1]; ∅ = ~(b[DARK] | b[LIGHT]); nw = (∅ >> 7 | ∅ << 25) & e & ↖; se = (∅ << 7 | ∅ >> 25) & e & ↘; jump = (nw >> 7 | nw << 25) & n & ↖ | (∅ >> 1 & e & ↗) >> 1 & n & ↗ | (∅ << 1 & e & ↙) << 1 & s & ↙ | (se << 7 | se >> 25) & s & ↘; slide = jump ? 0 : (∅ >> 7 | ∅ << 25) & n & ↖ | ∅ >> 1 & n & ↗ | ∅ << 1 & s & ↙ | (∅ << 7 | ∅ >> 25) & s & ↘; } u32int jumps(u32int from){ u32int to, n, s, e, ∅; n = from & b[DARK] | from & b[LIGHT] & b[KING]; s = from & b[LIGHT] | from & b[DARK] & b[KING]; e = b[!(from & b[LIGHT])]; ∅ = ~(b[DARK] | b[LIGHT]); to = (n << 1 & e & ↙) << 1 & ∅ & ↙; n = (n << 7 | n >> 25) & e & ↘; to |= (n << 7 | n >> 25) & ∅ & ↘; to |= (s >> 1 & e & ↗) >> 1 & ∅ & ↗; s = (s >> 7 | s << 25) & e & ↖; return to | (s >> 7 | s << 25) & ∅ & ↖; } u32int slides(u32int from){ u32int n, s, ∅; n = from & b[DARK] | from & b[LIGHT] & b[KING]; s = from & b[LIGHT] | from & b[DARK] & b[KING]; ∅ = ~(b[DARK] | b[LIGHT]); return ∅ & ↘ & (n << 7 | n >> 25) | ∅ & ↙ & n << 1 | ∅ & ↗ & s >> 1 | ∅ & ↖ & (s >> 7 | s << 25); } void move(u32int mv){ u32int rm; rm = ~(mv & b[~v & 1]); mv &= rm; b[~v & 1] &= rm; b[KING] &= rm; b[v & 1] ^= mv; if(mv & b[KING]) b[KING] ^= mv; else if(mv & b[v & 1] & CROWNHEAD) b[KING] |= mv & b[v & 1]; } void getjumps(u32int *mv, int *i, u32int from, u32int ∅, u32int n, u32int s, u32int e, u32int rm){ u32int x, to, j = 0; if((x = (n << 7 | n >> 25) & e & ↘) && (to = (x << 7 | x >> 25) & ∅ & ↘) && ++j) getjumps(mv, i, from, ∅ ^ to | x | n, to, s ? to : 0, e ^ x, rm | x); if((x = n << 1 & e & ↙) && (to = x << 1 & ∅ & ↙) && ++j) getjumps(mv, i, from, ∅ ^ to | x | n, to, s ? to : 0, e ^ x, rm | x); if((x = (s >> 7 | s << 25) & e & ↖) && (to = (x >> 7 | x << 25) & ∅ & ↖) && ++j) getjumps(mv, i, from, ∅ ^ to | x | s, n ? to : 0, to, e ^ x, rm | x); if((x = s >> 1 & e & ↗) && (to = x >> 1 & ∅ & ↗) && ++j) getjumps(mv, i, from, ∅ ^ to | x | s, n ? to : 0, to, e ^ x, rm | x); if(j == 0) mv[(*i)++ & 7] = from | n | s | rm; } int aijump(int d, int α, int β, u32int *mv){ u32int old[3], froms, from, j[8]; int i, val; for(froms = jump; α < β && (from = froms & -froms); froms ^= from){ i = 0; getjumps(j, &i, from, ~(b[DARK] | b[LIGHT]), from & (b[DARK] | b[LIGHT] & b[KING]), from & (b[LIGHT] | b[DARK] & b[KING]), b[~v & 1], 0); if(i & ~7) i = 8; if(mv != nil) *mv = j[nrand(i)]; old[0] = b[0]; old[1] = b[1]; old[2] = b[2]; while(α < β && --i >= 0){ move(j[i]); v++; movers(); val = jump ? -aijump(d, -β, -α, nil) : -aislide(d, -β, -α, nil); if(val > α){ α = val; if(mv != nil) *mv = j[i]; } v--; b[0] = old[0]; b[1] = old[1]; b[2] = old[2]; } } return α; } int num(u32int bits){ int c; for(c = 0; bits; c++) bits &= bits - 1; return c; } int aislide(int d, int α, int β, u32int *mv){ u32int old[3], froms, from, tos, to; int val; if(!slide) return -∞; if(d < 1){ /* evaluate */ from = b[v & 1] & ~b[KING]; to = b[~v & 1] & ~b[KING]; froms = b[v & 1] & b[KING]; tos = b[~v & 1] & b[KING]; /* material advantage */ α = (num(b[v & 1]) << 9) + (num(froms) << 10); β = (num(b[~v & 1]) << 9) + (num(tos) << 10); if(α > β) val = (α - β) * α / (β ? β : 1); else val = (α - β) * β / (α ? α : 1); /* occupy centre, not sides */ val += num(from & 0x10608000) - num(to & 0x10608000) << 6; val += num(to & 0x4020204) - num(from & 0x4020204) << 5; /* guard back rank */ val += num(from & (b[DARK] & 0x41041 | b[LIGHT] & 0x82000820)) - num(to & (b[DARK] & 0x41041 | b[LIGHT] & 0x82000820)) << 7; val += num(from & (b[DARK] & 0x1040 | b[LIGHT] & 0x80000020)) - num(to & (b[DARK] & 0x1040 | b[LIGHT] & 0x80000020)) << 5; /* mobility */ val += num(jump) << 7 | num(slide) << 5; v++; movers(); val -= num(jump) << 7 | num(slide) << 5; v--; movers(); /* advance */ val += num(from & b[DARK] & 0x8208200 | from & b[LIGHT] & 0x10410004) - num(to & b[DARK] & 0x8208200 | to & b[LIGHT] & 0x10410004) << 4; val += num(from & b[DARK] & 0x10410004 | from & b[LIGHT] & 0x8208200) - num(to & b[DARK] & 0x10410004 | to & b[LIGHT] & 0x8208200) << 5; val += num(from & b[DARK] & 0x20820008 | from & b[LIGHT] & 0x4104100) - num(to & b[DARK] & 0x20820008 | to & b[LIGHT] & 0x4104100) << 6; val += num(from & b[DARK] & 0x41000410 | from & b[LIGHT] & 0x82082) - num(to & b[DARK] & 0x41000410 | to & b[LIGHT] & 0x82082) << 7; /* guarding the back rank and double corner is usually a good idea */ val += num(from & b[DARK] & 0x41043 | from & b[LIGHT] & 0x82000c20) - num(to & b[DARK] & 0x41043 | to & b[LIGHT] & 0x82000c20) << 5; /* try to keep kings off the edge */ val += num(tos & 0x82461e67) - num(froms & 0x82461e67) << 5; /* go in for the kill */ if(num(b[DARK] | b[LIGHT]) < 6 && α > β){ val -= num(b[~v & 1] & 0xc03) << 11; if(froms) do{ froms |= froms >> 1 & ↗ | (froms >> 7 | froms << 25) & ↖ | froms << 1 & ↙ | (froms << 7 | froms >> 25) & ↘; val -= 0x80; }while(!(froms & b[~v & 1])); } return val | rand() & 0xf; } old[0] = b[0]; old[1] = b[1]; old[2] = b[2]; for(froms = slide; α < β && (from = froms & -froms); froms ^= from) for(tos = slides(from); α < β && (to = tos & -tos); tos ^= to){ move(from | to); v++; movers(); val = jump ? -aijump(d - 1, -β, -α, nil) : -aislide(d - 1, -β, -α, nil); if(val > α){ α = val; if(mv != nil) *mv = from | to; } v--; b[0] = old[0]; b[1] = old[1]; b[2] = old[2]; } return α; } void sqprint(char *s, u32int bit){ int i; for(i = 0; i < 32 && !(bit & 1 << bitboard[i]); i++); if(i = 32 - i){ s[0] = '0' + i / 10; s[1] = '0' + i % 10; }else s[0] = s[1] = '?'; } void printjumps(char *str, int d, u32int ∅, u32int n, u32int s, u32int rm){ u32int x, to, j = 0; if(h) return; sqprint(str, n | s); str[2] = 'x'; str += 3; if((x = (n << 7 | n >> 25) & rm & ↘) && (to = (x << 7 | x >> 25) & ∅ & ↘) && ++j) printjumps(str, d + 1, ∅ ^ to | x | n, to, s ? to : 0, rm ^ x); if((x = n << 1 & rm & ↙) && (to = x << 1 & ∅ & ↙) && ++j) printjumps(str, d + 1, ∅ ^ to | x | n, to, s ? to : 0, rm ^ x); if((x = (s >> 7 | s << 25) & rm & ↖) && (to = (x >> 7 | x << 25) & ∅ & ↖) && ++j) printjumps(str, d + 1, ∅ ^ to | x | s, n ? to : 0, to, rm ^ x); if((x = s >> 1 & rm & ↗) && (to = x >> 1 & ∅ & ↗) && ++j) printjumps(str, d + 1, ∅ ^ to | x | s, n ? to : 0, to, rm ^ x); if(!j && !rm && (n | s) & m[v]) h = d; } u32int strtobit(char *s){ u32int n; if(s == nil || *s < '0' || *s > '3') return 0; n = (*s++ - '0') * 10; return *s < '0' || *s > '9' || (n = 32 + '0' - n - *s) > 31 ? 0 : 1 << bitboard[n]; } u32int jumped(u32int from, u32int to){ if(to & from << 14) return to >> 7; if(to & from >> 18 && to & 0x3c) return to << 25; if(to & from >> 18) return to >> 7; if(to & from << 2) return to >> 1; if(to & from >> 14) return to << 7; if(to & from << 18 && from & 0x3c) return to << 7; if(to & from << 18) return to >> 25; if(to & from >> 2) return to << 1; return 0; } void domove(char *s){ u32int from, to, mv, j[8]; int i; if(!(from = strtobit(s))) return; mv = 0; if(s[2] == 'x'){ i = 0; getjumps(j, &i, from, ~(b[DARK] | b[LIGHT]), from & (b[DARK] | b[LIGHT] & b[KING]), from & (b[LIGHT] | b[DARK] & b[KING]), b[~v & 1], 0); if(i & ~7) i = 8; do{ if(!(to = strtobit(s += 3))) return; mv ^= from | to; mv |= jumped(from, to); from = to; }while(s[2] == 'x'); while(--i >= 0 && j[i] != mv); if(i < 0) return; } else if((mv = from | strtobit(s + 3)) == from || !(mv & slides(from))) return; move(mv); m[v] = mv; t = ++v; movers(); } void chat(void *s, int n){ if(n >= MSGLEN) n = MSGLEN - 1; memmove(msg[msgn], s, n); msg[msgn][n] = '\0'; msgn = msgn + 1 & MSG - 1; drawmsgs(); } void main(int argc, char **argv){ Event e; Cursor busy = {{-1, -1}, {0xff, 0x80, 0xff, 0x80, 0xff, 0x00, 0xfe, 0x00, 0xff, 0x00, 0xff, 0x80, 0xff, 0xc0, 0xef, 0xe0, 0xc7, 0xf0, 0x03, 0xf0, 0x01, 0xe0, 0x00, 0xc0, 0x03, 0xff, 0x03, 0xff, 0x03, 0xff, 0x03, 0xff}, {0x00, 0x00, 0x7f, 0x00, 0x7e, 0x00, 0x7c, 0x00, 0x7e, 0x00, 0x7f, 0x00, 0x6f, 0x80, 0x47, 0xc0, 0x03, 0xe0, 0x01, 0xf0, 0x00, 0xe0, 0x00, 0x40, 0x00, 0x00, 0x01, 0xb6, 0x01, 0xb6, 0x00, 0x00}}; u32int bit, king; int i, fd = -1; char buf[MSGLEN], *f, *u, *s; SET(f); ARGBEGIN{ default: sysfatal("usage: %s [-9 file] [movetext]", argv0); case '9': f = EARGF(sysfatal("bad argument to -9")); if((fd = open(f, ORDWR)) < 0) sysfatal("open: %r"); }ARGEND if(initdraw(nil, nil, "draughts") < 0) sysfatal("initdraw: %r"); for(i = 0; i < HUE; i++) if((hue[i] = allocimage(display, Rect(0,0,1,1), screen->chan, 1, rgb[i])) == nil) sysfatal("allocimage: %r"); einit(Emouse | Ekeyboard); srand(truerand()); u = getuser(); new: zero(); for(t = i = 0; fd < 0 && i < argc; i++) domove(argv[i]); strcpy(p[0], u); strcpy(p[1], u); eresized(0); if(fd >= 0){ s = strchr(f, '\0') - 3; if(s >= f && !strcmp(s, "ctl")){ strcpy(buf, "light"); do eenter("play as? [dark/light]", buf, 6, &e.mouse); while(strcmp(buf, "dark") && strcmp(buf, "light")); s = buf + 9; if(*buf == 'd') s = strecpy(s, buf + MSGLEN, u) + 1; strcpy(s, "none"); if((i = eenter("opponent's name", s, MSGLEN + buf - s - 10, &e.mouse)) <= 0) sysfatal("player entry cancelled"); s += i; if(*buf == 'l') s = strecpy(s + 1, buf + MSGLEN, u); strcpy(buf, "draughts"); i = write(fd, buf, s - buf); close(fd); s = strecpy(buf, buf + MSGLEN, f) - 3; s = seprint(s, buf + MSGLEN, "%d", i); if((fd = open(buf, ORDWR)) < 0) sysfatal("open: %r"); chat(buf, s - buf); }else chat(f, strlen(f)); if((i = read(fd, buf, MSGLEN - 1)) < 12) sysfatal("not a draughts game?"); buf[i] = '\0'; if(strcmp(buf, "draughts")) sysfatal("not a draughts game!"); strncpy(p[0], buf + 9, 63); for(s = buf + 9; *s++ != '\0';); if(s - buf >= i) sysfatal("couldn't get player 2 name"); strncpy(p[1], s, 63); if(strcmp(p[0], u) && !(strcmp(p[1], u) && strcmp(p[1], "none"))) flip = -1; strcpy(buf + 6, buf + 9); strncpy(s - 4, " vs ", 4); while(*s++ != '\0'); chat(buf + 6, s - buf - 7); if(s - buf < i) for(s = strtok(s, " "); s != nil; s = strtok(nil, " ")) domove(s); if(strcmp(p[t & 1], u) && strcmp(p[t & 1], "none")) esetcursor(&busy); estart(Eremote, fd, MSGLEN); eresized(0); } else chat("new game: click user name to create ai player", 45); for(;;){ if(fd < 0 && !strncmp(p[t & 1], "ai level ", 9)){ flushimage(display, 1); if(ecankbd() || !jump && !slide || t + 33 >= MOVE){ chat("ai stopped", 10); while(ecankbd()) ekbd(); /* gulp */ strcpy(p[t & 1], u); drawlabel(t & 1); esetcursor(nil); continue; } esetcursor(&busy); if(jump){ aijump(p[t & 1][9] - '1', -∞, ∞, m + t); }else{ for(i = nrand(num(bit = slide)); i--; bit &= bit - 1); m[t] = bit & -bit; for(i = nrand(num(bit = slides(m[t]))); i--; bit &= bit - 1); m[t] |= bit & -bit; aislide(p[t & 1][9] - '1', -∞, ∞, m + t); } move(m[t]); v = ++t; movers(); sleep(500); drawboard(); if(!jump && !slide) goto gameover; esetcursor(nil); } else switch(event(&e)){ case Eremote: if(e.data[0] == '!' && e.n < MSGLEN){ while(v < t){move(m[v]); v++;} memmove(buf, e.data, e.n); buf[e.n] = '\0'; domove(buf + 1); drawboard(); if(!jump && !slide) goto gameover; esetcursor(strcmp(p[t & 1], u) && strcmp(p[t & 1], "none") ? &busy : nil); } else chat(e.data, e.n); break; case Ekeyboard: h = 0; switch(e.kbdc){ case 127: if(fd >= 0){ close(fd); s = strecpy(buf, buf + MSGLEN, u); *s++ = '\n'; } else s = buf; s = strecpy(s, buf + MSGLEN, argv0); zero(); for(v = 0; v < t; v++){ if(s + 35 >= buf + MSGLEN){ *s = '\0'; print(s = buf); } *s++ = ' '; if(~v & 1) s = seprint(s, s + 6, "%d. ", v + 2 >> 1); if(num(m[v]) == 2){ sqprint(s, m[v] & b[v & 1]); s[2] = '-'; move(m[v]); sqprint(s + 3, m[v] & b[v & 1]); s += 5; } else{ printjumps(s, 0, ~(b[DARK] | b[LIGHT]), m[v] & b[v & 1] & (b[DARK] | b[LIGHT] & b[KING]), m[v] & b[v & 1] & (b[LIGHT] | b[DARK] & b[KING]), m[v] & b[~v & 1]); s += 3 * h + 2; move(m[v]); h = 0; } } *s++ = '\n'; *s = '\0'; print(buf); exits(nil); case 0xf011: for(i = v - 1, zero(); v < i; v++) move(m[v]); break; case 0xf012: if(v < t){move(m[v]); v++;}break; case 0xf800: zero(); break; case 0xf00e: while(v < t){move(m[v]); v++;}break; case 0x1b: flip *= -1; eresized(0); break; case 'n': if(fd < 0) goto new; default: if(fd >= 0){ buf[0] = e.kbdc; buf[1] = '\0'; if((i = eenter("message", buf, MSGLEN, &e.mouse)) > 0) write(fd, buf, i); } continue; } if(fd < 0) movers(); drawboard(); break; case Emouse: if(!e.mouse.buttons || v + 1 >= MOVE || fd >= 0 && v != t || strcmp(p[v & 1], u) && strcmp(p[v & 1], "none")) continue; do eread(Emouse, &e); while(e.mouse.buttons); if(fd < 0 && (ptinrect(e.mouse.xy, r[i = 0]) || ptinrect(e.mouse.xy, r[i = 1]))){ *buf = '\0'; eenter("ai level ? [0–9]", buf, 2, &e.mouse); if(*buf == '0') strcpy(p[i], u); else if(*buf >= '1' && *buf <= '9'){ strcpy(p[i], "ai level x"); p[i][9] = *buf; } else continue; drawlabel(i); s = strecpy(buf, buf + MSGLEN, p[0]); s = strecpy(s, buf + MSGLEN, " vs "); s = strecpy(s, buf + MSGLEN, p[1]); chat(buf, s - buf); continue; } for(i = 0; i < 32 && !ptinrect(e.mouse.xy, sq[i]); i++); bit = (i < 32) << i; if(bit & h & ~(b[DARK] | b[LIGHT])){ if(jump){ s = buf; if(fd >= 0){ *s++ = '!'; sqprint(s++, h & jump); s++; } for(m[v] = 0, king = b[KING] & h;;){ if(fd >= 0){ *s++ = 'x'; sqprint(s++, bit); s++; } m[v] ^= h = h & jump | bit | jumped(h & jump, bit); move(h); h = jumps(bit); if(!h || !king && bit & b[KING]) break; h |= jump = bit; drawboard(); do{ do eread(Emouse, &e); while(!e.mouse.buttons); do eread(Emouse, &e); while(e.mouse.buttons); for(i = 0; i < 32 && !ptinrect(e.mouse.xy, sq[i]); i++); bit = (i < 32) << i; }while(!(bit & h & ~jump)); } if(fd >= 0){ *s++ = ' '; write(fd, buf, s - buf); } } else{ move(m[v] = bit | h & slide); if(fd >= 0){ buf[0] = '!'; sqprint(buf + 1, h & slide); buf[3] = '-'; sqprint(buf + 4, bit); buf[6] = ' '; write(fd, buf, 7); } } t = ++v; h = 0; movers(); if(!jump && !slide){gameover: esetcursor(nil); if(b[DARK] | b[LIGHT]){ s = strecpy(buf, buf + MSGLEN, p[!b[DARK]]); s = strecpy(s, buf + MSGLEN, " wins!"); } else s = strecpy(buf, buf + MSGLEN, "it's a draw!"); chat(buf, s - buf); if(fd >= 0) continue; strcpy(p[0], u); drawlabel(0); strcpy(p[1], u); drawlabel(1); esetcursor(nil); } } else if(bit & ~h & jump) h = bit | jumps(bit); else if(bit & ~h & slide) h = bit | slides(bit); else h = 0; drawboard(); break; } } }