Andrew Que Sites list Photos
Projects Contact
Main

December 31, 2015

Happy New Year!

   Closing out 2015 this evening, and giving 2016 a nice loud welcome.  We did a blacklight and laser theme.  For this Xiphos dyed some large pieces of canvas black and hung them in the living room.  This provided a blank canvas for florescent paint, which our guests would apply to the canvas.  I hung 48" florescent light fixtures and put in blacklight tubes.  We had expected to need more florescent tubes to fill all our fixtures, but as it turns out the home improvement store we usually get this item no longer carries them.  So we had to settle for only lighting the upstairs with blacklight.  To this end we employed 3x 48" double bulb fixtures, 1x 48" single bulb fixture, and a couple smaller fixtures.  The result is that every room upstairs had a good blacklight glow.  In addition, Xiphos picked up a new laser display that, in combination with fog, produced some really cool effects.  It set the mood nicely for that gathering.
   It has been 20 years since the New Year of 1996--a time marker that has significant importance to me.  I'd like to thanks Zen, Steve, Tyson and especially Laura for their parts.  Happy New Year.
   More parts arrived today and I went about completing a project I started a couple days ago.  My bicycle has a headlight, taillight, and a cell phone use to track and navigate.  I found the battery for my head light is cheap and ordered a much better battery than I had originally.  Then I got to thinking: why couldn't I power everything on the bike with a single battery?  My tail light uses AAA batteries, and with its 1 watt LED the batteries don't last extremely long.  I've been working with buck converters for awhile, and you can find them online really cheap.  So I picked up a pack of 10x 3A variable converters.  I set one to produce 3 VDC--the same power as 2x AAA in series--to run my tail light.  I then gutted the battery holding area of the taillight so it could fit the converter.  A wire runs out of the light to the battery pack.  The taillight is water tight, so I used some silicon calk to seal the hole.  Now my taillight runs off the headlight battery. 
   I used a second converter set to 5 volts and wired it to a USB cable.  That should provide power to my phone.  I had picked up a solar battery pack for my phone last summer.  The problem was it could only supply 5 volts at 1 amp, and my phone wanted 1.5 amps.  So when my screen was on, the phone battery would discharge.  I had to shut my screen off for my long bike trips to avoid running out of power.  The buck converters I have can provide 3 amps, so should work better.  To test this, I turned my phone screen on, disabled the auto screen off, turned the brightness all the way up, and turned on the GPS.  I kept the phone plugged into the my headlight battery and sure enough the battery stayed at 100% after an hour of runtime.
   The last part was constructing a multitap cable.  This allows the single battery to feed 4 sources.  I only have 3 items that need power, but the 4th port is to plug in the battery charger so I don't have to unplug anything.  Now I just need a bike trip to test things out.
   At long last Wisconsin has figured out it is winter.  Today we got a pretty good storm that dumped about 4 inches of snow, high winds, and poor travel conditions.  I decided to hang out at my local coffee shop in front of the fire with a cup of tea and a laptop.  I always bike to this place which is all of a half mile away, but this has to have been the longest half mile bike ride I've ever done--even with the 25 MPH tailwind I had.  My bicycle is a mountain bike with fairly knobby tires.  I've ridden in the snow in the past and it handles pretty well.  However, you can't move very quickly.  Riding over packed snow is the best, but the plows had not yet come through and I only had tire tracks to ride on.  That's fine if you can stay in them, and that isn't easy.  But I enjoyed every minute of the ride.  Challenging and unconventional.
   At coffee I worked on project.  I continued to work on my game project and successfully implemented alpha-beta pruning.  Initially the game was trying to maximize the number of gains the next move could create.  I switched it to maximize the score.  This allowed me to stop exploring a tree branch when the score dropped below the current high score.  That is, if the move isn't promising, don't bother considering it.  That greatly reduced the complexity of the AI search when the computer has to make a move.  I played a good number of games and have finally succeeded in occasionally beating the computer.  However, the AI is still a vicious adversary.
   The game still needs a good deal of clean up.  I think I can improve the AI speeds further by using bit masks rather than arrays.  In addition, the game needs to be separated from the user interface.  Once this is done, I will probably release it.

December 27, 2015

Implementing AI

Went back to address an old AI problem I started back in 2006. I had implemented a Javascript version of Ataxx, inspired by my own expense with a clone implemented in the microscope puzzle in the 7th Guest. My AI system only though head a single move. The AI would look to see what move would give it the greatest gains, and the worst possible loss. If the gains were greater than the losses, the gain move was taken. If the losses would be higher, a move to block this was taken.

I had wanted to implement a Minimax algorithm to think ahead further, but never got such a setup to work. One of the problems was my implementation was in Javascript, and this language wasn't designed to be fast. The project sat idle for ages until I decided at coffee the other day to have an other crack at the problem. I rewrote the game in C using ncurses for the user interface. This gives me all the raw power I could want.

Surprisingly, the game went together in about a day with about a quarter of that time getting myself use to the ncurses library. I started by implementing the user interface—something to display the playing field and allowing a user to make moves. This evolved into users alternating to make moves until the game had no moves left.

