| |
In lugnet.org.ca.rtltoronto, Steve Hassenplug wrote:
> > > Here's a quick look at the interface for a code-only C$ game.
Folks who read rtlToronto can skip this part. I added it because I'm cross
posting to robotics.rcx.
For those who don't know, rtlToronto had a contest with robots playing Connect
Four. Creating a robot for this is double faceted. Getting robotic hardware to
interface to the connect four board, both scanning to determine where the
opponent dropped the chip, and dropping the chip to complete your turn were very
challenging tasks.
The other task was the RCX code that decided how to make the next move. Some
robots used something as simple as randomly picking a column from 1-7. The more
adventurous folks tackled the issue using a hypothetical look ahead mechanism
that uses alpha-beta pruning to discard obviously bad moves.
Steve traveled to Toronto and won the contest (so typical :). I was on a team
with Chris Magno (totalitarian leader LOL!) and Bruce Sheridon. We made a
vailant effort. I joined the team at the last minute and created the core game
engine.
Steve has been working on this issue for quite a while and done his usual
thorough research. He worked the problem very deeply, and was kind enough to
leave hints along the way as to what he was up to. He worked many of the issues
through lugnet, instead of behind the scenes, possibly to help the rest of us
along.
Steve based his RCX code on C code written by Keith Pomakis:
http://www.pomakis.com/~pomakis/c4/
I based my work on this as well.
I had a two phase solution. Basically just get the Pomakis code running on the
RCX. This part was pretty quick. My second phase solution was to add support
for pre-calculated table of opening moves. I had solutions for both of these
implemented in brickOS.
I tried to get it working under QuiteC, but had problems with receiving standard
RCX IR messages in QuiteC.
> >
> > Steve, can I have a few days to do some testing? I'm not sure when you want to
> > run the contest.
>
> Kevin,
>
> I really didn't plan on having a "contest". Sorry if I misled you. I know
> several people have code, and they wanted to know how it stacks up against other
> people's code. I'm just trying to set-up a format in which they can do that.
> So far, you're the only one who's really expressed interest. I still think
> Michael is working on something, but I'm not sure.
Not a problem..... just seeing how they stack up would be fine. Sorry if my
competitive nature jumped to a contest. It is a very interesting programming
problem given the constraints of the RCX.
>
> To answer your other questions:
> I can see a couple reasons for having more than one program (for going first or
> second). It's possible you could create a separate set of logic, designed to
> play to a draw, if you're going second. If, in fact, you believe your program
> could win, even playing second, there wouldn't be a good reason to play for a
> draw.
>
> Considering the fact that you can't load two of these programs in a single RCX,
> it's reasonable to assume you're using as much of the memory as possible. So,
> the difference between the two programs would just be the opening book. I
> suspect that's the reason for having two programs.
Bingo. The opening book for the first player is a mutually exclusive set of
board states from the opening book for the second player.
>
>
> Next, assuming that you weren't just making stuff up when you said you changed
> your -200 to 1, that means you changed your BrickOS code. So, I assume you did
> the same as Michael, and re-wrote some of your code in assembler. That sounds
> like a good plan.
Uhhhmmmm. The version I'm working on right now is not brickOS, nor is it QuiteC.
I'm using Kekoa Proudfoot's librcx as a base with cygwin's H8 gnu language
tools. librcx provides trivial interface to RCX's firmware and and hardware (in
particular, the sending and receiving of messages.
Nope, didn't take the time to write it in assembler, but I did take the time to
modify the C code to help the compiler produce better object code.
I made a number of algorithmic optimizations to the pomakis code:
1. I eliminated malloc stuff, and hard wired the code at compile time for a 6x7
board with 4 in a row to win. This eliminates the need for malloc and friends,
and therefore dependence on brickOS. It lets you know *exactly* how much memory
you are using, except for the C runtime stack.
2. I eliminated current_state->board in favor of a
current_state->columns[SIZE_X], where columns[0] contains a count of the number
of chips dropped in that column. This makes pushing state faster, and
eliminates scanning the board to determine what row the chip falls to.
3. I trimmed down push_state to three lines of code (hint: one of them is
memcpy); pop_state is two lines of code. They are both much smaller object code
too.
4. I changed the map array to be a preinitialized array of unsigned char. This
eliminated lots of code to initialize the ma, and cuts the size of the map in
half.
5. I optimized update_score, and merged it with drop_piece, because drop_piece
basically only increments the number of pieces and then updates score.
6. I modified calls to evaluate, so that the level is kept in a global
variable, instead of local. The eliminates pushing and popping of level during
all the hypothetical move calculation.
7. All the time is spent in evaluate(), push_state(), pop_state(),
drop_piece(), and update_score(). Optimizing the object code spit out by the
compiler is advantageous.
1. current_state->board is not really needed. You can use a simple
I created opening book generation code. This one took me a long time to get
right. Clearly spent the most time here.
My current solution to the opening book has a total of 12 bytes for, 84 bits for
current board state, 7 bits as a mask of the possible best moves at this board
state.
The opening book is sorted by board state, so I can do a simple binary search to
find out if there is a match. When the RCX code finds a match, it randomly
chooses amongst all the possible good moves.
When the lookup code fails to find a match, it bails out to the alpha/beta tree
algorithm of Pomakis, and calculates at a fixed skill level. One of the dilemas
is..... what level do I calculate the book at..... Steve, what did you do here?
librcx has very low memory overhead compared to brickOS firmware. This allows
me to have an opening book with 1700 or more possible board states, getting me
out to the 26th or 27th move.
I'm just finishing up the librcx version...... Steve, all kidding aside, you
really are very clever, which has driven me to extremes trying to solve this.
One of the ideas I had this morning was that instead of calculating opening book
pages at a given skill level, I could calculate it for a range of skill levels.
I'd want the book to identify the skill level that was used to create get to
this board state, so the RCX code can know how hard to think when it runs out of
book entries.
We'll see if I get that cut in.
>
>
> Steve
> "You are soooooo clever. I should not have bothered to even ask the
> question..... I mean I *am* talking to Steve" - KC
Kevin
|
|
Message has 2 Replies:
 | | Re: C$ - Code Only
|
| (...) I think most people seriously underestimated how hard building the robot would be. The funny thing is, all of rtlToronto's events have the same general premise: Build a robot that does something. Second, if you can make the robot do it well, (...) (20 years ago, 6-Feb-04, to lugnet.org.ca.rtltoronto, lugnet.robotics.rcx)
|
Message is in Reply To:
| | Re: C$ - Code Only
|
| (...) Kevin, I really didn't plan on having a "contest". Sorry if I misled you. I know several people have code, and they wanted to know how it stacks up against other people's code. I'm just trying to set-up a format in which they can do that. So (...) (20 years ago, 6-Feb-04, to lugnet.org.ca.rtltoronto)
|
28 Messages in This Thread:
 
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
