8 votes

What programming/technical projects have you been working on?

This is a recurring post to discuss programming or other technical projects that we've been working on. Tell us about one of your recent projects, either at work or personal projects. What's interesting about it? Are you having trouble with anything?

14 comments

  1. [3]
    DataWraith
    Link
    I've been building a Python AI for the game Ultimate Tic-Tac-Toe over the last week. The twist of the game is that almost every move you make constrains the next opponent move to a different one...

    I've been building a Python AI for the game Ultimate Tic-Tac-Toe over the last week.

    The twist of the game is that almost every move you make constrains the next opponent move to a different one of the nine 3x3 sub-grids, so trying to read ahead is difficult for human players.
    AI players using a traditional Minimax-style algorithm have a different problem in that there is no known-good heuristic to prune the tree, and contrary to normal Tic-Tac-Toe, you can't exhaustively search all variations. It is difficult to tell algorithmically who is ahead in a game until the last few moves (60 to 80 moves into the game).

    One solution to the problem of evaluating a state is to run a bunch of random simulations under the assumption that whoever is ahead will win a larger percentage of such random simulations. This is the idea behind vanilla Monte Carlo Tree Search. Most existing programs I could find use this approach.

    However, I was curious if I could use a neural network to learn the game, AlphaZero-style.
    I found a paper that combines neural network learning with a Minimax algorithm; the whole thing is a good bit simpler than AlphaZero, and, looking at the paper results, it could potentially learn better and faster.

    So now I have a program that plays against itself in order to learn a neural network score heuristic (that the search can then use to prune the game tree). Each iteration builds a tree of ~400 000 board positions and then trains the neural network on the GPU for a few minutes, mimicking the results of the tree search. In theory, as the neural network gets more accurate, it in turn improves the tree search, leading to a virtuous cycle of self-improvement.

    I think I ironed out most of the bugs by now, but I'll probably need to continuously run this for at least a week or two before it gets anywhere; I hope I'll be patient enough to see this through instead of being drawn away by the next shiny thing...

    7 votes
    1. [2]
      Apos
      Link Parent
      Ultimate Tic-Tac-Toe is so cool! I'm really tempted to implement the game myself. You'd think it's an easy game to solve since it's tic-tac-toe but in reality it's not? I guess it's more similar...

      Ultimate Tic-Tac-Toe is so cool! I'm really tempted to implement the game myself. You'd think it's an easy game to solve since it's tic-tac-toe but in reality it's not? I guess it's more similar to something like "go" than chess?

      3 votes
      1. DataWraith
        Link Parent
        Yeah. The difficulty is that you can't easily tell who is ahead until late in the game, which was also the problem in Go prior to AlphaGo. That plus the number of legal moves you have to search,...

        Yeah. The difficulty is that you can't easily tell who is ahead until late in the game, which was also the problem in Go prior to AlphaGo. That plus the number of legal moves you have to search, which is of course less of a problem in UTTT.

        Minimax.dev has a very nice writeup and sourcecode for a performant Rust implementation of Ultimate Tic-TacToe, with the goal of using Proof Number Search to actually solve the game instead of just playing it, but he seems to not have been able to get his hands on a machine with enough RAM to fit the complete game tree.

  2. [10]
    adi
    (edited )
    Link
    I built https://mkws.sh, a simple static site generator. You just download it and off you go, no package manager. It uses shell scripting for templating and has only two dependencies, pp, a simple...

    I built https://mkws.sh, a simple static site generator.

    You just download it and off you go, no package manager.

    It uses shell scripting for templating and has only two dependencies, pp, a simple preprocessor and lmt, a utility to get last modified time for a file from lts.

    Doesn't have any config files, you just customize the generating script.

    Because it uses shell script as templating you can use any UNIX tool in the templates, jlj uses pyphoon to show an ASCII Art Phase of the Moon on https://nfld.uk/.

    4 votes
    1. [9]
      Apos
      Link Parent
      Pretty cool! Never realized I could use single quotes in HTML. Is the source code browsable online? Or the .tgz has to be downloaded? Looks like one of the showcase website is down...

      Pretty cool! Never realized I could use single quotes in HTML. Is the source code browsable online? Or the .tgz has to be downloaded?

      Looks like one of the showcase website is down https://andrewjvpowell.com/.

      2 votes
      1. [8]
        adi
        Link Parent
        The components are https://mkws.sh/pp.html, https://mkws.sh/lts.html, https://mkws.sh/themes/base/base@3.0.2.tgz and https://mkws.sh/mkws/mkws@4.0.14.tgz. You can read the sources on their pages...

        Is the source code browsable online? Or the .tgz has to be downloaded?

        The components are https://mkws.sh/pp.html, https://mkws.sh/lts.html, https://mkws.sh/themes/base/base@3.0.2.tgz and https://mkws.sh/mkws/mkws@4.0.14.tgz. You can read the sources on their pages and in the archives.

        The main binaries file is just those pieces compiled and put in a single archive so you could just download and start building.

        There is a GitHub mirror here, but stuff is a little bit out of sync https://github.com/mkws-1.

        Looks like one of the showcase website is down https://andrewjvpowell.com/.

        The author recently moved to solar powering his website and still has some issues. This version works https://www.andrewjvpowell.com/.

        3 votes
        1. [7]
          Apos
          Link Parent
          That site also doesn't work, I get a SSL_ERROR_ACCESS_DENIED_ALERT error. Why did you do a link from README.md -> README in the mkws repo? I think it's the first time I see that.

          That site also doesn't work, I get a SSL_ERROR_ACCESS_DENIED_ALERT error.


          Why did you do a link from README.md -> README in the mkws repo? I think it's the first time I see that.

          1 vote
          1. [6]
            adi
            Link Parent
            Didn't reply to this You can even not quote them at all as long as you quote the "special" cases https://html.spec.whatwg.org/multipage/syntax.html#unquoted https://www.andrewjvpowell.com/ works...

            Didn't reply to this

            Never realized I could use single quotes in HTML.

            You can even not quote them at all as long as you quote the "special" cases https://html.spec.whatwg.org/multipage/syntax.html#unquoted

            That site also doesn't work, I get a SSL_ERROR_ACCESS_DENIED_ALERT error.

            https://www.andrewjvpowell.com/ works fine on my end, I'll let the author know.

            Why did you do a link from README.md -> README in the mkws repo? I think it's the first time I see that.

            I prefer no extension on Markdown files (it's plain text, right?) but GitHub renders as Markdown only files ending in .md?

            1 vote
            1. [5]
              Apos
              Link Parent
              (╯°□°)╯︵ ┻━┻ But everything is plain text also, for example my C# files are plain text but I still put the .cs extension.

              You can even not quote them at all as long as you quote the "special" cases https://html.spec.whatwg.org/multipage/syntax.html#unquoted

              (╯°□°)╯︵ ┻━┻

              I prefer no extension on Markdown files (it's plain text, right?) but GitHub renders as Markdown only files ending in .md?

              But everything is plain text also, for example my C# files are plain text but I still put the .cs extension.

              1. [4]
                adi
                Link Parent
                READMEs are meant to be read only by humans and they don't have an extension usually. I just believe it's cool that it doesn't matter if the README is Markdown or not but I link it to README.md...

                READMEs are meant to be read only by humans and they don't have an extension usually. I just believe it's cool that it doesn't matter if the README is Markdown or not but I link it to README.md for the rendering because "it happens" to be Markdown if it makes sense.

                1. [3]
                  Apos
                  Link Parent
                  But those wouldn't be done in markdown, for example: https://github.com/FNA-XNA/FNA.

                  But those wouldn't be done in markdown, for example: https://github.com/FNA-XNA/FNA.

                  1. [2]
                    adi
                    (edited )
                    Link Parent
                    https://github.com/FNA-XNA/FNA/blob/master/README can be interpreted as Markdown That's why I'd rather not have any extension even if it's Markdown.

                    https://github.com/FNA-XNA/FNA/blob/master/README can be interpreted as Markdown

                    The idea is that a Markdown-formatted document should be publishable as-is, as plain text, without looking like it’s been marked up with tags or formatting instructions.

                    That's why I'd rather not have any extension even if it's Markdown.

                    1 vote
                    1. Apos
                      Link Parent
                      Wait you're right! 😮 And looks like vscode opens it as markdown out of the box even without the extension. I'll have to remember that trick.

                      Wait you're right! 😮

                      And looks like vscode opens it as markdown out of the box even without the extension. I'll have to remember that trick.

                      1 vote
  3. spctrvl
    Link
    I've about finished with the conversion of my Maker Select v2 to an SKR 1.4 Turbo board. It basically works but I keep running into smallish issues that get me on to the upgrade train, though...

    I've about finished with the conversion of my Maker Select v2 to an SKR 1.4 Turbo board. It basically works but I keep running into smallish issues that get me on to the upgrade train, though there's little enough stock on the printer left to upgrade. I've switched out the thermistor and heat block for the upgraded gulf coast models, installed the bltouch autolevelling mechanism, printed a replacement cooler to give it clearance (went from dii cooler to cii cooler), and I'm replacing the whole plastic extruder mechanism with an all metal dual gear one. Seems I can't click a link without finding something new to add, for the extruder I went from replacing the gear, to replacing the mechanism, to replacing the mechanism with a dual gear mechanism. And it's all so cheap I can hardly stop myself. At this rate, the TMC2226 drivers will be in before I've gotten it back together, I wasn't expecting them until October but they've already cleared customs stateside, so they might even be here this weekend.

    3 votes