This allowed me to create some base functions for manipulating the game state. The Javascript version of the game didn't have these functions, which made implementing AI functions more difficult. Specifically, I needed a function to evaluate a move, returning both the resulting playing field and a number for gains made. This serves as the interface used for the UI and AI.

Evaluating what moves are available is an interesting problem. The playing field consists of 7x7 cells. Each player starts with 2 cells. A player's cell may move to any cell within two squares of itself. If it moves just a single square, the cell duplicates. If the cell is 2 moves away, the piece jumps to the new location, vacating the original position. Naturally, moving a single space results in a net gain. When moving, any cell owned by an opponent will be taken over. The goal is to take over as many cells on the board is possible. When the board is full, or no more moves can be made by a player, the game is over. Which ever player controls the most cells wins the game. Now the AI considerations.

When determining a move, one can look at it from the standpoint of player controlled cells. However much of the time several player cells can move into the same empty cell. For a complete game tree, each option would need to be evaluated. However, if the starting cells are a single square away, the results are identical. So that section of the game tree only needs to be evaluated once. For cells that are two squares away, multiple sources will still need to be considered because the originating piece moves to make this happen. However, if a cell can be occupied from both a cell that is one square away and a cell that is two squares away, the cells two squares away can be ignored. Why jump and loss a piece when you can duplicate and obtain the same results at no loss? So the game tree can be further pruned with this in mind.

That leaves the question: how to make a list of moves that need to be explored. For this, I keep a construct I call a Move, and I have a Move for each cell in the playing field (7x7). Each Move consists of a list of cells that can move into it. Any cell only has 24 possible ways into it, but since we prune this based on jumps and duplications, the worse-cast is the highly unlikely event the cell is surrounded by cells 2 squares away, for which there are 16. When a move is to be evaluated, a map of what cells can be occupied is generated, and each occupied cell contains a list of parent cells do to the occupying. Each one of these occupations needs to be evaluated. Impossible worst-case: 7x7x16 or 784. However, each of these moves is then evaluated further. So 784n where n is the number of moves to think ahead is the absolute worst case complexity.

For evaluation, each of the move in the Move table is evaluated for the net gain. If this gain is the same as the last move, this move is stored in a list. If this move has more gains than the last, the list is reset and the move stored. If this move has less gains, it is ignored. The goal is to find the move with the highest gains.  Now to think ahead, the gains for this round are subtracted by the gains from the next round. The next round is evaluated the same way, but as the other player. We assume the other player is going to try and maximize their gains.

How does it perform?  Well the game is fast enough with the computer thinking ahead 4 moves, and it's vicious.  While I can usually beat my Javascript version of Squares, I cannot beat this AI at all.  I'm not a very good player though so I might have to find someone else.  The only problem with this system is that I cannot figure out how to apply alpha-beta pruning.  Being able to do so should speed up the AI.

   Sun Dragon falls off-line after 120 days of runtime.  Looks like the battery completely died.  This is strange because the power curve show a sudden increase in voltage drop despite nothing having changed on the system.  High CPU load can account for increased energy usage, but the charts do not show such an increase.  I will have to keep an eye on the setup.
   Pictured are the rusty parts replaced on the garage door the other day.  Can't imagine why it failed.
   The results of an other subsurface scattering experiment.  This rendering took 2 days to complicate.  The material I was trying to design is suppose to be a translucent plastic, but looks more like gelatin.  As I played with various settings in Kerkythea I found the results differed significantly depending on which rendering engine, and level of detail.  Marks it hard to tweak parameters when each rendering method will produce different results and results take days.  So for now I am going to concede that I don't make a great creator of materials.
   Sometime over the summer one of the extension spring cables used to counterweight the garage door broke.  The stored energy from the spring did a fair bit of damage do the wood beam framing the structure, but luckily no one was hurt when this happened.  Since then the door has remained closed as without the counter weight the door is quite heavy.  Now that alternate side parking is in effect I have been parking in the garage so the driveway can accommodate an other car.  And with this came the incentive to repair the counter weight.
   When I inspected the setup I found that the cable had broken off the anchor point on the garage door.  There was a metal plate that bolts through the garage door and contained a hook to connect the counter weight cable, all made of rust.  The rust finally disintegrated enough of the metal that it broke under the force from the cable.  So after a couple of trips to the hardware store (because I didn't realize there were separate left and right brackets) I had all the parts I needed to do the repair.  Getting the old bracket off took some work.  But with the mass of a large hammer at velocities only a computer programmer would use, enough force was generated to dislodge the old bolts.  They had badly deformed due to rust, which is probably why they didn't want to come out.  After they had been removed, the new bracket went in pretty quick.  Then I went about connecting extension spring cable.  For this I needed Xiphos because it was hard to pull on the spring and direct the cable at the same time.  With the two of us I had the cable back on and a crazy thing happened: everything worked.  The garage door moves easily again.  For some reason I was thinking this was going to be harder than it was.