From 3711c92f43eedbd698a9c477e3248fb87892fbd9 Mon Sep 17 00:00:00 2001 From: Tom Smeding Date: Fri, 15 Feb 2019 11:32:44 +0100 Subject: Multiple AI's (+RAND) --- .gitignore | 3 ++- Makefile | 38 ++++++++++++++++++++++++----- ai_mc.cpp | 79 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ ai_mc.h | 11 +++++++++ ai_rand.cpp | 19 +++++++++++++++ ai_rand.h | 11 +++++++++ main.cpp | 16 +++++++++++-- mc.cpp | 79 ------------------------------------------------------------- mc.h | 11 --------- 9 files changed, 168 insertions(+), 99 deletions(-) create mode 100644 ai_mc.cpp create mode 100644 ai_mc.h create mode 100644 ai_rand.cpp create mode 100644 ai_rand.h delete mode 100644 mc.cpp delete mode 100644 mc.h diff --git a/.gitignore b/.gitignore index 4f457ba..3e5e27a 100644 --- a/.gitignore +++ b/.gitignore @@ -1,2 +1,3 @@ -ai +aimc +airand .objs/ diff --git a/Makefile b/Makefile index c8bca05..c1a3ee7 100644 --- a/Makefile +++ b/Makefile @@ -2,20 +2,36 @@ CXX := g++ CXXFLAGS := -Wall -Wextra -std=c++11 -g -O2 LDFLAGS := -TARGET := ai OBJDIR := .objs -CXX_SOURCES := $(wildcard *.cpp) -OBJ_FILES := $(patsubst %.cpp,$(OBJDIR)/%.o,$(CXX_SOURCES)) -DEP_FILES := $(patsubst %.cpp,$(OBJDIR)/%.d,$(CXX_SOURCES)) +ifneq ($(value AI),) + AI_UPPER := $(shell echo '$(value AI)' | tr a-z A-Z) + AI_LOWER := $(shell echo '$(value AI)' | tr A-Z a-z) +else + AI_UPPER := MC + AI_LOWER := mc +endif +CXXFLAGS += -DAI=$(AI_UPPER) -.PHONY: all clean +MAIN_OBJ := $(OBJDIR)/main_$(AI_LOWER).o +CXX_SOURCES := $(filter-out main.cpp ai_%.cpp,$(wildcard *.cpp)) ai_$(AI_LOWER).cpp +OBJ_FILES := $(patsubst %.cpp,$(OBJDIR)/%.o,$(CXX_SOURCES)) $(MAIN_OBJ) +DEP_FILES := $(patsubst %.cpp,$(OBJDIR)/%.d,$(CXX_SOURCES)) $(MAIN_OBJ:.o=.d) + +TARGET := ai$(AI_LOWER) + +AI_ALL_LOWER := $(patsubst ai_%.cpp,%,$(wildcard ai_*.cpp)) + +TARGET_ALL := $(patsubst %,ai%,$(AI_ALL_LOWER)) + + +.PHONY: all clean debug all: $(TARGET) clean: - rm -f $(TARGET) + rm -f $(TARGET_ALL) rm -rf $(OBJDIR) $(TARGET): $(OBJ_FILES) termio/libtermio.a @@ -32,6 +48,16 @@ $(OBJDIR)/%.d: %.cpp termio/libtermio.a @echo DEP $< @$(CXX) -MT $(OBJDIR)/$*.o -MM $(CXXFLAGS) $< >$@ +$(OBJDIR)/main_$(AI_LOWER).o: main.cpp termio/libtermio.a + @mkdir -p $(dir $@) + @echo CXX "$< -o $(notdir $@)" + @$(CXX) $(CXXFLAGS) -c -o $@ $< + +$(OBJDIR)/main_$(AI_LOWER).d: main.cpp termio/libtermio.a + @mkdir -p $(dir $@) + @echo DEP "$< -o $(notdir $@)" + @$(CXX) -MT $(OBJDIR)/$*.o -MM $(CXXFLAGS) $< >$@ + termio/.git: git submodule update --init diff --git a/ai_mc.cpp b/ai_mc.cpp new file mode 100644 index 0000000..6175d96 --- /dev/null +++ b/ai_mc.cpp @@ -0,0 +1,79 @@ +#include +#include +#include +#include "ai_mc.h" +#include "util.h" + +using namespace std; + +#define NPLAYOUTS 1000 +#define SCORE_WIN 1 +#define SCORE_LOSE (-1) +#define SCORE_TIE 0 + + +// Takes copy of board, since it probably isn't worth it to undo the whole rest +// of the game. +// TODO: Multiply the playout score with its cumulative probability (which is +// pretty small!) to get a probabilistically correct estimate of the expected +// score. +static int playout(Board bd, uint8_t myclr) { + // cerr << " PLAYOUT" << endl; + while (bd.bag.totalLeft() > 0) { + uint8_t clr = bd.bag.drawRandom(); + + int moves[BSZ * BSZ], nmoves = 0; + bd.forEachMove([&moves, &nmoves](int idx) { moves[nmoves++] = idx; }); + + assert(nmoves > 0); + int idx = moves[random() % nmoves]; + + // cerr << " idx = " << Idx(idx) << " clr=" << (unsigned)clr << endl; + + uint8_t win = bd.putCW(idx, clr); + if (win != 0) { + return win == myclr ? SCORE_WIN : SCORE_LOSE; + } + } + + return SCORE_TIE; +} + + +int MC::calcMove(Board &bd, uint8_t myclr) { + assert(bd.bag.totalLeft() > 0); + + float maxscore = INT_MIN; + int maxat = -1; + + bd.forEachMove([&bd, myclr, &maxscore, &maxat](int idx) { + // cerr << "MC::calcMove: trying idx=" << Idx(idx) << endl; + float score = 0; + + for (int i = 0; i < NPLAYOUTS; i++) { + // cerr << "playout " << i << endl; + + uint8_t clr = bd.bag.peekRandom(); + float probability = (float)bd.bag.numLeft(clr) / bd.bag.totalLeft(); + bd.bag.drawColour(clr); + + // cerr << " random clr=" << (unsigned)clr << endl; + uint8_t win = bd.putCW(idx, clr); + if (win != 0) { + score += probability * (win == myclr ? SCORE_WIN : SCORE_LOSE); + } else { + score += probability * playout(bd, myclr); + } + + bd.bag.replace(clr); + bd.undo(idx); + } + + if (score > maxscore) { + maxscore = score; + maxat = idx; + } + }); + + return maxat; +} diff --git a/ai_mc.h b/ai_mc.h new file mode 100644 index 0000000..d4221d9 --- /dev/null +++ b/ai_mc.h @@ -0,0 +1,11 @@ +#pragma once + +#include "board.h" + +using namespace std; + + +namespace MC { + // bd will be unchanged upon return + int calcMove(Board &bd, uint8_t myclr); +} diff --git a/ai_rand.cpp b/ai_rand.cpp new file mode 100644 index 0000000..7479d01 --- /dev/null +++ b/ai_rand.cpp @@ -0,0 +1,19 @@ +#include +#include +#include +#include "ai_rand.h" +#include "util.h" + +using namespace std; + + +int RAND::calcMove(Board &bd, uint8_t myclr) { + (void)myclr; + assert(bd.bag.totalLeft() > 0); + + int moves[BSZ * BSZ], nmoves = 0; + bd.forEachMove([&moves, &nmoves](int idx) { moves[nmoves++] = idx; }); + + assert(nmoves > 0); + return moves[random() % nmoves]; +} diff --git a/ai_rand.h b/ai_rand.h new file mode 100644 index 0000000..9185ccd --- /dev/null +++ b/ai_rand.h @@ -0,0 +1,11 @@ +#pragma once + +#include "board.h" + +using namespace std; + + +namespace RAND { + // bd will be unchanged upon return + int calcMove(Board &bd, uint8_t myclr); +} diff --git a/main.cpp b/main.cpp index c53f5ae..61cd573 100644 --- a/main.cpp +++ b/main.cpp @@ -2,18 +2,28 @@ #include #include #include "board.h" -#include "mc.h" +#include "ai_mc.h" +#include "ai_rand.h" #include "ui.h" #include "util.h" using namespace std; +#define STR_(x) #x +#define STR(x) STR_(x) + +#ifndef AI +#define AI MC +#endif + int main() { struct timeval tv; gettimeofday(&tv, nullptr); srandom(tv.tv_sec * 1000000U + tv.tv_usec); + cerr << "Using AI " << STR(AI) << endl; + Board bd = Board::makeEmpty(); cerr << "Initial stone at " << Idx(BSZ * BMID + BMID) << endl; bd.put(BSZ * BMID + BMID, bd.bag.drawRandom()); @@ -30,7 +40,7 @@ int main() { cout << "YOUR TURN." << endl; idx = UI::getMove(bd); } else { - idx = MC::calcMove(bd, onturn); + idx = AI::calcMove(bd, onturn); } uint8_t clr = bd.bag.drawRandom(); @@ -45,4 +55,6 @@ int main() { onturn = NEXTTURN(onturn); } + + cout << "TIE" << endl; } diff --git a/mc.cpp b/mc.cpp deleted file mode 100644 index 5e64102..0000000 --- a/mc.cpp +++ /dev/null @@ -1,79 +0,0 @@ -#include -#include -#include -#include "mc.h" -#include "util.h" - -using namespace std; - -#define NPLAYOUTS 1000 -#define SCORE_WIN 1 -#define SCORE_LOSE (-1) -#define SCORE_TIE 0 - - -// Takes copy of board, since it probably isn't worth it to undo the whole rest -// of the game. -// TODO: Multiply the playout score with its cumulative probability (which is -// pretty small!) to get a probabilistically correct estimate of the expected -// score. -static int playout(Board bd, uint8_t myclr) { - // cerr << " PLAYOUT" << endl; - while (bd.bag.totalLeft() > 0) { - uint8_t clr = bd.bag.drawRandom(); - - int moves[BSZ * BSZ], nmoves = 0; - bd.forEachMove([&moves, &nmoves](int idx) { moves[nmoves++] = idx; }); - - assert(nmoves > 0); - int idx = moves[random() % nmoves]; - - // cerr << " idx = " << Idx(idx) << " clr=" << (unsigned)clr << endl; - - uint8_t win = bd.putCW(idx, clr); - if (win != 0) { - return win == myclr ? SCORE_WIN : SCORE_LOSE; - } - } - - return SCORE_TIE; -} - - -int MC::calcMove(Board &bd, uint8_t myclr) { - assert(bd.bag.totalLeft() > 0); - - float maxscore = INT_MIN; - int maxat = -1; - - bd.forEachMove([&bd, myclr, &maxscore, &maxat](int idx) { - // cerr << "MC::calcMove: trying idx=" << Idx(idx) << endl; - float score = 0; - - for (int i = 0; i < NPLAYOUTS; i++) { - // cerr << "playout " << i << endl; - - uint8_t clr = bd.bag.peekRandom(); - float probability = (float)bd.bag.numLeft(clr) / bd.bag.totalLeft(); - bd.bag.drawColour(clr); - - // cerr << " random clr=" << (unsigned)clr << endl; - uint8_t win = bd.putCW(idx, clr); - if (win != 0) { - score += probability * (win == myclr ? SCORE_WIN : SCORE_LOSE); - } else { - score += probability * playout(bd, myclr); - } - - bd.bag.replace(clr); - bd.undo(idx); - } - - if (score > maxscore) { - maxscore = score; - maxat = idx; - } - }); - - return maxat; -} diff --git a/mc.h b/mc.h deleted file mode 100644 index d4221d9..0000000 --- a/mc.h +++ /dev/null @@ -1,11 +0,0 @@ -#pragma once - -#include "board.h" - -using namespace std; - - -namespace MC { - // bd will be unchanged upon return - int calcMove(Board &bd, uint8_t myclr); -} -- cgit v1.2.3-54-g00ecf